ピクニック 2（paizaランク B 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

京子ちゃんは友人とピクニックに行く予定です。行く予定の公園の敷地は南北 n メートル、東西 m メートルの長方形の形をしており、 n \* m 個の 1 辺 1 メートル正方形の区画で分けることができます。公園は区画によって景色が異なり、それぞれ価値が決まっています。北から i 番目、西から j 番目の区画を (i, j) と表し、(i, j) の価値を a_i_j とします。また、ピクニックではレジャーシートを敷く予定です。レジャーシートは縦横 k メートルの大きさで、東西・南北にそれぞれ平行に敷きます。
京子ちゃんたちはもっとも景色のいい場所でご飯を食べたいので、レジャーシートを敷く k * k 個の区画の価値の合計が最大となるような場所に陣取ることにしました。このときの k * k 個の区画の価値の合計はいくつになるでしょうか？

入力される値

n m k
a_1_1 a_1_2 ... a_1_m
a_2_1 a_2_2 ... a_2_m
...
a_n_1 a_n_2 ... a_n_m

・ 1 行目に、公園の大きさを表す整数 n, m とレジャーシートの一辺の長さ k が与えられます。
・ 2 行目から n + 1 行目にかけて、区画 (i, j) の価値 a_i_j の各要素が与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: レジャーシートを敷く k * k 個の区画の価値の合計の最大値を出力してください。

また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 1 ≦ n, m ≦ 50
・ 1 ≦ k ≦ n
・ 1 ≦ k ≦ m
・ 1 ≦ k ≦ 10
・ 1 ≦ a_i_j ≦ 100

入力例1: 2 3 2
1 2 3
3 4 5

出力例1: 14

入力例2: 1 1 1
1

出力例2: 1

問題一覧へ戻る