Submission #278595

#	Time	Username	Problem	Language	Result	Execution time	Memory
278595		keta_tsimakuridze	Schools (IZhO13_school)	C++14	20 / 100	2094 ms	14456 KiB

school

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e5+5;
int a[N],b[N],n,n1,n2,k,curAns,Cc,c,i,ans;
pair<int,int>p[N];
set<pair<int,int> > cur,cur2,s2;
int main(){
	cin>>n>>n1>>n2;
	for(k=1;k<=n;k++){
		cin>>a[k]>>b[k];
		p[k]={a[k]-b[k],k};
		s2.insert({b[k],k});
	}
	sort(p+1,p+n+1);
	reverse(p+1,p+n+1);
	for(k=1;k<=n1;k++){
		 cur.insert({a[p[k].s],p[k].s});
		 curAns+=a[p[k].s];
		 s2.erase({b[p[k].s],p[k].s});
	}
	for(k=1;k<=n2;k++){
		c=(*(--s2.end())).first;
		i=(*(--s2.end())).second;
		s2.erase({c,i});
		cur2.insert({c,i});
		curAns+=b[i];
	}
	ans=curAns;
	for(k=n1+1;k<=n-n2;k++){
		c=(*cur.begin()).first;
		i=(*cur.begin()).second;
		if(c>a[p[k].second]) continue;
		else {
			int Cc=curAns;
			Cc-=c; Cc+=a[p[k].second];
			if(cur2.find({b[p[k].second],p[k].second})!=cur2.end()){
				
				Cc-=b[p[k].second];
				Cc+=(*(--s2.end())).first;
				if(Cc>curAns){
				    cur2.erase({b[p[k].second],p[k].second});
				    cur2.insert(*(--s2.end()));
					s2.erase(*(--s2.end()));
					curAns=Cc;
				}
			}
			else {
				if(Cc>curAns){
					curAns=Cc;
				}
			}
		}
	}
	cout<<curAns<<endl;
	
}

• Subtask 1: 20 / 100