本質的には公式解説と同じです。

マスではなく、行と列を選ぶ問題だと思います。行と列を選んだ時のスコアは、「行に含まれる数の和 ＋ 列に含まれる数の和 － 行と列の交点の数」となります。前2項だけ考慮して解の候補を絞って良さそうに思えます。

実際、「行に含まれる数の和 ＋ 列に含まれる数の和」が大きい順に \(N+1\) 個を調べると、その中に必ず「行に含まれる数の和 ＋ 列に含まれる数の和 － 行と列の交点の数」が最大のものが含まれます。
このことは、\(N+1\) 個の中に行列の交点に数が書かれていないケースを必ず含むことと、行列の交点に数が書かれていないケースでの最大値は真の答えの下界になること、「行和＋列和≧行和＋列和－交点」となることから示せます。

「行に含まれる数の和 ＋ 列に含まれる数の和」が大きい順に調べることは、例えばプライオリティーキューなどを用いることで行えます。前処理と合わせて計算量は \(O(N \log N)\) になります。

擬似コード

// 行和と列和がそれぞれ降順になるよう、座標圧縮＋ソートされているものとする
priority_queue<array<Integer,3>>q; //(行和+列和, 行index, 列index)
rep(i,row_size)q.push({row_val[i]+col_val[0], i, 0});

ans=0;
while(q.size>0){
	v,i,j=q.pop();
	if(v<=ans)break;
	chmax(ans, v-cell_val[i,j]);
	if(j+1<col_size)q.push({row_val[i]+col_val[j+1], i, j+1});
}
print(ans)