fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define pub push_back
  7. #define pob pop_back
  8. #define mpa make_pair
  9. #define endl '\n'
  10. #define BIT(i) ((1 << i))
  11. const int maxn = 1010;
  12. int n;
  13. int a[maxn][maxn];
  14. int dp[maxn][maxn];
  15. int pre[maxn][maxn];
  16. int L[maxn][maxn];
  17. int R[maxn][maxn];
  18. int main()
  19. {
  20.     ios_base::sync_with_stdio(false);
  21.     cin.tie(0);
  22.     cout.tie(0);
  23.     #define code code
  24. //    freopen("code.INP","r",stdin);
  25. //    freopen("code.OUT","w",stdout);
  26.     cin >> n;
  27.     for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> a[i][j];
  28.     for(int s=2; s<=n*2; s++)
  29.     {
  30.         for(int i=1; i<=n; i++)
  31.         {
  32.             int j = s - i;
  33.             if(1 <= j && j <= n)
  34.             {
  35.                 pre[i][j] = pre[i - 1][j + 1] + a[i][j];
  36.             }
  37.         }
  38.     }
  39.     memset(L, -0x3f, sizeof L);
  40.     memset(R, -0x3f, sizeof R);
  41.     memset(dp, -0x3f, sizeof dp);
  42.     dp[1][1] = a[1][1];
  43.     for(int s=3; s<=n*2; s++)
  44.     {
  45.         for(int i=1; i<=n; i++)
  46.         {
  47.             int j = s - i;
  48.             if(1 <= j && j <= n)
  49.             {
  50.                 int val = max(dp[i - 1][j], dp[i][j - 1]);
  51.                 L[i][j] = max(L[i - 1][j + 1], val - pre[i - 1][j + 1]);
  52.             }
  53.         }
  54.         for(int i=n; i>=1; i--)
  55.         {
  56.             int j = s - i;
  57.             if(1 <= j && j <= n)
  58.             {
  59.                 int val = max(dp[i - 1][j], dp[i][j - 1]);
  60.                 R[i][j] = max(R[i + 1][j - 1], val + pre[i][j]);
  61.             }
  62.         }
  63.         for(int i=1; i<=n; i++)
  64.         {
  65.             int j = s - i;
  66.             if(1 <= j && j <= n)
  67.             {
  68.                 dp[i][j] = max(R[i][j] - pre[i - 1][j + 1], pre[i][j] + L[i][j]);
  69.             }
  70.         }
  71.     }
  72.     cout << dp[n][n];
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 19372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1044266559
https://ideone.com/uVa8du
language:
C++14 (clang 8.0)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!