【正经题解】方格取数

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
int a[1001][1001];
long long up[1005],down[1005],f[1005];
inline int read(){
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f*x;
}
int main(){
//	freopen("number.in","r",stdin);
//	freopen("number.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
		a[i][j]=read();
	f[1]=a[1][1];
	for(int i=2;i<=n;i++) f[i]=f[i-1]+a[i][1];
	for(int j=2;j<m;j++){
		memset(down,0,sizeof(down));
		memset(up,0,sizeof(up));
		down[1]=f[1]+a[1][j];up[n]=f[n]+a[n][j];
		for(int i=2;i<=n;i++) down[i]=max(f[i],down[i-1])+a[i][j];
		for(int i=n-1;i>=1;i--) up[i]=max(f[i],up[i+1])+a[i][j];
		for(int i=1;i<=n;i++) f[i]=max(down[i],up[i]);
	}
	f[1]+=a[1][m];
	for(int i=2;i<=n;i++) f[i]=max(f[i],f[i-1])+a[i][m];
	printf("%lld",f[n]);
	return 0;
}