http://acm.pku.edu.cn/JudgeOnline/problem?id=1157
Код:
#include<stdio.h>
int main()
{
int f,v;
int i,j,max;
int a[200][200];
long w[200][200];
w[0][0]=0;
scanf("%d%d",&f,&v);
for(i=1;i<=f;i++)
for(j=1;j<=v;j++) scanf("%d",&a[i][j]);
for(i=1;i<=v;i++) w[1][i]=a[1][i];
for(i=2;i<=f;i++)
{
w[i][i-1]=-2500;
for(j=i;j<=v-f+i;j++)
{
w[i][j]=-2500;
if (w[i][j-1]-a[i][j-1]+a[i][j]>w[i][j]) w[i][j]=w[i][j-1]+a[i][j]-a[i][j-1];
if (w[i-1][j-1]+a[i][j]>w[i][j]) w[i][j]=w[i-1][j-1]+a[i][j];
}
}
max=-2500;
for(j=f;j<=v;j++)
if(w[f][j]>max) max=w[f][j];
printf("%ld\n",max);
return 0;
}