/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
注意
この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
PAST島には、地図上で縦 H 行、横 W 列の区画に分かれた釣り堀があります。上から i 番目、左から j 番目の区画を (i,j) と表記します。区画 (i,j) にいる魚のおいしさは A_{i,j} です。
はじめ、あなたは区画 (1,1) にいます。これから、あなたは以下のルールで釣りをします。
- 今いる区画を (p,q) とする。
- 区画 (p,q) で、魚を 0 匹または 1 匹釣る。
- その後、以下のルールで移動する。
- (p,q) = (H,W) なら、釣りを終了する。
- そうでなければ、区画 (p+1,q) または (p,q+1) に移動する。
- ただし、 p=H のとき (p+1,q) への移動は許されない。
- さらに、 q=W のとき (p,q+1) への移動は許されない。
1 以上 H+W-1 以下の全ての整数 k について、以下の問題を解いてください。
- 魚を全体で k 匹まで釣ってよいとき、釣った魚のおいしさの総和の最大値はいくつか？
制約
- 入力はすべて整数
- 1 \le H,W \le 100
- 1 \le A_{i,j} \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
出力
H+W-1 行出力せよ。i 行目には k=i としたときの答えを出力せよ。
入力例 1
5 6 4 5 1 2 6 9 1 3 3 2 7 4 8 3 7 6 2 1 7 8 3 3 7 5 8 4 5 5 5 6
出力例 1
9 16 23 30 36 41 45 48 52 53
k=4 の場合、例えば、(3,1),(4,1),(4,2),(4,5) で魚を 1 匹ずつ釣るのが最適です。
このように釣りを行うためには、例えば (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4) \rightarrow (4,5) \rightarrow (5,5) \rightarrow (5,6) と移動するとよいです。
Score : 6 points
Warning
Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
In the PAST Island, there is a fishing pond, which is divided into H horizontal rows and W vertical columns of squares on the map. The deliciousness of a fish in Square (i, j) is A_{i,j}.
Initially, you are in Square (1, 1). Now, you will do fishing as follows:
- Let (p, q) be the square you are currently in.
- You catch zero or one fish in (p, q).
- Then, you move as follows:
- if (p, q) = (H, W), you end fishing;
- otherwise, move to Square (p+1, q) or Square (p, q+1). However,
- if p = H, you cannot move to Square (p+1, q);
- if q = W, you cannot move to Square (p, q+1).
For every integer k from 1 through H+W-1, solve the following problem:
- find the maximum possible total deliciousness of fish you catch when you are allowed to catch at most k fish in total.
Constraints
- All values in input are integers.
- 1 \le H,W \le 100
- 1 \le A_{i,j} \le 10^9
Input
Input is given from Standard Input in the following format:
H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
Output
Print H+W-1 lines. The i-th line should contain the answer for k=i.
Sample Input 1
5 6 4 5 1 2 6 9 1 3 3 2 7 4 8 3 7 6 2 1 7 8 3 3 7 5 8 4 5 5 5 6
Sample Output 1
9 16 23 30 36 41 45 48 52 53
For k=4, it is optimal to catch fish in, for example, (3,1),(4,1),(4,2),(4,5).
To catch fish in these squares, you can move as, for example, (1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (4,1) \rightarrow (4,2) \rightarrow (4,3) \rightarrow (4,4) \rightarrow (4,5) \rightarrow (5,5) \rightarrow (5,6).