가장 큰 직사각형

시간 제한0.6초메모리 제한128 MB

요약

열의 순서를 자유롭게 재배열할 수 있는 0/1 행렬에서, 각 셀 위쪽 연속 1의 높이를 구해 정렬한 뒤 만들 수 있는 최대 1 사각형의 넓이를 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬, 행렬
정답자: 아직 제출이 없습니다

문제

0과 1로 이루어진 N × M 행렬이 주어진다. 모든 칸이 1로 채워진 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 단, 열의 순서는 자유롭게 바꿀 수 있다. 즉, 원하는 열들을 골라 임의의 순서로 서로 이웃하게 재배치한 뒤, 그 열들과 어떤 연속된 행 구간이 모두 1이면 하나의 직사각형이 된다. (행의 순서는 바꿀 수 없다.)

입력

첫째 줄에 두 정수 N과 M이 공백으로 구분되어 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 행렬이 주어지며, 각 줄은 0과 1로 이루어진 길이 M의 문자열이다.

출력

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

제한

1 ≤ N ≤ 15000
1 ≤ M ≤ 1500

힌트

열의 순서를 적절히 바꿔 2번째, 4번째, 5번째 열이 서로 이웃하도록 놓으면 넓이가 21인 직사각형을 얻을 수 있다. (2번째 ~ 8번째 행 × 2, 4, 5번째 열)

예제5

예제 1

입력

예상 출력

예제 2
입력
```
1 1
1
```
예상 출력
```
1
```
예제 3
입력
```
3 4
1111
1111
1111
```
예상 출력
```
12
```
예제 4
입력
```
3 4
1010
1010
1010
```
예상 출력
```
6
```
예제 5
입력
```
5 1
1
0
1
1
1
```
예상 출력
```
3
```