땅 한 조각

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

요약

높이 격자에서 최고 높이와 최저 높이의 차이가 C 이하이고 너비가 100 이하인 직사각형 중 넓이가 가장 큰 것을 찾는다.

난이도: 어려움10점 중 8점
유형: 슬라이딩 윈도우, 행렬, 투 포인터, 완전 탐색
정답자: 아직 제출이 없습니다

문제

딩길빌(Dingilville) 주민들은 공항을 지을 땅을 고르려고 한다. 이들은 지형 지도를 가지고 있는데, 지도는 단위 정사각형들로 이루어진 직사각형 격자이다. 각 정사각형은 좌표 $(x, y)$ 로 구분되며, $x$ 는 가로(서–동) 좌표, $y$ 는 세로(남–북) 좌표이다. 지도에는 모든 정사각형의 높이가 적혀 있다.

다음 두 조건을 모두 만족하면서 넓이가 가장 큰(즉 포함하는 정사각형 개수가 가장 많은) 직사각형 영역을 찾아라.

영역에서 가장 높은 정사각형과 가장 낮은 정사각형의 높이 차가 주어진 한계 $C$ 이하이고,
영역의 너비(서–동 방향으로 늘어선 정사각형 개수)가 $100$ 이하이다.

이러한 가장 큰 영역의 넓이를 출력한다.

입력

첫째 줄에 세 정수 $U$ , $V$ , $C$ 가 주어진다.
이어지는 $V$ 개의 줄에는 $x = 1, \dots, U$ 에 대한 높이 $H_{xy}$ 가 주어진다. 더 정확히는 $H_{xy}$ 가 $(V - y + 2)$ 번째 입력 줄의 $x$ 번째 수로 나타난다. 즉 첫 데이터 줄은 가장 북쪽 행( $y = V$ ), 마지막 데이터 줄은 가장 남쪽 행( $y = 1$ )에 해당한다.

출력

두 조건을 모두 만족하는 영역의 가능한 가장 큰 넓이(정사각형 개수)를 정수 하나로 출력한다.

제한

$1 \le U \le 700$ , $1 \le V \le 700$ . 여기서 $U$ 는 서–동 방향 정사각형 개수, $V$ 는 남–북 방향 정사각형 개수이다.
$0 \le C \le 10$
$-30\,000 \le H_{xy} \le 30\,000$ . $H_{xy}$ 는 좌표 $(x, y)$ ( $1 \le x \le U$ , $1 \le y \le V$ )에 있는 정사각형의 높이이다.
지도의 남서쪽 모서리 정사각형은 좌표 $(1, 1)$ , 북동쪽 모서리는 좌표 $(U, V)$ 를 가진다.

예제3

예제 1

입력

10 15 4
41 40 41 38 39 39 40 42 40 40
39 40 43 40 36 37 35 39 42 42
44 41 39 40 38 40 41 38 35 37
38 38 33 39 36 37 32 36 38 40
39 40 39 39 39 40 40 41 43 41
39 40 41 38 39 38 39 39 39 42
36 39 39 39 39 40 39 41 40 41
31 37 36 41 41 40 39 41 40 40
40 40 40 42 41 40 39 39 39 39
42 40 44 40 38 40 39 39 37 41
41 41 40 39 39 40 41 40 39 40
47 46 49 43 43 41 41 40 39 42
42 41 41 39 40 39 42 40 42 42
41 44 49 43 46 41 42 41 42 42
45 40 42 42 46 42 44 40 42 41

예상 출력

예제 2
입력
```
3 3 0
2 2 2
2 2 2
2 2 2
```
예상 출력
```
9
```
예제 3
입력
```
1 1 0
5
```
예상 출력
```
1
```