最大部分行列
与えられた の整数行列に対して、合計値が最大となる部分行列を求めます。
入力
最初の行には、行列の行数 r と列数 c が与えられます (1 ≤ r, c ≤ 50)。
次に続く r 行には、各行ごとに c 個の整数がスペース区切りで書かれており、これらは行列の要素を表します。各要素の値の範囲は です。
出力
部分行列の最大合計値となる整数を1つ出力してください。
例
入力 | 出力 |
|---|---|
3 5 | 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