표준 문제

시간 제한3초메모리 제한128 MB

요약
0과 1로 이루어진 표에서 최대 백만 개의 질의마다 지정된 행 범위 안에 있는 최대 크기의 0 사각형 면적을 구합니다.
난이도

어려움10점 중 9점

유형
세그먼트 트리, 분할 정복, 스택, 행렬
정답자
아직 제출이 없습니다

문제

N행 M열의 표가 주어진다. 각 칸에는 0 또는 1이 들어 있다.

여러 질의가 주어진다. 각 질의는 위쪽 행 r1과 아래쪽 행 r2를 지정한다. 답으로 선택하는 직사각형은 모든 행이 r1부터 r2까지의 범위 안에 있어야 하며, r1행과 r2행도 사용할 수 있다. 이 범위 밖의 행은 사용할 수 없다.

각 질의마다 모든 칸이 0인 직사각형 중 넓이가 가장 큰 것의 넓이를 구하라. 직사각형의 변은 표의 행과 열에 평행하며, 넓이는 포함한 칸의 개수이다.

입력

첫째 줄에 표의 크기 N과 M이 공백으로 구분되어 주어진다.

다음 N개의 줄에는 각 줄마다 M개의 수가 공백으로 구분되어 주어진다. 각 수는 0 또는 1이다.

그다음 줄에 질의의 수 Q가 주어진다. 다음 Q개의 줄에는 각 질의의 위쪽 행과 아래쪽 행을 나타내는 두 정수 r1, r2가 공백으로 구분되어 주어진다.

출력

각 질의마다 한 줄에 하나의 정수를 출력한다. 이 정수는 주어진 행 범위 안에 놓을 수 있는 가장 큰 0 직사각형의 넓이이다.

제한

  • 1 <= N, M <= 1000
  • 1 <= Q <= 10^6
  • 1 <= r1 <= r2 <= N

예제1

  1. 예제 1

    입력
    3 4
0 1 0 0
1 0 0 0
0 0 0 0
3
1 2
2 3
1 3
    예상 출력
    4
6
6