fork download 
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <stdlib.h>
  6. #include <ctime>
  7. #include <set>
  8. #include <map>
  9. #include <queue>
  10. #include <string>
  11. #include <math.h>
  12. #include <queue>
  13. #include <memory.h>
  14. #include <iostream>
  15. #include <stack>
  16. #include <complex>
  17. #include <list>
  18.  
  19. using namespace std;
  20.  
  21. void ASS(bool bb)
  22. {
  23.     if (!bb)
  24.     {
  25.         ++*(int*)0;
  26.     }
  27. }
  28.  
  29. #define FOR(i, x) for (int i = 0; i < (int)(x); ++i)
  30. #define CL(x) memset(x, 0, sizeof(x))
  31. #define CLX(x, y) memset(x, y, sizeof(x))
  32.  
  33. typedef vector<int> vi;
  34.  
  35. #pragma comment(linker, "/STACK:106777216")
  36.  
  37. const int inf = 1 << 30;
  38.  
  39. const int N = 107;
  40.  
  41. int n, m;
  42.  
  43. int a[N][N];
  44. int d[N][N][N][2];
  45.  
  46. int D(int x, int L, int R, int moveRight)
  47. {
  48.     if (x == n) {
  49.         if (L == R - 1 && R == m - 1)
  50.             return 0;
  51.         else
  52.             return -inf;
  53.     }
  54.     int &res = d[x][L][R][moveRight];
  55.     if (res != -1)
  56.         return res;
  57.     res = D(x + 1, L, R, 0) + a[x][L] + a[x][R]; // move both paths down
  58.     if (!moveRight) {
  59.         res = max(res, D(x, L, R, 1)); // stop moving left path, now move only right
  60.         if (L + 1 < R)
  61.             res = max(res, D(x, L + 1, R, 0) + a[x][L]); // move left path by one cell
  62.     } else {
  63.         if (R + 1 < m)
  64.             res = max(res, D(x, L, R + 1, 1) + a[x][R]); // move right path by one cell
  65.     }
  66.     return res;
  67. }
  68.  
  69. int main() {
  70.  
  71.     cin >> n >> m;
  72.     FOR(i, n) {
  73.         FOR(j, m) {
  74.             cin >> a[i][j];
  75.         }
  76.     }
  77.  
  78.     memset(d, 0xFF, sizeof(d));
  79.  
  80.     int res = D(0, 0, 1, 0);
  81.     cout << res << endl;
  82.  
  83.     return 0;
  84. }
Success #stdin #stdout 0.01s 12960KB
comments (?)
stdin 
Standard input is empty
stdout 
-1073741824
https://ideone.com/7z7opr
language:
C++ (gcc 8.3)
created:
10 years 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!