\(i\) 行目の成分の総和を \(R_i\)、\(j\) 列目の成分の総和を\(C_j\) とおくと、\(2\) 種類の操作は次のように言い換えられます。

• \(R\) の隣接する \(2\) 項 (\(i, i + 1\) 項目) を選び、\(R_i + R_{i + 1}\) 点を得る。そして、\(R\) の \(i - 1\) 項目以前、\(R_i + R_{i + 1}\)、\(R\) の \(i + 2\) 項目以降、をこの順に連結したものに \(R\) を置き換える。
• \(C\) の隣接する \(2\) 項 (\(j, j + 1\) 項目) を選び、\(C_j + C_{j + 1}\) 点を得る。そして、\(C\) の \(j - 1\) 項目以前、\(C_j + C_{j + 1}\)、\(C\) の \(j + 2\) 項目以降、をこの順に連結したものに \(C\) を置き換える。

各操作はそれぞれ \(R, C\) の片方にしか干渉しないため、それぞれで得られる点数を独立に最大化すればよいことがわかります。以下では \(R\) を対象とします。

\[f(l, r):=R_l, \ldots , R_{r - 1} についての答え\]

と定義します。各時点での \(R\) の各項は、最初の \(R\) における区間に対応していることから、最後の操作がどの \(2\) 区間に対して行われるのかを全通り考えることで、次が成立することがわかります。

\[f(l, r) = \max_{l +1 \leq i < r - 1} (f(l, i) + f(i, r)) + \sum_{l \leq i < r} R_i\]

この式に基づき、より小さい問題からはじめて答えを記録していくことで \(f(1, H + 1)\) を \(O(H^3)\) の計算量で求めることができます。これは区間 DP と呼ばれる処理です。以上の考え方により部分点が得られます。実装にあたっては適宜累積和を用いるとよいです。

さて、「最後の操作がどの \(2\) 区間に対して行われるのかを全通り考える」と述べましたが、実は考えるべき候補を絞ることができます。最後の操作がいずれも長さ \(2\) 以上の \(2\) 区間に対して行われる場合に注目します。長さ \(2\) 以上の区間ではすでに少なくとも \(1\) 回の操作が行われているので、さらにその直前の状態を考えることができます。全体で \(4\) 区間 \([l, i_1), [i_1, i_2), [i_2, i_3), [i_3, r)\) に分かれている状態です。この場合に得られる点数は

\[f(l, i_1) + f(i_1, i_2) + f(i_2, i_3) + f(i_3, r) + 2\sum_{l \leq j < i_1} R_i + 2\sum_{i_1 \leq j < i_2} R_i + 2\sum_{i_2 \leq j < i_3} R_i + 2\sum_{i_3 \leq j < r} R_i\]

となります。一方、左右いずれかの端の \(2\) 区間に対する操作を行い続ける場合に得られる点数は

\[f(l, i_1) + f(i_1, i_2) + f(i_2, i_3) + f(i_3, r) + \sum_{l \leq j < i_1} R_i + 2\sum_{i_1 \leq j < i_2} R_i + 3\sum_{i_2 \leq j < i_3} R_i + 3\sum_{i_3 \leq j < r} R_i\]

や

\[f(l, i_1) + f(i_1, i_2) + f(i_2, i_3) + f(i_3, r) + 3\sum_{l \leq j < i_1} R_i + 3\sum_{i_1 \leq j < i_2} R_i + 2\sum_{i_2 \leq j < i_3} R_i + \sum_{i_3 \leq j < r} R_i\]

となり、このどちらかの方が必ず得になります。つまり、最後の操作がいずれも長さ \(2\) 以上の \(2\) 区間に対して行われる場合が最適となることはありえません。したがって、

\[f(l, r) = \max (f(l, l + 1) + f(l + 1, r), f(l, r - 1) + f(r - 1, r)) + \sum_{l \leq i < r} R_i\]

でよいことになり、区間 DP の計算量を \(O(H^2)\) に落とせます。以上で満点が得られます。