6037 : 히스토그램 최대 직사각형 — 0-1 행렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 2차원 격자판 행렬이 주어지며, 각 칸은 0 또는 1로 채워져 있습니다.
이 행렬 내부에서 1로만 구성된 가장 넓은 직사각형 영역의 크기(칸의 개수)를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 행렬 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 원소는 0 또는 1입니다.
이 행렬 내부에서 1로만 구성된 가장 넓은 직사각형 영역의 크기(칸의 개수)를 구하는 프로그램을 작성하십시오.
[제약 조건]
• 행렬 크기: $1 \le N, M \le 1{,}000$ (정수)
• 각 원소는 0 또는 1입니다.
입력 설명
첫째 줄에 행렬의 세로 크기 $N$과 가로 크기 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 1,000$)
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $M$개의 0 또는 1이 공백으로 구분되어 주어집니다.
둘째 줄부터 $N$개의 줄에 걸쳐 각 줄에 $M$개의 0 또는 1이 공백으로 구분되어 주어집니다.
출력 설명
1로만 구성된 최대 직사각형 영역의 넓이(1의 개수)를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
0 1 1 0
0 1 1 1
1 1 1 1
1 1 0 0
출력 예시
COPY
복사되었습니다!
복사되었습니다!
6도움
각 행을 밑변으로 삼는 히스토그램을 구성합니다. 위쪽으로 연속된 1의 개수를 높이로 누적하여 구한 높이 배열들에 대해 매 행마다 단조 스택 기반 최대 직사각형을 갱신합니다.