at3107

cherry

Oct 30th, 2020
568
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,j,k) for(int i=j;i<k;i++)
  4. int n,grid[102][102],dp[102][102];
  5.  
  6. int fun(int r1,int c1,int c2)
  7. {
  8.     int r2 = r1 + c1 - c2;
  9.     if (n == r1 || n == r2 || n == c1 || n == c2 ||
  10.                 grid[r1][c1] == -1 || grid[r2][c2] == -1)
  11.             return -9999999;
  12.     if (r1 == n-1 && c1 == n-1)
  13.             return grid[r1][c1];
  14.     if(dp[r1][c1][c2]!=INT_MIN) return dp[r1][c1][c2];
  15.     int ans=grid[r1][c1];
  16.     if (c1 != c2) ans += grid[r2][c2];
  17.             ans += Math.max(Math.max(dp(r1, c1+1, c2+1), dp(r1+1, c1, c2+1)),
  18.                             Math.max(dp(r1, c1+1, c2), dp(r1+1, c1, c2)));
  19.             memo[r1][c1][c2] = ans;
  20.             return ans;
  21. }
  22. int main()
  23. {
  24.     cin>>n;
  25.     rep(i,0,n) rep(j,0,n) cin>>grid[i][j];
  26.     rep(i,0,n) rep(j,0,n) rep(k,0,n) dp[i][j][k]=INT_MIN;
  27.     int ans=fun(0,0,0);
  28.     cout<<max(ans,0);
  29.     return 0;
  30. }
RAW Paste Data