记录编号	593236	评测结果	AAAAAAAAAA
题目名称	Partition	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	10.622 s
提交时间	2024-08-27 21:40:31	内存使用	102.41 MiB

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2003;
const long long int INF=20000000000000000;
int n,m;
long long int ans;
long long int a[MAXN][MAXN];
long long int dp1[MAXN][MAXN],dp2[MAXN][MAXN];
long long int pre_sum[MAXN][MAXN];
int main(){
    freopen("partition.in","r",stdin);
    freopen("partition.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			ans+=a[i][j];
	    }
	for(int i=n;i>=1;i--)
		for(int j=1;j<=m;j++)
			pre_sum[i][j]+=pre_sum[i+1][j]+a[i][j];
	for(int i=0;i<MAXN;i++){
		for(int j=0;j<=MAXN;j++){
			dp1[i][j]=-INF;
			dp2[i][j]=-INF;
		}
	}
	dp1[0][m+1]=dp2[0][1]=0; 
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m+1;j++){
			dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1]+pre_sum[i][j-1]);
		}
		for(int j=m+1;j>=1;j--){
			dp1[i][j]=max(dp1[i-1][j],dp1[i][j+1]+pre_sum[i][j]);
		}
	}
	ans+=dp1[n+1][1]+dp2[n+1][m+1]*2;
	printf("%lld",ans);
	return 0;
}