Ray's Arrays

B. Ray's Arrays

No Submission Yet

Problem Statement

Ray loves arrays. In fact, he has \(n\) arrays, each of length \(n\), which he has put together to form an \(n \times n\) grid \(a\).

One day, he brought his grid to school to impress his friends and ended up forgetting it in the library. When he went back to get it the next day, he noticed that there have been some changes to it: some of the cells of the grid had coins in them! The cell in \(i\)-th row and \(j\)-th column had \(a_{i, j}\) coins in it. Needless to say, Ray was quite happy. However, the grid looked messy in his opinion, so he decided to make it look better.

His goal is to have all coins be in the same cell (it could be any cell). The way he plans to do it is by repeatedly applying the following operation: moving one coin from its cell to an adjacent cell (they have to share a side).

He doesn't have much time before his next class, so he needs to know the minimum number of operations he needs to apply to get all of the coins to be in the same cell. Can you help him? Note that the answer may not fit into a \(32\)-bit integer.

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(1 \leq n \leq 500\)
\(0 \leq a_{i, j} \leq 1000\)
Note that the first \(5\) testcases further guarentee that \(0 \leq a_{i, j} \leq 1 \)

Input Format

The first line has one integer \(n\)
The following \(n\) lines contain \(n\) integers each, the \(j\)-th element in the \(i\)-th line \(a_{i,j}\) is the number of coins in the \(j\)-th cell of the \(i\)-th row of the grid.

Output Format

Output one integer — the minimum number of operations Ray needs to apply to get all the coins from the grid in one cell.

Sample Input

1 0 1
0 0 0
0 0 1

Sample Output


Sample Explanation

The minimum number of operations is \(4\), which we can achieve by moving all coins to cell \((1, 3)\).

Credit: Eggag & CodeTiger

Contact Us
LIT Discord Server