제출 #1151569

#제출 시각아이디문제언어결과실행 시간메모리
1151569MuhammadSaramBikeparking (EGOI24_bikeparking)C++20
100 / 100
232 ms16848 KiB
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
#define dis(x,y) min(abs(x-y),2*n-abs(x-y))

int main()
{
	int n;
	cin>>n;
	int a[n],b[n];
	for (int i=0;i<n;i++)
		cin>>a[i];
	set<pair<int,int>> se;
	for (int i=0;i<n;i++)
	{
		cin>>b[i];
		if (b[i]) se.insert({i,b[i]});
	}
	int ans=0;
	for (int i=n-2;i>=0;i--)
	{
		while (a[i])
		{
			auto it=se.lower_bound({i+1,0});
			if (it==se.end())
				break;
			pair<int,int> p=*it;
			int mn=min(a[i],p.second);
			a[i]-=mn,ans+=mn;
			se.erase(p);p.second-=mn;
			if (p.second)
				se.insert(p);
		}
	}
	for (int i=0;i<n;i++)
	{
		while (a[i] && !se.empty())
		{
			auto it=se.lower_bound({i,0});
			if (it==se.end())
			{
				pair<int,int> p=*se.begin();
				int mn=min(a[i],p.second);
				a[i]-=mn,ans-=mn;
				se.erase(p);p.second-=mn;
				if (p.second) se.insert(p);
			}
			else
			{
				pair<int,int> p=*it;
				int mn=min(a[i],p.second);
				a[i]-=mn;
				se.erase(p);p.second-=mn;
				if (p.second)
					se.insert(p);
			}
		}
	}
	cout<<ans<<endl;
	
	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...