Submission #7948738

---

Source Code Expand

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

#define REP(i,x,y) for(ll i=x; i<=y; i++)
#define BIT(t) (1ll << (t))
#define PER(i,y,x) for(ll i=y; i>=x; i--)
#define SIZE(v) ll(v.size())
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
typedef long long ll;

ll f(ll h,ll w,vvll& grid){
    REP(i,1,h){
        REP(j,1,w){
            grid[i][j] += grid[i][j-1];
        }
    }
    REP(j,1,w){
        REP(i,1,h){
            grid[i][j] += grid[i-1][j];
        }
    } 
    vvll b(h+1, vll(h+1));
    vll c(h+1, -1e18), d(h+1, -1e18);
    REP(i,0,h){
        REP(j,i+1,h){
            vll u(w+1);
            vll v(w+1);
            REP(k,0,w){
                u[k] = grid[j][k] - grid[i][k];
            }
            v[0] = u[0];
            REP(k,1,w){
                v[k] = min(v[k-1], u[k]);
            }
            ll ans = -1e18;
            REP(k,1,w){
                ans = max(ans, u[k] - v[k-1]);
            }
            b[i][j] = ans;
        }
    }
    c[0] = -1e17; d[h] = -1e17;
    REP(i,1,h){
        REP(j,0,i-1){
            c[i] = max(c[i], b[j][i]);
        }
    }
    PER(i,h-1,0){
        PER(j,h,i+1){
            d[i] = max(d[i], b[i][j]);
        }
    }
    ll ans = -1e17;
    REP(i,1,h){
        REP(j,i,h){
            ans = max(ans, c[i] + d[j]);
            //cout << i << " " << j << " " << c[i] + d[j] << endl;
        }
    }
    return ans;
}

int main(){
    ll h,w;
    cin >> h >> w;
    vvll grid1(h+1, vll(w+1)), grid2(w+1, vll(h+1));
    REP(i,1,h){
        REP(j,1,w){
            cin >> grid1[i][j];
            grid2[j][i] = grid1[i][j];
        }
    }
    ll ans1 = f(h,w,grid1);
    ll ans2 = f(w,h,grid2);
    cout << max(ans1, ans2) << endl;
}

Submission Info

Judge Result