Advertisement
unknown_0711

vacation

Apr 23rd, 2023
849
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.63 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. int dp[100001][3], a[100001][3];
  4. // vector< vector<int> > dp(100001, vector<int> (3,-1);
  5. // vector< vector<int> > dp(100001, vector<int> (3);
  6. // same with a
  7. int n;
  8.  
  9. int solve(int i, int j) {
  10.  
  11.     if (i == n)return 0;
  12.     if (dp[i][j] != -1)return dp[i][j];
  13.     else return dp[i][j] = a[i][j] + max(solve(i + 1, (j + 1) % 3), solve(i + 1, (j + 2) % 3));
  14. }
  15.  
  16. int main() {
  17.     cin >> n;
  18.     for (int i = 0; i < n; i++)
  19.         for (int j = 0; j < 3; j++) {
  20.             cin >> a[i][j];
  21.             dp[i][j] = -1;
  22.         }
  23.     int ans = 0;
  24.     for (int j = 0; j < 3; j++)ans = max(ans , solve(0, j));
  25.     cout << ans << endl;
  26. }
  27.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement