G - Matrix Compressor
解説
/
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : {100} 点
問題文
あなたは H 行 W 列の行列を持っています。行列の i 行目、j 列目の成分は 1 桁の正整数 S_{i, j} です。
あなたは次の 2 種類の操作を好きな順序で、合計 H + W - 2 回行えます。
- 隣接する 2 行 (i, i + 1 行目) を選び、2 行の成分の総和の点数を得る。そして、2 行を圧縮する。すなわち、(存在すれば) i - 1 行目以前、i 行目と i + 1 行目の行ベクトルとしての和、(存在すれば) i + 2 行目以降、をこの順に縦に連結したものに行列全体を置き換える。この操作は、行列が 2 行以上である場合に行える。
- 隣接する 2 列 (j, j + 1 列目) を選び、2 列の成分の総和の点数を得る。そして、2 列を圧縮する。すなわち、(存在すれば) j - 1 列目以前、j 列目と j + 1 列目の列ベクトルとしての和、(存在すれば) j + 2 列目以降、をこの順に横に連結したものに行列全体を置き換える。この操作は、行列が 2 列以上である場合に行える。
獲得可能な合計点数の最大値を求めてください。
制約
- 入力は全て整数
- 1 \le H, W \le 3000
- 1 \le S_{i, j} \le 9
部分点
- 1 \leq H, W \leq 200 を満たすデータセットに正解した場合は 30 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
H W S_{1, 1}S_{1, 2}\ldots S_{1, W} S_{2, 1}S_{2, 2}\ldots S_{2, W} \vdots S_{H, 1}S_{H, 2}\ldots S_{H, W}
出力
獲得可能な合計点数の最大値を出力せよ。
入力例 1
3 3 314 159 265
出力例 1
130
順に、 2, 3 列目、2, 3 行目、1, 2 行目、1, 2 列目、と選ぶのが最適な方法の一つです。このとき、 30 + 28 + 36 + 36 = 130 点が得られます。行列は以下のように変化していきます。
$$ \begin{bmatrix} 3 & 1 & 4 \\ 1 & 5 & 9 \\ 2 & 6 & 5 \end{bmatrix} \to \begin{bmatrix} 3 & 5 \\ 1 & 14 \\ 2 & 11 \end{bmatrix} \to \begin{bmatrix} 3 & 5 \\ 3 & 25 \end{bmatrix} \to \begin{bmatrix} 6 & 30 \end{bmatrix} \to \begin{bmatrix} 36 \end{bmatrix} $$
入力例 2
10 8 82974679 74744362 34499984 86891758 56419363 76176864 78392791 71539599 44588446 71227999
出力例 2
4555