アルゴリズムとデータ構造

最大部分行列

与えられた の整数行列に対して、合計値が最大となる部分行列を求めます。

入力

最初の行には、行列の行数 r と列数 c が与えられます (1 ≤ r, c ≤ 50)。
次に続く r 行には、各行ごとに c 個の整数がスペース区切りで書かれており、これらは行列の要素を表します。各要素の値の範囲は です。

出力

部分行列の最大合計値となる整数を1つ出力してください。

例

入力
出力
3 5 1 2 -3 4 -6 -1 3 -100 4 0 0 1 -2 0 100
104

解説

1
2
-3
4
-6
-1
3
-100
4
0
0
1
-2
0
100
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue