Submission #616361

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long ll;
ll x[300][300];
ll tmp[300][300],u[300],d[300];
ll inf=1e10;
ll ans=-inf;
int H,W;
int main(){
	cin>>H>>W;
	rep(i,H) rep(j,W) cin>>x[i][j];
	rep(i,H){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		u[i]=mx;
	}
	rep(i,H-1) chmax(u[i+1],u[i]);
	rep(i,W) rep(j,W) tmp[i][j]=0;
	for(int i=H-1;i>=0;i--){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		d[i]=mx;
	}
	for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
	rep(i,H-1) chmax(ans,u[i]+d[i+1]);
	rep(i,H) rep(j,W) tmp[i][j]=x[i][j];
	rep(i,H) rep(j,W) x[j][i]=tmp[i][j];
	swap(H,W);
	rep(i,300) rep(j,300) tmp[i][j]=0;
	rep(i,300) u[i]=d[i]=0;
	rep(i,H){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		u[i]=mx;
	}
	rep(i,H-1) chmax(u[i+1],u[i]);
	rep(i,W) rep(j,W) tmp[i][j]=0;
	for(int i=H-1;i>=0;i--){
		ll mx=-inf;
		rep(a,W){
			ll now=0;
			for(int b=a;b<W;b++){
				now+=x[i][b];
				tmp[a][b]=max(tmp[a][b]+now,now);
				chmax(mx,tmp[a][b]);
			}
		}
		d[i]=mx;
	}
	for(int i=H-2;i>=0;i--) chmax(d[i],d[i+1]);
	rep(i,H-1) chmax(ans,u[i]+d[i+1]);
	cout<<ans<<endl;
}

Submission Info

Judge Result