Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define cy cout << "YES\n"
- #define cn cout << "NO\n"
- #define nl "\n"
- #define fi first
- #define se second
- #define MOD 1000000007
- #define all(v) v.begin(), v.end()
- #define sz(s) s.size()
- #define f0r(i, n) for (ll i = 0; i < n; i++)
- template <typename T = int>
- istream &operator>>(istream &in, vector<T> &v)
- {
- for (auto &x : v)
- in >> x;
- return in;
- }
- template <typename T = int>
- ostream &operator<<(ostream &out, const vector<T> &v)
- {
- for (const T &x : v)
- out << x << " ";
- return out;
- }
- void sherry()
- {
- ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
- #endif
- }
- ll n;
- vector<ll> v1, v2, dp;
- ll rec(ll i, ll prev, ll sum)
- {
- if (i >= n)
- return -1e9;
- if (i == n - 1)
- return 0;
- ll &ret = dp[i];
- if (~ret)
- return dp[i];
- if (prev == 1)
- {
- ret = max(rec(i + 1, 2, sum + v2[i]), rec(i + 1, -1, sum));
- }
- else if (prev == 2)
- {
- ret = max(rec(i + 1, 1, sum + v1[i]), rec(i + 1, -1, sum));
- }
- else
- {
- ret = max(rec(i + 1, 2, sum + v2[i]), rec(i + 1, 1, sum + v1[i]));
- }
- return ret;
- }
- void solve()
- {
- cin >> n;
- v1 = vector<ll>(n);
- v2 = vector<ll>(n);
- dp.assign(n + 5, -1);
- for (int i = 0; i < n; i++)
- {
- cin >> v1[i];
- }
- for (int i = 0; i < n; i++)
- {
- cin >> v2[i];
- }
- cout << rec(0, -1, 0);
- }
- int main()
- {
- sherry();
- int t = 1;
- // cin >> t;
- while (t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement