Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Diagonal Sum

By Sherlock221b · Limits 1s, 512 MB

Given an N*N size matrix, you have to re-arrange the elements of the matrix in such a way that the difference between the summation of the elements of the main diagonal and the summation of the elements of the seconday diagonal is as large as possible. You can swap between any two elements of the matrix to re-arrange the matrix.

The main diagonal of a matrix consists of those elements that lie on the diagonal that runs from top left to bottom right. And the secondary diagonal of a matrix consists of those elements that lie on the diagonal that runs from top right to bottom left.

Input

In the first line of input, there will be a number N (3 ≤ N ≤ 100) as described above. Then there will be N integers in each of the next N lines denoting the matrix. The elements of the matrix will lie in the range [-106,106]. In other words, the absolute value of each element of the matrix will not exceed 106.

Output

In a single line, print the maximum possible difference between the summation of the elements of the main diagonal and the summation of the elements of the secondary diagonal after re-arranging.

Sample

InputOutput
3
-11 5 8 
2 6 17
4 -3 2
39

Explanation of first test case:

We can re-arrange the matrix to:

 17   5 -11
  2   6   4
 -3   2   8

The difference is (17+6+8) - (-11+6-3) = 39, which is the maximum in this case.

Discussion

Statistics


89% Solution Ratio

ghazanfarEarliest, Dec '16

Circle.21Fastest, 0.0s

oneoff.njpVi3LIlOLightest, 131 kB

touhidurrrShortest, 119B

Submit

Login to submit

Editorial

If N is an odd number, the main diagonal and the secondary diagonal have an element in common (namel...

Toph uses cookies. By continuing you agree to our Cookie Policy.