問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
1 行目に整数 N, W, H が与えられます。
2 行目以降に N 行 N 列の整数の二次元配列 A が与えられます。
A の j 行目 k 列目を A_{j, k} (0 ≦ j ≦ N - 1, 0 ≦ k ≦ N - 1) と表すことにします。
横幅が W 、縦幅が H であるような長方形領域が取り得る領域内の整数の和の最大値を累積和を用いて求め、一行で出力してください。
・ 1 行目に整数 N, W, H が与えられます。
・ 2 行目以降に N 行 N 列の整数の二次元配列 A が与えられます。
N W H
A_{0, 0} A_{0, 1} ... A_{0, N - 1}
A_{1, 0} A_{1, 1} ... A_{1, N - 1}
...
A_{N - 1, 0} A_{N - 1, 1} ... A_{N - 1, N - 1}
横幅が W 、縦幅が H であるような長方形領域が取り得る領域内の整数の和の最大値を累積和を用いて求め、一行で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 100
・ 1 ≦ W, H ≦ N
・ 0 ≦ A_{i, j} ≦ 100 (0 ≦ i ≦ N - 1, 0 ≦ j ≦ N - 1)
3 1 1
1 2 3
4 5 6
7 8 9
9
3 3 1
1 2 3
4 5 6
7 8 9
24