407970: GYM102953 7 Maximum Plus Sign

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

7. Maximum Plus Signtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an $$$n$$$ by $$$n$$$ 2D grid consisting of $$$n^2$$$ integers. You're trying to find the "plus sign" in the grid with the maximum sum.

You define a "plus sign" to be any contiguous segment of rows (including at least one row), and any contiguous segment of columns (including at least one column). For example, the cells highlighted in blue in the image below are a plus sign:

Your task is to find the sum of the elements of the 2D grid in the plus sign with the maximum sum. For example, the plus sign shown above has a sum of elements of 15.

Note that a valid plus sign doesn't necessarily have to look like a plus sign if it fits the definition above, i.e. the entire grid (a rectangle) would be considered a valid plus sign, as well as a T-shape (if the plus sign included the top row).

Input

The first line of input contains a single positive integer $$$n$$$ $$$(4 <= n <= 400)$$$: the width and height of the 2D grid.

The next $$$n$$$ lines each contain $$$n$$$ space-separated positive integers: the grid. Each grid element will be between $$$-10^9$$$ and $$$10^9$$$, inclusive.

Output

Output a single integer, representing the sum of the elements on the plus sign with the maximum sum in the 2D grid, as defined above.

Scoring

Subtask 1 (15 points): $$$n <= 40$$$

Subtask 2 (27 points): no additional constraints

ExamplesInput
5
3 7 -9 8 2
1 -5 3 -4 1
-3 2 0 3 6
-1 -8 5 6 2
4 5 -1 -3 5
Output
34
Input
4
-9 -1 -3 -2
-4 -6 -8 -1
-1 -1 -3 -2
-10 -12 -4 -5
Output
-15

加入题单

上一题 下一题 算法标签: