P7626 [COCI 2011/2012 #1] MATRIX

Given an $N \times N$ matrix, find the square submatrix (i.e., with equal height and width) that has the maximum beauty value. Define the **beauty value** of a matrix as follows: let $A$ be the sum of the numbers on the **main diagonal** of this matrix, and let $B$ be the sum of the numbers on the other diagonal. Then the beauty value is $A - B$.

The first line contains a positive integer $N$. The next $N$ lines each contain $N$ integers, describing the matrix.

Output one integer on a single line, the maximum beauty value.

#### Constraints For $100\%$ of the testdata, $1 \le N \le 400$, and each matrix element $\in [-10^3,10^3]$. #### Notes The scoring of this problem follows the original COCI settings. The full score is $80$. This problem is translated from **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T2 MATRIX___. Translated by ChatGPT 5