バツ印を書くために必要な線分の本数の最小値は、以下の値と等しいです。

• マス \((i,j)\) にバツ印が付けられていてかつマス \((i-1,j-1)\) にバツ印が付けられていないような整数対 \((i,j)\) の個数と、マス \((k,l)\) にバツ印が付けられていてかつマス \((k-1,l+1)\) にバツ印が付けられていないような整数対 \((k,l)\) の個数の合計（ここで、マス \((i-1,j-1),(k-1,l+1)\) が存在しない場合にもそれらのマスにはバツ印が書かれていないと見做す）

故にこの問題は、以下のように表現することができます。

各マスに対して、バツ印を付けるか付けないかの \(2\) 状態を割り振る。マス \((i,j)\) にバツ印を付けるとスコアに \(A_{i,j}\) が加算され、付けないと何も加算されない。

そしてまた一方で、マス \((i,j)\) にバツ印が付けられていてかつマス \((i-1,j-1)\) にバツ印が付けられていないような整数対 \((i,j)\)、およびマス \((k,l)\) にバツ印が付けられていてかつマス \((k-1,l+1)\) にバツ印が付けられていないような整数対 \((k,l)\) が \(1\) つ存在するごとにそれぞれスコアから \(C\) が減算される。

得られるスコアを最大化せよ。

このままだと加算と減算が混ざっていて見通しが悪いので、以下のように加算のみに統一します。

各マスに対して、バツ印を付けるか付けないかの \(2\) 状態を割り振る。マス \((i,j)\) にバツ印を付けないとコストに \(A_{i,j}\) が加算され、付けると何も加算されない。

そしてまた一方で、マス \((i,j)\) にバツ印が付けられていてかつマス \((i-1,j-1)\) にバツ印が付けられていないような整数対 \((i,j)\)、およびマス \((k,l)\) にバツ印が付けられていてかつマス \((k-1,l+1)\) にバツ印が付けられていないような整数対 \((k,l)\) が \(1\) つ存在するごとにそれぞれコストに \(C\) が加算される。

\(A_{i,j}\) の総和からコストを引いた値を最大化せよ。転じて、合計コストを最小化せよ。

ここまで来るとかなり見通しがよいです。このコストを最小化する問題は、以下のように構築されるグラフにおける、始点、終点の \(2\) 頂点に対する最小カット問題に帰着させることが可能です。

1. 各頂点がグリッドの各マスに対応した、\(H \times W\) 頂点 \(0\) 辺のグラフを用意する。さらに、そのグラフにそれぞれ始点、終点となる \(2\) 頂点を追加する
2. 任意のマス \((i,j)\) に対し、以下の \(1\) 本の辺を張る。
   • 始点からマス \((i,j)\) への重み \(A_{i,j}\) の有向辺
3. マス \((i-1,j-1)\) が存在しないような任意のマス \((i,j)\) に対し、以下の \(1\) 本の辺を張る。
   • マス \((i,j)\) から終点への重み \(C\) の有向辺
4. マス \((i-1,j-1)\) が存在するような任意のマス \((i,j)\) に対し、以下の \(2\) 本の辺を張る。
   • マス \((i,j)\) から終点への重み \(0\) の有向辺
   • マス \((i,j)\) からマス \((i-1,j-1)\) への重み \(C\) の有向辺
5. マス \((i-1,j+1)\) が存在しないような任意のマス \((i,j)\) に対し、以下の \(1\) 本の辺を張る。
   • マス \((i,j)\) から終点への重み \(C\) の有向辺
6. マス \((i-1,j+1)\) が存在するような任意のマス \((i,j)\) に対し、以下の \(2\) 本の辺を張る。
   • マス \((i,j)\) から終点への重み \(0\) の有向辺
   • マス \((i,j)\) からマス \((i-1,j+1)\) への重み \(C\) の有向辺

これをそのままコードに移しましょう。

計算量は Dinic 法を用いると \(O(HW \sqrt{HW})\) となります

計算量の解析に誤りがありました。 グラフの頂点数、辺数を \(V, E\) としたとき Dinic 法の計算量は \(O(EV^2)\) となるため、\(O(H^3W^3)\) となります。または、\(C\) や \(A_{i,j}\) の値がすべて \(K\) 以下であるとしたとき、\(O(KHW \sqrt{HW})\) となります。 これで通ることが証明できる十分小さい制約で出題すべきでした。申し訳ございません。

C++ の場合、atcoder library を利用すると非常に便利です。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;
using namespace atcoder;

#define rep(i, j, n) for(int i = int(j); i < int(n); i++)

using ll = long long;

int main(){
    int H,W,C; cin >> H >> W >> C;
    mf_graph<ll> graph(H*W+2);
    vector<vector<int>> A(H,vector<int>(W));
    rep(i,0,H){
        rep(j,0,W) cin >> A[i][j];
    }
    int sz = H*W;
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            graph.add_edge(sz,now,A[i][j]);
        }
    }
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            if(0 < i && 0 < j){
                int next = (i-1)*W+(j-1);
                graph.add_edge(now,sz+1,0);
                graph.add_edge(now,next,C);
            }
            else{
                graph.add_edge(now,sz+1,C);
            }
        }
    }
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            if(0 < i && j+1 < W){
                int next = (i-1)*W+(j+1);
                graph.add_edge(now,sz+1,0);
                graph.add_edge(now,next,C);
            }
            else{
                graph.add_edge(now,sz+1,C);
            }
        }
    }
    ll ans = 0;
    rep(i,0,H){
        rep(j,0,W) ans += A[i][j];
    }
    ans -= graph.flow(sz,sz+1);
    cout << ans << endl;
}