Submission #1340755

#TimeUsernameProblemLanguageResultExecution timeMemory
1340755goulthenBikeparking (EGOI24_bikeparking)C++20
0 / 100
98 ms23916 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()

const int MAXN = 3e5+10;
const int INF = 1e18+10;
const int MOD = 1e9+7;
int a[MAXN], b[MAXN];

void solve() {
    int n; cin >> n;
    rep(i,1,n) cin >> a[i];
    rep(i,1,n) cin >> b[i];

    set<pii> st;
    int sum = 0;
    rep(i,1,n) {
        if(a[i] > 0) {
            st.insert({i,a[i]});
        }
        sum += a[i];
    }
    int ans = 0;
    rep(i,1,n) {
        while(b[i]>0) {
            auto it = st.upper_bound({i,-1});

            if(it==st.begin()) break;
            it--;
            
            auto [id, cnt] = *it;
            st.erase(it);

            if(cnt > b[i]) {
                st.insert({id,cnt-b[i]});
                ans += b[i];
                sum -= b[i];
                a[i] -= b[i];
                b[i] = 0;
            } else {
                b[i] -= cnt;
                sum -= cnt;
                ans += cnt;
                a[i] = 0;
            }
        }
    }
    rep(i,1,n) {
        sum -= min(a[i], b[i]);
    }

    cout << ans-sum << endl;
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
    int tt = 1;
    //cin >> tt;

    while (tt--) solve();
    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...