Submission #1324468

#TimeUsernameProblemLanguageResultExecution timeMemory
1324468haithamcoderBikeparking (EGOI24_bikeparking)C++20
25 / 100
114 ms19208 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll LOG = 31;
const ll MOD = 1000000007;
const ll inf = 1e17;
const ll B = 2305843009213693951;


#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);


int main() {
    Algerian OI

    ll n;
    cin >> n;

    vector<ll> x(n), y(n);

    for (ll& c : x) cin >> c;
    for (ll& c : y) cin >> c;

    // deque<ll> dq;
    set<ll> s;
    for (ll i = 0; i < n; i++) s.insert(i);
    ll res = 0;
    
    for (ll i = n - 1; i >= 0; i--) {
        while (y[i]) {
            if (s.upper_bound(i) == s.begin()) {
                ll c = *(--s.end());
                ll take = min(x[c], y[i]);
                x[c] -= take;
                y[i] -= take;
                res -= take;
                if (!x[c]) s.erase(c);
            } else {
                auto it = --s.upper_bound(i);
                if (*it == i && it != s.begin()) --it;

                ll c = *it;
                ll take = min(x[c], y[i]);
                y[i] -= take;
                x[c] -= take;
                res += take * (c != i);
                if (!x[c]) s.erase(c);
            }
        }
    }

    cout << res << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...