등차 직사각형

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

요약

정수로 채워진 n×m 격자에서 각 행과 각 열이 모두 등차수열을 이루는 가장 큰 직사각형을 찾아 넓이를 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 배열, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

$n \times m$ 개의 단위 정사각형으로 이루어진 격자가 주어진다. 각 단위 정사각형에는 정수가 하나씩 적혀 있다.

이 격자에서 등차 직사각형(arithmetic rectangle)을 찾으려 한다. 등차 직사각형이란 단위 정사각형들로 이루어진 직사각형 중에서, 모든 행과 모든 열의 수가 각각 등차수열을 이루는 것을 말한다. 여기서 등차수열이란 이웃한 두 항의 차가 항상 일정한 수열을 뜻한다.

우리의 목표는 가장 큰 등차 직사각형, 즉 가장 많은 단위 정사각형을 덮는 등차 직사각형을 찾는 것이다. 예를 들어 아래 격자에서 가장 큰 등차 직사각형은 $9$ 개의 단위 정사각형으로 이루어져 있다. 단위 정사각형 하나는 그 자체로 등차 직사각형이며, 길이가 $2$ 이하인 행이나 열은 항상 등차수열로 본다.

입력

첫째 줄에 테스트 케이스의 개수 $t$ ( $1 \le t \le 10000$ )가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$ 과 $m$ ( $1 \le n, m \le 3000$ )이 주어진다. 이어지는 $n$ 개의 줄에는 각각 $m$ 개의 정수가 주어지며, 각 정수는 $[0, 10^9]$ 범위에 있다. 이 수들이 격자를 나타낸다.

하나의 입력 파일 크기는 20 MB를 넘지 않는다.

출력

각 테스트 케이스마다 한 줄에 답을 하나씩, 총 $t$ 개의 줄을 출력한다. 하나의 테스트 케이스에 대한 답은 그 격자에서 찾을 수 있는 가장 큰 등차 직사각형이 포함하는 단위 정사각형의 개수(정수 하나)이다.

예제6

예제 1

입력

예상 출력

9
6

예제 2
입력
```
1
1 1
7
```
예상 출력
```
1
```
예제 3
입력
```
1
1 5
1 3 5 8 10
```
예상 출력
```
3
```
예제 4
입력
```
1
3 3
5 5 5
5 5 5
5 5 5
```
예상 출력
```
9
```
예제 5
입력
```
1
3 4
1 4 7 10
3 7 11 15
5 10 15 20
```
예상 출력
```
12
```
예제 6
입력
```
1
2 7
1 2 3 4 5 6 7
8 8 8 8 8 8 8
```
예상 출력
```
14
```