Nếu biết được vị trí tâm và độ dài của 2 dấu cộng, ta có thể dễ dàng kiểm tra xem 2 dấu cộng đó có giao nhau không trong ~O(1)~. Từ đó, ta có thuật toán ~O(N^6)~ (~15^6~ xấp xỉ ~1e7~ vừa đủ time limit) là duyệt qua cặp tất cả các cặp vị trí là tâm của 2 dấu cộng, sau đó, với mỗi dấu cộng, ta xét tất cả các độ dài có thể của dấu cộng đó và tính tổng bằng Prefix Sum 2D.

Code mẫu

/*
Patrol centre
*/
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for (ll i=m;i<=n;i++)
#define reb(i,m,n) for (ll i=m;i>=n;i--)
#define rv(i,vt) for (auto i:vt)
#define ii pair<ll,ll>
#define vi vector<ll>
#define F first
#define S second
#define pb push_back
#define sz(v) (int)v.size()
using namespace std;
const ll N=20+5,mod=1e9+7;
vector<ll> bl;
ll n,m,a[N][N],pre[N][N];
ll get (ll x, ll y, ll u, ll v){
    return (pre[u][v]-pre[x-1][v]-pre[u][y-1]+pre[x-1][y-1]);
}
ll cur (ll x, ll y, ll len){
    ll tmp=get(x-len+1,y,x+len-1,y);
    tmp+=get(x,y-len+1,x,y+len-1);
    tmp-=a[x][y];
    return tmp;
}
bool check (ll x, ll y, ll len){
    return (x-len+1>=1 && x+len-1<=n && y-len+1>=1 && y+len-1<=m);
}
bool intersect (ll x1, ll y1, ll len1, ll x2, ll y2, ll len2){
    if (y1==y2) return (abs(x2-x1)<=(len1+len2-2));
    if (x1==x2) return (abs(y2-y1)<=(len1+len2-2));
    if (len1>(abs(x2-x1)) && len2>(abs(y2-y1))) return 1;
    if (len2>(abs(x2-x1)) && len1>abs((y2-y1))) return 1;
    return 0;
}
void elixprep(){

}
void elix()
{
    cin>>n>>m;
    rep(i,1,n)
    rep(j,1,m) cin>>a[i][j],pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
    ll res=-1e18;
    rep(x,1,n)
    rep(y,1,m)
    rep(u,1,n)
    rep(v,1,m)
    rep(len1,1,20)
    rep(len2,1,20) if (check(x,y,len1) && check(u,v,len2) && !intersect(x,y,len1,u,v,len2)){
    res=max(res,cur(x,y,len1)+cur(u,v,len2));
    }
    cout<<res;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests=1;
    //cin>>tests;
    elixprep();
    while (tests--){
        elix();
        cout<<endl;
}
    cerr << "\n" << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
}
//listen to trap music. it won't help