记录编号	593226	评测结果	AAAAAAAAAA
题目名称	Partition	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	3.588 s
提交时间	2024-08-27 20:02:07	内存使用	83.63 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long s[2005][2005],f[2005][2005],g[2005][2005];
int main(){
	freopen("partition.in","r",stdin);
	freopen("partition.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%lld",&s[i][j]);
	for(int i=n;i;i--)
		for(int j=1;j<=m;j++)
			s[i][j]+=s[i+1][j];
	long long S=0;
	for(int j=1;j<=m;j++)
		S+=s[1][j];
	memset(f,-0x3f,sizeof f);
	memset(g,-0x3f,sizeof g);
	f[0][1]=g[0][m+1]=0;
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m+1;j++)
			f[i][j]=max(f[i-1][j],f[i][j-1]+s[i][j-1]);
		for(int j=m+1;j;j--)
			g[i][j]=max(g[i-1][j],g[i][j+1]+s[i][j]);
	}
	cout<<S+2*f[n+1][m+1]+g[n+1][1];
	return 0;
}