Josif_tepe

Untitled

Oct 23rd, 2025
483
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.94 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <cstring>
  6. #include <map>
  7. using namespace std;
  8. typedef long long ll;
  9. const int maxn = 1e5 + 10;
  10. int n;
  11. int a[maxn][3];
  12. int dp[maxn][3];
  13. int rec(int at, int prev_activity) {
  14.     if(at >= n) {
  15.         return 0;
  16.     }
  17.     if(dp[at][prev_activity] != -1) {
  18.         return dp[at][prev_activity];
  19.     }
  20.    
  21.     int res = 0;
  22.    
  23.     for(int i = 0; i < 3; i++) {
  24.         if(i != prev_activity) {
  25.             res = max(res, rec(at + 1, i) + a[at][i]);
  26.         }
  27.     }
  28.    
  29.     dp[at][prev_activity] = res;
  30.     return res;
  31. }
  32. int main() {
  33.     memset(dp, -1, sizeof dp);
  34.    
  35.     cin >> n;
  36.     for(int i = 0; i < n; i++) {
  37.         cin >> a[i][0] >> a[i][1] >> a[i][2];
  38.     }
  39.    
  40.     int res = 0;
  41.     for(int i = 0; i < 3; i++) {
  42.         res = max(res, rec(1, i) + a[0][i]);
  43.     }
  44.    
  45.     cout << res << endl;
  46.    
  47.    
  48.     return 0;
  49. }
  50.  
Advertisement
Add Comment
Please, Sign In to add comment