만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

최대 직사각형

시간 제한3초메모리 제한512 MB

요약
0 0이 나올 때까지 각 이진 행렬에서 1로만 이루어진 가장 큰 직사각형 넓이를 구합니다.
난이도

보통10점 중 6점

유형
스택, 행렬, 동적 계획법
정답자
아직 제출이 없습니다

문제

0과 1로 이루어진 N×MN \times M 크기의 행렬이 주어진다. 원소가 모두 1인 부분 직사각형 가운데 넓이가 가장 큰 것의 넓이를 구하라.

부분 직사각형은 연속한 행 구간과 연속한 열 구간이 만나는 영역이고, 넓이는 그 안에 들어 있는 칸의 개수다.

입력

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에 NN과 MM이 주어진다 (1≤N,M≤10001 \le N, M \le 1000). 이어지는 NN개 줄에는 각 행의 원소 MM개가 공백으로 구분되어 주어지며, 각 원소는 0 또는 1이다.

마지막 줄에는 0이 두 개 주어진다. 이 줄은 테스트 케이스가 아니다.

출력

각 테스트 케이스마다 원소가 모두 1인 가장 큰 직사각형의 넓이를 한 줄에 하나씩 출력한다. 그런 직사각형이 없으면 0을 출력한다.

예제2

  1. 예제 1

    입력
    4 5
    0 1 0 1 1
    1 1 1 1 1
    0 1 1 1 0
    1 1 1 1 1
    3 4
    1 1 1 1
    1 1 1 1
    1 1 1 1
    6 6
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0 0 0 0 0
    0 0
    
    예상 출력
    9
    12
    0
    
  2. 예제 2

    입력
    2 3
    1 0 1
    1 1 1
    0 0
    
    예상 출력
    3