/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は N 行 M 列のグリッドを持っています。グリッドの i 行 j 列目のマスには整数 A_{i,j} が書かれています。
高橋君は、このグリッドの中から長方形領域を 1 つ選び、その領域内に含まれる全てのマスの値の合計を求めます。ここで「長方形領域」とは、整数 r_1, r_2 （ 1 \le r_1 \le r_2 \le N ）と c_1, c_2 （ 1 \le c_1 \le c_2 \le M ）を選んだとき、行が r_1 以上 r_2 以下かつ列が c_1 以上 c_2 以下である全てのマスからなる領域のことを指します。
高橋君は、この合計が最大となるように長方形領域を選びたいと考えています。長方形領域は必ず 1 つ以上のマスを含むため、長方形領域を選ばずに合計を 0 とすることはできないことに注意してください。特に、全てのマスの値が負である場合でも、いずれかの長方形領域を選ばなければなりません。
高橋君が選べる長方形領域内の値の合計の最大値を求めてください。
制約
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- -10^4 \leq A_{i,j} \leq 10^4
- 入力はすべて整数である
入力
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- 1 行目には、グリッドの行数を表す整数 N と列数を表す整数 M が、スペース区切りで与えられる。
- 続く N 行のうち i 行目（ 1 \le i \le N ）には、グリッドの i 行目の各マスの値 A_{i,1}, A_{i,2}, \ldots, A_{i,M} がスペース区切りで与えられる。
出力
高橋君が選べる長方形領域内の値の合計の最大値を整数として 1 行で出力せよ。
入力例 1
3 3 1 -2 3 -4 5 6 7 -8 9
出力例 1
18
入力例 2
2 2 -5 -3 -1 -7
出力例 2
-1
入力例 3
5 4 2 1 -3 4 -1 3 2 -1 4 -2 1 3 -3 1 -4 2 1 2 3 -1
出力例 3
14
入力例 4
8 10 3 -1 2 -4 5 1 -3 2 4 -2 -2 4 1 3 -1 2 -5 3 1 0 1 -3 5 2 4 -1 3 -2 1 2 -4 2 -1 6 3 5 -2 4 -3 1 0 1 3 -2 4 2 1 -1 5 3 -1 -2 4 1 -3 6 2 3 -4 2 3 1 -5 2 1 -2 4 1 3 -1 -2 3 2 -1 3 1 -3 2 -1 4
出力例 4
77
入力例 5
1 1 -7
出力例 5
-7
Score : 400 pts
Problem Statement
Takahashi has a grid with N rows and M columns. The cell at row i and column j of the grid contains an integer A_{i,j}.
Takahashi will select one rectangular region from this grid and compute the sum of the values of all cells contained in that region. Here, a "rectangular region" refers to the region consisting of all cells whose row is between r_1 and r_2 (inclusive) and whose column is between c_1 and c_2 (inclusive), where r_1, r_2 (1 \le r_1 \le r_2 \le N) and c_1, c_2 (1 \le c_1 \le c_2 \le M) are chosen integers.
Takahashi wants to choose the rectangular region so that this sum is maximized. Note that a rectangular region must contain at least one cell, so it is not possible to choose no rectangular region and have a sum of 0. In particular, even if all cell values are negative, he must still choose some rectangular region.
Find the maximum possible sum of values within a rectangular region that Takahashi can choose.
Constraints
- 1 \leq N \leq 500
- 1 \leq M \leq 500
- -10^4 \leq A_{i,j} \leq 10^4
- All input values are integers
Input
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- The first line contains an integer N representing the number of rows and an integer M representing the number of columns of the grid, separated by a space.
- The following N lines each describe a row of the grid. The i-th of these lines (1 \le i \le N) contains the values A_{i,1}, A_{i,2}, \ldots, A_{i,M} of the cells in row i of the grid, separated by spaces.
Output
Print the maximum possible sum of values within a rectangular region that Takahashi can choose, as an integer on a single line.
Sample Input 1
3 3 1 -2 3 -4 5 6 7 -8 9
Sample Output 1
18
Sample Input 2
2 2 -5 -3 -1 -7
Sample Output 2
-1
Sample Input 3
5 4 2 1 -3 4 -1 3 2 -1 4 -2 1 3 -3 1 -4 2 1 2 3 -1
Sample Output 3
14
Sample Input 4
8 10 3 -1 2 -4 5 1 -3 2 4 -2 -2 4 1 3 -1 2 -5 3 1 0 1 -3 5 2 4 -1 3 -2 1 2 -4 2 -1 6 3 5 -2 4 -3 1 0 1 3 -2 4 2 1 -1 5 3 -1 -2 4 1 -3 6 2 3 -4 2 3 1 -5 2 1 -2 4 1 3 -1 -2 3 2 -1 3 1 -3 2 -1 4
Sample Output 4
77
Sample Input 5
1 1 -7
Sample Output 5
-7