D - おいしいたこ焼きの焼き方

Contest Duration: 2014-03-22(Sat) 12:00 - 2014-03-22(Sat) 14:00 (local time) (120 minutes) Back to Home

D - おいしいたこ焼きの焼き方 Editorial

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

高橋君のたこ焼き屋で使っているたこ焼き器は焼く場所によって美味しさの変わるクセの強いたこ焼き器です。
また、店員の力量によって一度に焼けるたこ焼きの数が違います。
高橋君はそれぞれの店員ができるだけ美味しくたこ焼きを焼けるようにしようと思いました。

たこ焼き器は $N×N$ の正方形をしています。
それぞれの場所ごとにたこ焼きの美味しさ $D_{ij}$ が決まっています。
それぞれの店員は一度に焼けるたこ焼きの上限 $P_k$ が決まっています。
また、一度に焼くたこ焼きは必ずたこ焼き器の長方形の部分になっていて、その中の全てを使わなければなりません。
それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を求めて下さい。
ただし、店員が焼き始める時はたこ焼き器が完全に空いていてどの場所でも使えるとします。

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $D_{11}$   $D_{12}$  ...  $D_{1N}$ 
 $D_{21}$   $D_{22}$  ...  $D_{2N}$ 
 $...$ 
 $D_{N1}$   $D_{N2}$  ...  $D_{NN}$ 
 $Q$ 
 $P_1$ 
 $P_2$ 
 $...$ 
 $P_Q$

１行目にたこ焼き器の一辺の大きさを表す整数 $N(1≦N≦50)$ が与えられます。
続く $N$ 行にたこ焼き器のそれぞれの場所で焼けるたこ焼きの美味しさを表す整数 $D_{ij}(1≦D_{ij}≦100)$ が与えられます。
次の行に店員の人数を表す整数 $Q$ ( $1≦Q≦N^2$ )が与えられます。
続く $Q$ 行にそれぞれの店員が焼けるたこ焼きの数を表す整数 $P_k(1≦P_k≦N^2)$ が与えられます。

出力

それぞれの店員について一度に焼けるたこ焼きの美味しさの合計の最大値を出力して下さい。
また、出力の末尾には改行を入れて下さい。

部分点

$1≦N≦5$ を満たすテストケース全てに正解すると、 $100$ 点満点のうち $50$ 点が与えられる。

入力例 1

出力例 1

3
9
14

１人目の店員は左上でたこ焼きを焼くと美味しさの合計が $3$ になります。
２人目の店員は左上の2×2の範囲でたこ焼きを焼くと美味しさの合計が $9$ になります。
３人目の店員はたこ焼き器全てを使えるので美味しさの合計が $14$ になります。

これは部分点に含まれる入力になります。

入力例 2

出力例 2

一番下の列の範囲1×3でたこ焼きを焼くと美味しさの合計が $27$ になります。
この店員はたこ焼きを４個焼くことができますが、３個しか焼かないほうが美味しさの合計が大きくなります。

これは部分点に含まれる入力になります。