Advertisement
luanaamorim

Untitled

Apr 11th, 2021
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.13 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 (3000*3000*105)
  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[3][MAX][MAX], vis[MAX][MAX];
  23.  
  24. int e(int a, int b)
  25. {
  26. return (a>=0 && b>=0 && a<n && b<m);
  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. if (e(a, b+1) && d != 1) ans = max(ans, f(0, a, b+1) + tab[a][b+1]);
  36. if (e(a, b-1) && d != 0) ans = max(ans, f(1, a, b-1) + tab[a][b-1]);
  37. if (e(a+1, b)) ans = max(ans, f(2, a+1, b) + tab[a+1][b]);
  38.  
  39. return dp[d][a][b] = ans;
  40. }
  41.  
  42. int main()
  43. {_
  44. cin >> n >> m;
  45. memset(dp, -1, sizeof(dp));
  46. for (int i = 0; i < n; i++)
  47. for (int j = 0; j < m; j++)
  48. cin >> tab[i][j];
  49.  
  50. cout << f(0, 0, 0) + tab[0][0] << endl;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement