A1218. [COCI-2011_2012-contest1]#2 MATRIX
编程题
普及/提高-
知识点
题目描述
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.
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 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.
输入输出样例
输入 #1
2 1 -2 4 5
输出 #1
4
输入 #2
3 1 2 3 4 5 6 7 8 9
输出 #2
0
输入 #3
3 -3 4 5 7 9 -2 1 0 -6
输出 #3
5