Advertisement
Guest User

Untitled

a guest
Dec 30th, 2020
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. //hey bhagwan AC kara de :''}
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define fo(i,n) for (int i = 0; i < n; ++i)
  6. #define tr(i,n) for(auto i=n.begin();i!=n.end();i++)
  7. #define w(t) while(t--)
  8. #define ll long long int
  9. #define pb push_back
  10. #define mp make_pair
  11. #define f first
  12. #define s second
  13. #define fst ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  14. #define all(x) (x).begin(), (x).end()
  15. const ll mod = 1000000007;
  16. int a[10001];
  17. int b[10001];
  18. int c[10001];
  19. int dp[10001][3];
  20. int find(int n, int curr, int id)
  21. {
  22.     // cout<<dp[n][id]<<" ";
  23.     if (n == 0)
  24.     {
  25.  
  26.         if (id == 0) {
  27.             int ans = curr + max(b[0], c[0]);
  28.             return ans;
  29.         }
  30.         if (id == 1) {
  31.             int ans = curr + max(a[0], c[0]);
  32.             return ans;
  33.         }
  34.         if (id == 2) {
  35.             int ans = curr + max(a[0], b[0]);
  36.             return ans;
  37.         }
  38.     }
  39.     if (dp[n][id] == -1)
  40.     {
  41.         if (id == 0){
  42.             dp[n][id] = max(find(n - 1, curr + b[n], 1), find(n - 1, curr + c[n], 2));
  43.             return dp[n][id];
  44.         }
  45.         else if (id == 1){
  46.             dp[n][id] = max(find(n - 1, curr + a[n], 0), find(n - 1, curr + c[n], 2));
  47.             return dp[n][id];
  48.         }
  49.         else{
  50.             dp[n][id] = max(find(n - 1, curr + a[n], 0), find(n - 1, curr + b[n], 1));
  51.             return dp[n][id];
  52.         }
  53.     }
  54.     else
  55.         return dp[n][id];
  56.  
  57. }
  58.  
  59. void solve()
  60. {
  61.     int n;
  62.     cin >> n;
  63.     memset(dp, -1, sizeof(dp));
  64.     fo(i, n)
  65.     cin >> a[i] >> b[i] >> c[i];
  66.  
  67.     int a1 = find(n - 1, 0, 0);
  68.     int a2 = find(n - 1, 0, 1);
  69.     int a3 = find(n - 1, 0, 2);
  70.     cout << max({a1, a2, a3});
  71. }
  72.  
  73. int main()
  74. {
  75.     fst;
  76.     solve();
  77. }
  78.  
  79.  
  80.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement