Parcel

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

"""Solution code for "BOJ 8017. Parcel".

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

Tags: [subgrid]
"""

import sys
from teflib import seqtask

ARABLE = '0'
WASTE = '1'


def main():
    n = int(sys.stdin.readline())
    grid = [sys.stdin.readline().split() for _ in range(n)]

    answer = 0
    heights = [0] * n
    for row in grid:
        for i, v in enumerate(row):
            heights[i] = heights[i] + 1 if v == ARABLE else 0
        begs, ends = seqtask.max_ranges_for_each_min(heights)
        answer = max(
            answer,
            *((end - beg) * h for beg, end, h in zip(begs, ends, heights)),
        )

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.seqtask.max_ranges_for_each_min