fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define yes cout<<"YES\n";
  6. #define no cout<<"NO\n";
  7. const int N=3e5+7;
  8. ll T=1;
  9. ll h[N];
  10. ll n, oo = 1e18, k;
  11. ll a[N], b[N], c[N];
  12. ll dp[N][4];
  13. ll rec(ll i, int last)
  14. {
  15.     if(i > n)
  16.         return 0;
  17.  
  18.     ll &ret = dp[i][last];
  19.  
  20.     if(ret != -1)
  21.         return ret;
  22.  
  23.     ret = -oo;
  24.  
  25.     if(last == 1){
  26.         ret = max(ret, rec(i + 1, 2) + b[i]);
  27.         ret = max(ret, rec(i + 1, 3) + c[i]);
  28.     }
  29.     else if(last == 2){
  30.         ret = max(ret, rec(i + 1, 1) + a[i]);
  31.         ret = max(ret, rec(i + 1, 3) + c[i]);
  32.     }
  33.     else if(last == 3){
  34.         ret = max(ret, rec(i + 1, 1) + a[i]);
  35.         ret = max(ret, rec(i + 1, 2) + b[i]);
  36.     }
  37.     else{
  38.         ret = max(ret, rec(i + 1, 1) + a[i]);
  39.         ret = max(ret, rec(i + 1, 2) + b[i]);
  40.         ret = max(ret, rec(i + 1, 3) + c[i]);
  41.     }
  42.  
  43.     return ret;
  44. }
  45. void solve()
  46. {
  47.     memset(dp, -1, sizeof dp);
  48.  
  49.     cin >> n;
  50.     for(int i = 1; i <= n; i++)
  51.         cin >> a[i] >> b[i] >> c[i];
  52.  
  53.     cout << rec(1, 0);
  54. }
  55. int main()
  56. {
  57.     ios::sync_with_stdio(NULL);
  58.     cin.tie(0);
  59.     cout.tie(0);
  60.  
  61. //    freopen("","r", stdin);
  62. //    freopen("","w", stdout);
  63. //    cin>>T;
  64.     while(T--)
  65.         solve();
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 19740KB
comments (?)
stdin 
3
10 40 70
20 50 80
30 60 90
stdout 
210
https://ideone.com/pZdxHY
language:
C++ (gcc 8.3)
created:
1 day 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!