Advertisement
sherry_ahmos

Untitled

Dec 6th, 2022
917
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. #define ll long long
  9. #define cy cout << "YES\n"
  10. #define cn cout << "NO\n"
  11. #define nl "\n"
  12. #define fi first
  13. #define se second
  14. #define MOD 1000000007
  15. #define all(v) v.begin(), v.end()
  16. #define sz(s) s.size()
  17. #define f0r(i, n) for (ll i = 0; i < n; i++)
  18. template <typename T = int>
  19. istream &operator>>(istream &in, vector<T> &v)
  20. {
  21.     for (auto &x : v)
  22.         in >> x;
  23.     return in;
  24. }
  25.  
  26. template <typename T = int>
  27. ostream &operator<<(ostream &out, const vector<T> &v)
  28. {
  29.     for (const T &x : v)
  30.         out << x << " ";
  31.     return out;
  32. }
  33.  
  34. void sherry()
  35. {
  36.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  37. #ifndef ONLINE_JUDGE
  38.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  39. #endif
  40. }
  41. ll n;
  42. vector<ll> v1, v2, dp;
  43. ll rec(ll i, ll prev, ll sum)
  44. {
  45.     if (i >= n)
  46.         return -1e9;
  47.     if (i == n - 1)
  48.         return 0;
  49.     ll &ret = dp[i];
  50.     if (~ret)
  51.         return dp[i];
  52.     if (prev == 1)
  53.     {
  54.         ret = max(rec(i + 1, 2, sum + v2[i]), rec(i + 1, -1, sum));
  55.     }
  56.     else if (prev == 2)
  57.     {
  58.         ret = max(rec(i + 1, 1, sum + v1[i]), rec(i + 1, -1, sum));
  59.     }
  60.     else
  61.     {
  62.         ret = max(rec(i + 1, 2, sum + v2[i]), rec(i + 1, 1, sum + v1[i]));
  63.     }
  64.     return ret;
  65. }
  66. void solve()
  67. {
  68.     cin >> n;
  69.     v1 = vector<ll>(n);
  70.     v2 = vector<ll>(n);
  71.     dp.assign(n + 5, -1);
  72.     for (int i = 0; i < n; i++)
  73.     {
  74.         cin >> v1[i];
  75.     }
  76.     for (int i = 0; i < n; i++)
  77.     {
  78.         cin >> v2[i];
  79.     }
  80.     cout << rec(0, -1, 0);
  81. }
  82. int main()
  83. {
  84.     sherry();
  85.     int t = 1;
  86.     // cin >> t;
  87.     while (t--)
  88.         solve();
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement