D - Souvenirs
Editorial
/
そのとき, 次のような進み方が最適です。
問題文担当者:square1001
Time Limit: 2 sec / Memory Limit: 256 MB
配点: $600$ 点
左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i, j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。
問題文
E869120とsquare1001は, $H \times W$ のマス目を移動して, お土産を買うことにしました。左上のマスがスタート地点, 右下のマスがゴール地点です。
上から$i$番目, 左から$j$番目には, $a_{i, j}$ 個のお土産が売られています。
そこで, 2人で協力してお土産をできるだけ多く集めることにしました。
しかし, 2人は最短経路で行かなければなりません。そうしないとTLEします。
そのとき, 買うことができるお土産の個数の最大値を求めなさい。
入力
入力は以下の形式で標準入力から与えられる。$H \ W$ $a_{1, 1} \ a_{1, 2} \ \cdots \ a_{1, W}$ $a_{2, 1} \ a_{2, 2} \ \cdots \ a_{2, W}$ $\vdots \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \vdots$ $a_{H, 1} \ a_{H, 2} \ \cdots \ a_{H, W}$
- $1$行目に, 整数$H$と$W$が与えられる。
- $2$行目から$H+1$行目には, $W$個の整数が空白区切りで与えられる。
出力
出力は以下の形式で標準出力に従うこと。
- 買うことのできるお土産の個数の最大値を1行に出力しなさい。
制約
- $1 \le H, W \le 200$
- $0 \le a_{i, j} \le 10^5$
小課題
小課題1 [50点]- $1 \le H \le 2$ を満たす。
- $1 \le H \le 3$ を満たす。
- $1 \le H, W \le 7$ を満たす。
- $1 \le H, W \le 30$ を満たす。
- 追加の制約はない。
入力例1
3 3 1 0 5 2 2 3 4 2 4
出力例1
21ここでは, 上から $i$ 番目, 左から $j$ 番目を $(i, j)$ とします。
そのとき, 次のような進み方が最適です。
- E869120は, $(1, 1) -> (1, 2) -> (1, 3) -> (2, 3) -> (3, 3)$ と進む。
- square1001は, $(1, 1) -> (2, 1) -> (3, 1) -> (3, 2) -> (3, 3)$ と進む。
入力例2
6 6 1 2 3 4 5 6 8 6 9 1 2 0 3 1 4 1 5 9 2 6 5 3 5 8 1 4 1 4 2 1 2 7 1 8 2 8
出力例2
97