Advertisement
luanaamorim

Untitled

Apr 11th, 2021
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <map>
  9. #include <cstring>
  10. #include <set>
  11. #define ll long long
  12. #define INF (3001*3001*100)
  13. #define MAX (int) 3100
  14. #define MOD 1000000007
  15. #define par pair<int, int>
  16. #define all(v) v.begin(), v.end()
  17. #define lsb(x) (x & -x)
  18. #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  19.  
  20. using namespace std;
  21.  
  22. int tab[MAX][MAX], n, m, dp[10][MAX][MAX], vis[MAX][MAX];
  23.  
  24. int e(int a, int b)
  25. {
  26.     return (a>=0 && b>=0 && a<n && b<m && !vis[a][b]);
  27. }
  28.  
  29. int f(int d, int a, int b)
  30. {
  31.     if (a == n-1 && b == m-1) return 0;
  32.     if (~dp[d][a][b]) return dp[d][a][b];
  33.     int ans = -INF;
  34.  
  35.     vis[a][b] = 1;
  36.     if (e(a, b+1)) ans = max(ans, f(1, a, b+1) + tab[a][b+1]);
  37.     if (e(a, b-1)) ans = max(ans, f(2, a, b-1) + tab[a][b-1]);
  38.     if (e(a+1, b)) ans = max(ans, f(3, a+1, b) + tab[a+1][b]);
  39.     vis[a][b] = 0;
  40.  
  41.     return dp[d][a][b] = ans;
  42. }
  43.  
  44. int main()
  45. {_
  46.     cin >> n >> m;
  47.     memset(dp, -1, sizeof(dp));
  48.     for (int i = 0; i < n; i++)
  49.         for (int j = 0; j < m; j++)
  50.             cin >> tab[i][j];
  51.  
  52.     cout << f(0, 0, 0) + tab[0][0] << endl;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement