Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int n,m;
- int dp[1010][1010][3];
- int a[1010][1010];
- int was[1010][1010][3];
- int r(int x, int y, int from)
- {
- if ((x==n-1) && (y==m-1))
- return a[x][y];
- if (was[x][y][from])
- return dp[x][y][from];
- was[x][y][from]=1;
- int res=-1000000000;
- if (x<n-1)
- res=max(res,a[x][y]+r(x+1,y,0));
- if ((y<m-1) && (from!=2))
- res=max(res,a[x][y]+r(x,y+1,1));
- if ((y>=0) && (from!=1))
- res=max(res,a[x][y]+r(x,y-1,2));
- return dp[x][y][from]=res;
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- FOR(i,0,n)
- FOR(j,0,m)
- scanf("%d",&a[i][j]);
- int res=r(0,0,0);
- cout<<res<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment