제출 #1335832

#제출 시각아이디문제언어결과실행 시간메모리
1335832YSH2020Bikeparking (EGOI24_bikeparking)C++20
9 / 100
183 ms23816 KiB
//greedily make the ppl at the back happi first
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
	int n; cin >> n;
	int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
	int b[n]; for (int i = 0; i < n; i++) cin >> b[i];
	set<pair<int,int>> ok;
	for (int i = 0; i < n; i++) if (a[i] > 0) ok.insert({i,b[i]});
	int ans=0;
	for (int i = 0; i < n; i++) {
		//make these ppl happy by allocating them to the first that they can go
		int cur = a[i];
		while (cur>0&&ok.size()) {
			auto itr = ok.lower_bound({i+1,0});
			if (itr == ok.end()) {
				//then too bad, we have to go neutral.
				itr = ok.lower_bound({i,0});
				if (itr == ok.end()) {
					//too bad lol you have to make someone cry now.
					break;
				}
				else {
					auto store = *itr;
					int take = min((*itr).second, cur);
					if (take==(*itr).second) {ok.erase(itr); cur-=take;}
					else {ok.erase(itr); ok.insert({store.first, store.second-take});cur-=take;}
				}
			}
			else {
				auto store = *itr;
				int take = min(cur,store.second);
				ans += take;
				if (store.second==take) {ok.erase(itr); cur -= take;}
				else {ok.erase(itr); ok.insert({store.first, store.second-take});cur-=take;
				}
			}
		}
	}
	for (auto i:ok) ans -= i.second;
	cout << ans;
	//now that they are all happy, we can make everyone else sad.
	
}
#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...