# 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