문제2014--The Matrix

2014: The Matrix

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 33  통과: 13
[제출] [채점기록] [묻고답하기]

문제 설명

As we all know, we live inside the matrix that is divided into N rows and N columns. An integer is written into each one of the NxN cells of the matrix.

In order to leave the matrix, we must find the most beautiful square (square-shaped sub-matrix) contained in the matrix.

If we denote by A the sum of all integers on the main diagonal of some square, and by B the sum of the other diagonal, then the beauty of that square is A - B.

Note: The main diagonal of a square is the diagonal that runs from the top left corner to the bottom right corner.

입력 설명

The first line of input contains the positive integer N (2 ≤ N ≤ 400), the size of the matrix.

The following N lines each contain N integers in the range [-1000, 1000], the elements of the matrix.

출력 설명

The only line of output must contain the maximum beauty of a square found in the matrix.

입력 예시 Copy

2 
1 -2
4 5

출력 예시 Copy

4

도움

Sample Input 2

3
1 2 3
4 5 6
7 8 9

Sample Output 2

0

Sample Input 3

3
-3 4 5
7 9 -2
1 0 -6

Sample Output 3

5

출처/분류