Submission #3552061

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
#define inf 100000000000000007
using namespace std;
int n,m,a[303][303],b[303][303],c[303][303],ans;
int ans1[303],ans2[303],ans3[303],ans4[303];
int d[100100];
int ask(int x){
	int res=-inf,dp=-inf;
	for(int i=1;i<=x;i++)
	dp=max(dp+d[i],d[i]),
	res=max(res,dp);
	return res;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
    	cin>>a[i][j];
		b[i][j]=b[i-1][j]+a[i][j];
		c[i][j]=c[i][j-1]+a[i][j];
	}
	memset(ans1,0xcf,sizeof(ans1));
	memset(ans2,0xcf,sizeof(ans2));
	memset(ans3,0xcf,sizeof(ans3));
	memset(ans4,0xcf,sizeof(ans4));
    for(int i=1;i<=n;i++){
		for(int j=i;j>=1;j--){
			for(int k=1;k<=m;k++) 
				d[k]=b[i][k]-b[j-1][k];
			ans1[i]=max(ans1[i],ask(m));
		}
		ans1[i]=max(ans1[i],ans1[i-1]);
//		cout<<ans1[i]<<" ";
	}
//	puts("");
	for(int i=n;i>=1;i--){
		for(int j=i;j<=n;j++){
			for(int k=1;k<=m;k++)
				d[k]=b[j][k]-b[i-1][k];
			ans2[i]=max(ans2[i],ask(m));
		}
		ans2[i]=max(ans2[i],ans2[i+1]);
//		cout<<ans2[i]<<" ";
	}
//	puts("");
	for(int i=1;i<=m;i++){
		for(int j=i;j>=1;j--){
			for(int k=1;k<=n;k++)
				d[k]=c[k][i]-c[k][j-1];
			ans3[i]=max(ans3[i],ask(n));
		}
		ans3[i]=max(ans3[i],ans3[i-1]);
//		cout<<ans3[i]<<" ";
	}
//	puts("");
	for(int i=m;i>=1;i--){
		for(int j=i;j<=m;j++){
			for(int k=1;k<=n;k++)
				d[k]=c[k][j]-c[k][i-1];
			ans4[i]=max(ans4[i],ask(n));
		}
		ans4[i]=max(ans4[i],ans4[i+1]);
//		cout<<ans4[i]<<" ";
	}
//	puts("");
	ans=-inf;
	for(int i=1;i<n;i++)
	ans=max(ans,ans1[i]+ans2[i+1]);
	for(int i=1;i<m;i++)
	ans=max(ans,ans3[i]+ans4[i+1]);
	cout<<ans;
}
/*
4 4
5 2 -3 2
3 8 -3 -10
4 5 3 2
-5 -3 3 5
*/

Submission Info

Judge Result