| Concurso de programación ANIEI 2023 |
|---|
| Finished |
In the famous game The Legend of Pepe, Pepe is a forest elf who needs to save his kingdom from the evil Gadonorf. To achieve this, he needs the legendary artifact of the Tri-Power which is made of 3 magic triangles, the evil Gadonorf had the Triangle of muscles, the princess had the triangle of mathematics, and the hero had none, so he decided to create his own.
To create his triangle he needs to cut a triangle on a grid, the 'triangle' is made up of squares on the grid such that the top is only a square, and from the top to the bottom it has a number of squares in that row equal to the previous row plus 2, in such a way that they are connected in the shape of a triangle, generating 3 sides of equal length.
The power of a cut triangle is equal to the sum of the value in the cells, however, there are cells that are cursed with the ancient magic called 'rust', so a triangle that is 'rusted' will have 0 power.
Help Pepe know what is the greatest amount of power he can get for his magic triangle.
From the previous images, only the yellow triangle is valid.
The first line of input contains an integer $$$N$$$ ($$$ 1 \leq N \leq 1000 $$$) representing the length of one side of the grid. Each of the next $$$N$$$ contains $$$N$$$ integers separated by a space $$$v_i$$$ ($$$ 1 \leq v_i \leq 10^{10} $$$ where the $$$j$$$-th integer of the $$$i$$$-th line represents the power of the cell in position $$$(i,j)$$$ of the grid, or -1 if that cell is rusted.
Print a line with an integer that represents the greatest amount of power that a valid magic triangle can have on the grid.
2 18 18 10 4
18
3 -1 4 10 -1 -1 3 2 2 6
10
4 8 -1 -1 -1 -1 -1 2 4 -1 -1 -1 8 -1 9 1 10
10
1 -1
0
| Name |
|---|


