====== 최대 직사각형 ======

===== 풀이 =====
  * [[ps:tutorial:부분 그리드#1로만 이루어진 최대 직사각형]] 을 찾는 문제. {{myicon>p5}} [[ps:problems:boj:8017]]과도 동일한 문제.
  * O(m)의 '히스토그램에서 가장 큰 직사각형 찾기'를 1행~i행 까지로 만든 누적합 배열에 n번 적용하는 방식으로 O(n*m)에 풀수 있다.

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 11873. 최대 직사각형".

- Problem link: https://www.acmicpc.net/problem/11873
- Solution link: http://www.teferi.net/ps/problems/boj/11873

Tags: [nge]
"""

import sys
from teflib import seqtask

END_OF_INPUT = '0 0'


def main():
    while (line := sys.stdin.readline().rstrip()) != END_OF_INPUT:
        N, M = [int(x) for x in line.split()]
        grid = [sys.stdin.readline().split() for _ in range(N)]

        answer = 0
        heights = [0] * M
        for row in grid:
            for i, x in enumerate(row):
                heights[i] = 0 if x == '0' else heights[i] + 1
            begs, ends = seqtask.max_ranges_for_each_min(heights)
            max_area = max(h * (e - b) for h, b, e in zip(heights, begs, ends))
            answer = max(max_area, answer)

        print(answer)


if __name__ == '__main__':
    main()

</dkpr>
  * Dependency: [[:ps:teflib:seqtask#max_ranges_for_each_min|teflib.seqtask.max_ranges_for_each_min]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}