Submission #9665

#	Time	Username	Problem	Language	Result	Execution time	Memory
9665		yukariko	On grid (kriii2_O)	C11	0 / 4	0 ms	1796 KiB

O

#include <stdlib.h>
#include <stdio.h>
#define MAX(a,b) (a>b?a:b);
int R,C;
int a[301][301];
int dp[301][301];
sum(x,y,p,q)
{
  int i,j,s=0;
  for(i=x;i<=p;i++)
  {
    for(j=y;j<=q;j++)
    {
      s+=a[i][j];
    }
  }
  return s;
}
f(x,y,s)
{
  int i,j,p,q,k,t,max=0;
  if(x==R||y==C)
  {
    if(x==R&&y==C)return s;
    return 0;
  }
  if(dp[x][y]>s*2)return dp[x][y];
  for(i=x;i<R;i++)
  {
    for(j=y;j<C;j++)
    {
      k=sum(x,y,i,j);
      t=f(i+1,j+1,s+k);
      max=max<t?t:max;
    }
  }
  return dp[x][y]=max;
}
main()
{
  scanf("%d%d",&R,&C);
  int i,j;
  for(i=0;i<R;i++)
  {
    for(j=0;j<C;j++)
    {
      scanf("%d",&a[i][j]);
    }
  }
  printf("%d",f(0,0,0));
}

• Subtask 1: 0 / 1
• Subtask 2: 0 / 3