• 1로만 이루어진 최대 직사각형 을 찾는 문제. Parcel과도 동일한 문제.
• O(m)의 '히스토그램에서 가장 큰 직사각형 찾기'를 1행~i행 까지로 만든 누적합 배열에 n번 적용하는 방식으로 O(n*m)에 풀수 있다.

"""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()

• Dependency: teflib.seqtask.max_ranges_for_each_min