fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 1e3 + 5;
  10. const ll inf = 9e18;
  11. int a[N][N], n;
  12. ll dp[N][N][2];
  13.  
  14. void nhap() {
  15.     cin >> n;
  16.     FOR(i, 1, n) FOR(j, 1, n) cin >> a[i][j];
  17. }
  18.  
  19. ll calc(ll x, ll y, bool type) {
  20.     if (x == n && y == n) return a[n][n];
  21.     if (dp[x][y][type] != -1) return dp[x][y][type];
  22.  
  23.     ll res = -inf;
  24.     if (!type && x < n && y > 1) res = max(res, a[x][y] + calc(x + 1, y - 1, type));
  25.     if (type && x > 1 && y < n) res = max(res, a[x][y] + calc(x - 1, y + 1, type));
  26.     if (x < n) res = max(res, a[x][y] + max(calc(x + 1, y, 0), calc(x + 1, y, 1)));
  27.     if (y < n) res = max(res, a[x][y] + max(calc(x, y + 1, 0), calc(x, y + 1, 1)));
  28.  
  29.     return dp[x][y][type] = res;
  30. }
  31.  
  32. void giai() {
  33.     memset(dp, -1, sizeof dp);
  34.     cout << max(calc(1, 1, 0), calc(1, 1, 1));
  35. }
  36.  
  37. int main() {
  38.     ios_base::sync_with_stdio(0);
  39.     cin.tie(0); cout.tie(0);
  40.  
  41.     #define name "test"
  42.  
  43.     if (fopen(name".inp", "r")) {
  44.         freopen(name".inp", "r", stdin);
  45.         freopen(name".out", "w", stdout);
  46.     }
  47.  
  48.     nhap();
  49.     giai();
  50.  
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 19304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-9000000000000000000
https://ideone.com/p55b9k
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!