Transmutation Diamonds

All submissions for this problem are available.
In the nation of Amestris, people use transmutation circles for Alchemy, but in different regions of the world people have come up with different methods to harness the power of Alchemy. In the nation of Creta, people use transmutation figures in the shape of a Diamond for Alchemy. Refer to the figure below to understand what a Diamond shape is. The Elric brothers come to Creta to learn this form of Alchemy. For this Alchemy, the energy from the earth is used to deconstruct and reconstruct. Now Edward is standing on a piece of land, which can be considered to be a grid of dimensions $N \times N$. For every block of land, the energy it provides in Alchemy is given as $E_{ij}$. It is also possible for some block to have negative energy, in which case it reduces the power of transmutation diamond. The power of transmutation from a diamond figure is the sum of the energies ( $E_{ij}$ ) of the blocks included in the transmutation diamond. Given that the diamond figure must lie inside the grid, find the maximum power that can be generated from any diamond transmutation figure. Note that you have to select at least one block. ![](https://codechef_shared.s3.amazonaws.com/download/HYC/External_contest_i... =500x500) The above figure shows the smallest three diamonds shapes that can be formed in the grid. ### Input:  The first line contains $T$, the number of test cases. Then the test cases follow.  For each test case, the first line contains $N$.  Then $N$ lines follow, each containing $N$ integers. The $j^{th}$ integer in the $i^{th}$ line is $E_{ij}$. ### Output: For each test case, output a single integer in a new line, denoting the maximum transmutation power of any diamond in the grid. ### Constraints  $1\leq T\leq 100$  $ 1 \leq N \leq 100$  $ E_{ij}  \leq 10^{9}$ ### Sample Input: ``` 3 1 5 2 1 1 1 1 3 10 5 50 26 1 10 0 6 45 ``` ### Sample Output: ``` 5 1 46 ```Author:  sachin_yadav 
Editorial  https://discuss.codechef.com/problems/MXPOWER 
Tags  dcod2019, precomputation, prefixsum, sachin_yadav, sachin_yadav 
Date Added:  23102019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 