Guest User

Untitled

a guest
Jul 22nd, 2012
317
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.59 KB | None | 0 0
  1. int n,m;
  2. int dp[1010][1010][3];
  3. int a[1010][1010];
  4. int was[1010][1010][3];
  5. int r(int x, int y, int from)
  6. {
  7.     if ((x==n-1) && (y==m-1))
  8.         return a[x][y];
  9.     if (was[x][y][from])
  10.         return dp[x][y][from];
  11.     was[x][y][from]=1;
  12.     int res=-1000000000;
  13.     if (x<n-1)
  14.         res=max(res,a[x][y]+r(x+1,y,0));
  15.     if ((y<m-1) && (from!=2))
  16.         res=max(res,a[x][y]+r(x,y+1,1));
  17.     if ((y>=0) && (from!=1))
  18.         res=max(res,a[x][y]+r(x,y-1,2));
  19.     return dp[x][y][from]=res;
  20. }
  21. int main()
  22. {
  23.     scanf("%d%d",&n,&m);
  24.     FOR(i,0,n)
  25.         FOR(j,0,m)
  26.             scanf("%d",&a[i][j]);
  27.     int res=r(0,0,0);
  28.     cout<<res<<endl;
  29.     return 0;
  30. }
Advertisement
Add Comment
Please, Sign In to add comment