Submission #1058703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058703		Gray	Bikeparking (EGOI24_bikeparking)	C++17	100 / 100	32 ms	6996 KiB

Main

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bitset>
#include <cassert>
#include <cmath>
#include <functional>
#include <map>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define ull unsigned ll
#define ld long double
#define ln "\n"
#define ff first
#define ss second
using namespace std;
const ll inf=2e18;
const ll MOD = 1000000007;

void solve(){
	ll n; cin >> n;
	vector<ll> x(n), y(n);
	for (ll i=0; i<n; i++) cin >> x[i];
	for (ll i=0; i<n; i++) cin >> y[i];
	ll res=0, l=0;
	multiset<pair<ll, ll>> cand;
	for (ll i=0; i<n; i++){
		// cout << i << ": " << l << ":" << res << ln;
		while (l<i and y[i]){
			ll rem = min(y[i], x[l]);
			y[i]-=rem;
			x[l]-=rem;
			res+=rem;
			if (!x[l]) l++;
		}
		while (y[i] and !cand.empty()){
			auto cur=*cand.begin();
			cand.erase(cand.begin());
			y[cur.ss]+=cur.ff;
			x[cur.ss]+=cur.ff;
			ll rem = min(x[cur.ss], y[i]);
			x[cur.ss]-=rem;
			y[i]-=rem;
			res+=rem;
			if (x[cur.ss]){
				rem = min(x[cur.ss], y[cur.ss]);
				x[cur.ss]-=rem;
				y[cur.ss]-=rem;
				cand.insert({rem, cur.ss});
			}
		}
		if (y[i]){
			assert(l==i);
			ll rem = min(y[i], x[i]);
			y[i]-=rem;
			x[i]-=rem;
			cand.insert({rem, i});
			if (!x[i]) l++;
		}
	}
	// cout << res << ln;
	// for (ll i=0; i<n; i++) cout << x[i] << ' ';
	// cout << ln;
	// for (ll i=0; i<n; i++) cout << y[i] << ' ';
	// cout << ln;
	l=0;
	for (ll i=0; i<n; i++){
		while (l<n and y[i]){
			ll rem = min(y[i], x[l]);
			y[i]-=rem;
			x[l]-=rem;
			if (l>i) res-=rem;
			if (!x[l]) l++;
		}
	}
	cout << res << ln;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

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