테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Parcel ======

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:seqtask#max_ranges_for_each_min|teflib.seqtask.max_ranges_for_each_min]]

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