Submission #1229939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229939		gry3125	Bikeparking (EGOI24_bikeparking)	C++20	100 / 100	234 ms	21504 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define ll long long int
#define fi first
#define se second
using namespace std;

int main() {

    ll n, r = 0; cin >> n;
    multiset<ll> x; vector<ll> y(n), cnt(n);
    for (int i = 0; i < n; i++) {
    	ll xi; cin >> xi;
    	if (xi != 0) x.insert(i);
    	cnt[i] = xi;
    }
    for (int i = 0; i < n; i++) cin >> y[i];
    
    for (int i = 0; i < n; i++) {
    	while (y[i] > 0) {
    		auto it = x.lower_bound(i);
    		if (it == x.begin()) break;
    		auto val = *prev(it);
    		if (y[i] < cnt[val]) {
    			cnt[val] -= y[i];
    			r += y[i]; 
    			y[i] = 0;
    		} else {
    			x.erase(x.find(val));
    			y[i] -= cnt[val];
    			r += cnt[val];
    			cnt[val] = 0;
    		}
    	}
    }
    vector<ll> rx(n);
    for (auto p : x) {
    	rx[p] = cnt[p];
    }
    ll c = 0;
    for (int i = n-1; i >= 0; i--) {
    	if (c == n) continue;
    	while (y[i] > 0) {
    		while (c < n && rx[c] == 0) c++;
    		if (c == n) break;
    		if (y[i] <= rx[c]) {
    			if (i < c) r -= y[i];
    			if (i > c) r += y[i];
    			rx[c] -= y[i];
    			y[i] = 0;
    		} else {
    			if (i < c) r -= rx[c];
    			if (i > c) r += rx[c];
    			y[i] -= rx[c];
    			rx[c] = 0;
    		}
    	}
    }

    cout << r;
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 9 / 9
• Subtask 3: 19 / 19
• Subtask 4: 24 / 24
• Subtask 5: 32 / 32