Submission #617810

---

Source Code Expand

#include <bits/stdc++.h>
 
#define long long long
#define LOOPVAR_TYPE long
 
#define all(x) (x).begin(), (x).end()
#define sz(x) ((LOOPVAR_TYPE)(x).size())
#define foreach(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); it++)
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(LOOPVAR_TYPE i = (LOOPVAR_TYPE)(a); i < (LOOPVAR_TYPE)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
 
#define fir first
#define sec second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
 
const double EPS = 1e-9;
const double PI = acos(-1.0);
const long INF = 1070000000LL;
const long MOD = 1000000007LL;
 
using namespace std;
 
typedef istringstream iss;
typedef stringstream sst;
typedef pair<LOOPVAR_TYPE, LOOPVAR_TYPE> pi;
typedef vector<LOOPVAR_TYPE> vi;
 
int H, W;
int B[310][310];
long vs[310][310];
 
long solve(){
	rep(j, W){
		vs[0][j] = 0;
		rep(i, H){
			vs[i+1][j] = vs[i][j] + B[i][j];
		}
	}
	long sub[310][310];
	rep(u, H) rep(l, u, H){ // [u, l]
		long a[310];
		rep(j, W){
			a[j] = vs[l+1][j] - vs[u][j];
		}
		long sum[310] = {0};
		rep(j, W){
			sum[j+1] = sum[j] + a[j];
		}
		long ma = -INF*INF;
		long mi = 0;
		rep(j, W){
			ma = max(ma, sum[j+1] - mi);
			mi = min(mi, sum[j+1]);
		}
		sub[u][l] = ma;
	}
	long subMaxU[310];
	long subMaxD[310];
	rep(r, H){
		subMaxU[r] = subMaxD[r] = -INF*INF;
		rep(s, r+1){
			subMaxU[r] = max(subMaxU[r], sub[s][r]);
		}
		rep(s, r, H){
			subMaxD[r] = max(subMaxD[r], sub[r][s]);
		}
	}
	long maxU[310];
	long maxD[310];
	maxU[0] = subMaxU[0];
	rep(r, 1, H){
		maxU[r] = max(maxU[r-1], subMaxU[r]);
	}
	maxD[H-1] = subMaxD[H-1];
	for(int r = H-2; r >= 0; r--){
		maxD[r] = max(maxD[r+1], subMaxD[r]);
	}
	long res = -INF*INF;
	rep(r, H-1){
		res = max(res, maxU[r] + maxD[r+1]);
	}
	return res;
}
 
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
 
	cin >> H >> W;
	rep(i, H) rep(j, W) cin >> B[i][j];
	long ans = solve();
	int esc[310][310];
	rep(i, H) rep(j, W){
		esc[j][i] = B[i][j];
	}
	rep(i, H) rep(j, W){
		B[j][i] = esc[j][i];
	}
	swap(H, W);
	//rep(i,H){rep(j,W)cout<<B[i][j]<<" ";cout<<endl;}
	ans = max(ans, solve());
	cout << ans << endl;
}

Submission Info

Judge Result