Submission #89017

#TimeUsernameProblemLanguageResultExecution timeMemory
89017temoyanteladzeSchools (IZhO13_school)C++14
100 / 100
603 ms35324 KiB
//outsider
#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second
using namespace std;

int main() {
ll n,l,r;
ll ans=0;
vector<pair<ll,ll> >a;

    cin>>n>>l>>r;
    a.resize(n+1);
	for(ll i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;

	sort(a.begin()+1,a.end());
	reverse(a.begin()+1,a.end());

	multiset<ll>q;
    multiset <pair<ll,ll> > os1,os2;

	for(ll i=1;i<=l;i++)
	{
		ans+=a[i].x;
		q.insert(-a[i].y+a[i].x);
	}

	for(ll i=l+1;i<=n;i++)
	{
		os1.insert(a[i]);
		os2.insert({a[i].y,a[i].x});
	}

	for (ll i=r;i>0;i--){
		pair<ll,ll>fat,sad;
		fat=*os1.rbegin();
	    sad=*os2.rbegin();
	    ll f1=-*q.begin();

		if(f1+fat.x>sad.x)
		{
			ans+=f1+fat.x;
			q.erase(q.begin());
			ll p=fat.y-fat.x;
			q.insert(-p);
			os1.erase(os1.find(fat));
			os2.erase(os2.find({fat.y, fat.x}));

		}
		 else{
			ans +=sad.x;
			os2.erase(os2.find(sad));
			os1.erase(os1.find({sad.y, sad.x}));
		 }
	}
cout<< ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...