Submission #1891426

---

Source Code Expand

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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 2e18 * 2;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int solve(int h, int w, vll b) {
	int i, j;
	vll sum1(h, vl(w + 1));
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			sum1[i][j + 1] = sum1[i][j] + b[i][j];
		}
	}
	vl left(w + 1, -INF), right(w + 1, -INF); //left[i]:右端がiの時のmax, right[i]: 左端がiの時のmax
	for (i = 0; i < w; i++) {
		ll res1 = -INF;
		for (j = i + 1; j <= w; j++) {
			vl sum2(h + 1);
			for (int k = 0; k < h; k++) {
				sum2[k + 1] = sum2[k] + (sum1[k][j] - sum1[k][i]);
			}
			ll M = -INF;
			ll res2 = -INF;
			for (int k = h; k > 0; k--) {
				M = max(M, sum2[k]);
				res2 = max(res2, M - sum2[k - 1]);
			}
			left[j] = max(left[j], res2);
			res1 = max(res1, res2);
		}
		right[i] = res1;
	}
	vl left2(w + 1), right2(w + 1);
	ll M = -INF;
	for (i = 1; i <= w; i++) {
		M = max(M, left[i]);
		left2[i] = M;
	}
	M = -inf;
	for (i = w - 1; i >= 0; i--) {
		M = max(M, right[i]);
		right2[i] = M;
	}
	ll res = -INF;
	for (i = 1; i < w; i++) {
		res = max(res, left2[i] + right2[i]);
	}
	return res;
}


int main() {
	int h, w, i, j;
	cin >> h >> w;
	vll b(h, vl(w));
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			cin >> b[i][j];
		}
	}
	ll ans1 = solve(h, w, b);
	vll b2(w, vl(h));
	for (i = 0; i < h; i++) {
		for (j = 0; j < w; j++) {
			b2[j][i] = b[i][j];
		}
	}
	ll ans2 = solve(w, h, b2);
	cout << max(ans1, ans2) << endl;
}

Submission Info

Judge Result