AT_past202104_i 魚釣り

[problemUrl]: https://atcoder.jp/contests/past202104-open/tasks/past202104_i 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 $ 匹まで釣ってよいとき、釣った魚のおいしさの総和の最大値はいくつか？

入力は以下の形式で標準入力から与えられる。 > $ 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 $ としたときの答えを出力せよ。

### 注意 この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 入力はすべて整数 - $ 1\ \le\ H,W\ \le\ 100 $ - $ 1\ \le\ A_{i,j}\ \le\ 10^9 $ ### Sample Explanation 1 $ 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) $ と移動するとよいです。