Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n,m;
- int arr[2010][2010];
- int dp[2010][2010];
- int cal(int I,int J){
- // int ans = arr[I][J];
- if(dp[I][J] != -1)return dp[I][J];
- int a,b,c,d;
- a=b=c=d=0;
- if(I%2 == 0){
- if(I+1 < n && arr[I+1][J] != -1)a = cal(I+1,J);//+arr[I][J];
- if(J+1 < m && arr[I][J+1] != -1)b = cal(I,J+1);//+arr[I][J];
- }
- else{
- if(I+1 < n && arr[I+1][J] != -1)c = cal(I+1,J);//+arr[I][J];
- if(J-1 >= 0 && arr[I][J-1] != -1)d = cal(I,J-1);//+arr[I][J];
- }
- return dp[I][J] = arr[I][J] + max(max(a,b),max(c,d));
- }
- int main()
- {
- //freopen("input.txt","r",stdin);
- scanf("%d %d",&n,&m);
- for(int i = 0 ; i < n ; i ++){
- for(int j = 0 ; j < m ; j ++){
- scanf("%d",&arr[i][j]);
- dp[i][j] = -1;
- }
- }
- int ans = 0;
- for(int i = 0 ; i < n ; i ++){
- for(int j = 0 ; j < m ; j ++){
- ans = max(ans,cal(i,j));
- }
- }
- printf("%d",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement