fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4.  
  5.  
  6. const int mx = 1e5 + 10;
  7.  
  8. int a[mx], b[mx], c[mx], n;
  9. int dp[mx][4];
  10.  
  11. int solve(int i, int t)
  12. {
  13.     if (i >= n)
  14.         return 0;
  15.  
  16.     if (dp[i][t] != -1)
  17.         return dp[i][t];
  18.  
  19.     int x1 = 0, x2 = 0;
  20.  
  21.     if (t == 1)
  22.     {
  23.         x1 = b[i] + solve(i + 1, 2);
  24.         x2 = c[i] + solve(i + 1, 3);
  25.     }
  26.     else if (t == 2)
  27.     {
  28.         x1 = a[i] + solve(i + 1, 1);
  29.         x2 = c[i] + solve(i + 1, 3);
  30.     }
  31.     else if (t == 3)
  32.     {
  33.         x1 = a[i] + solve(i + 1, 1);
  34.         x2 = b[i] + solve(i + 1, 2);
  35.     }
  36.     return dp[i][t] = max(x1, x2);
  37. }
  38.  
  39. signed main()
  40. {
  41.  
  42.     int i, ans = 0;
  43.  
  44.     cin >> n;
  45.     int ans1 = 0, ans2 = 0, ans3 = 0;
  46.  
  47.      memset(dp, -1, sizeof(dp));
  48.  
  49.     for (i = 0; i < n; i++)
  50.         cin >> a[i] >> b[i] >> c[i];
  51.  
  52.     ans1 = a[0] + solve(1, 1);
  53.     ans2 = b[0] + solve(1, 2);
  54.     ans3 = c[0] + solve(1, 3);
  55.  
  56.     ans = max(ans1, max(ans2, ans3));
  57.  
  58.     cout << ans;
  59. }
  60.  
Success #stdin #stdout 0.01s 7060KB
comments (?)
stdin
copy 
3
10 40 70
20 50 80
30 60 90
stdout
copy 
210
https://ideone.com/RDkHVq
language:
C++14 (gcc 8.3)
created:
4 years 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!