시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.6 초 128 MB 324 33 25 17.986%

문제

0과 1로 이루어진 N * M 행렬이 주어졌을 때, 1로 이루어진 가장 큰 직사각형을 찾는 프로그램을 작성하시오. 직사각형은 전체가 1로 가득 차있어야 한다. 또한, 열을 순서를 바꿀 수 있다.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 행렬이 주어진다.

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다.

제한

  • 1 ≤ N ≤ 15000
  • 1 ≤ M ≤ 1500

예제 입력 1

10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

예제 출력 1

21

힌트

열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열)

W3sicHJvYmxlbV9pZCI6IjMzMjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSIsImRlc2NyaXB0aW9uIjoiPHA+MFx1YWNmYyAxXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBOICogTSBcdWQ1ODlcdWI4MmNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgMVx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM4MDRcdWNjYjRcdWFjMDAgMVx1Yjg1YyBcdWFjMDBcdWI0ZGQgXHVjYzI4XHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWM1ZjRcdWM3NDQgXHVjMjFjXHVjMTFjXHViOTdjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDU4OVx1YjgyY1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1ZjRcdWM3NTggXHVjMjFjXHVjMTFjXHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWJjMTRcdWFmZDQsIDJcdWM1ZjQsIDRcdWM1ZjQsIDVcdWM1ZjRcdWM3NzQgXHVjMTFjXHViODVjIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YWM4YyBcdWIxOTNcdWIyOTRcdWIyZTRcdWJhNzQsIFx1ZDA2Y1x1YWUzMFx1YWMwMCAyMVx1Yzc3OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuICgyXHVkNTg5fjhcdWQ1ODkgKiAyLDQsNVx1YzVmNCk8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4xJm5ic3A7JmxlOyBOJm5ic3A7JmxlOyAxNTAwMDxcL2xpPlxyXG5cdDxsaT4xJm5ic3A7JmxlOyBNJm5ic3A7JmxlOyAxNTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMzIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTG9ncyIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYW4gTiB4IE0gYmluYXJ5IG1hdHJpeCwgZmluZCB0aGUgYXJlYSBvZiB0aGUgYmlnZ2VzdCByZWN0YW5nbGUgY29uc2lzdGluZyBlbnRpcmVseSBvZiB2YWx1ZXMgb2YgMSwga25vd2luZyB0aGF0IHlvdSBjYW4gcGVybXV0ZSB0aGUgY29sdW1ucyBvZiB0aGUgbWF0cml4LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IG9uZSBzcGFjZTogTiBhbmQgTS4gVGhlIGZvbGxvd2luZyBOIGxpbmVzIHdpbGwgY29udGFpbiBNIGNoYXJhY3RlcnMgb2YgMCBvciAxLCBkZXNjcmliaW5nIHRoZSBtYXRyaXguICgxICZsZTsgTiAmbGU7IDE1MDAwLCAxICZsZTsgTSAmbGU7IDE1MDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG9ubHkgbGluZSBvZiB0aGUgb3V0cHV0IHdpbGwgY29udGFpbiB0aGUgYXJlYSBvZiB0aGUgbGFyZ2VzdCByZWN0YW5nbGUuPFwvcD5cclxuIiwiaGludCI6IjxwPkJ5IHBlcm11dGluZyB0aGUgY29sdW1ucyBzdWNoIHRoYXQgY29sdW1ucyAyLCA0IGFuZCA1IGFyZSBhZGphY2VudCB5b3UgaGF2ZSBhIHJlY3RhbmdsZSBvZiBhcmVhIDIxIChyb3dzIDItOCBhbmQgY29sdW1ucyAyLCA0LCA1KS48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2009 4번

  • 문제를 번역한 사람: baekjoon
  • 시간 제한을 수정한 사람: Green55