제출 #1151569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1151569		MuhammadSaram	Bikeparking (EGOI24_bikeparking)	C++20	100 / 100	232 ms	16848 KiB

Main

#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;
}

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