Submission #242639

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
242639	2020-06-28T12:47:38 Z	kshitij_sodani	Schools (IZhO13_school)	C++17	100 / 100	537 ms	36440 KB

school

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,m,s;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>s;
	vector<pair<llo,llo>> kk;
	for(llo i=0;i<n;i++){
		llo aa,bb;
		cin>>aa>>bb;
		kk.pb({aa,bb});
	}
	sort(kk.begin(),kk.end());
	llo su=0;
	reverse(kk.begin(),kk.end());
	set<pair<llo,llo>> ss;
	set<pair<llo,llo>> tt;
	set<pair<llo,llo>> mm;
	for(llo i=0;i<n;i++){
		if(i<m){
			su+=kk[i].a;
			ss.insert({kk[i].a-kk[i].b,i});
		}		
		else{
			tt.insert({-kk[i].b,i});
			mm.insert({-kk[i].a,i});
		}
	}
	if(m==n){
		cout<<su<<endl;
		return 0;
	}
	for(llo i=0;i<s;i++){
		llo x=-(*tt.begin()).a;
		llo y=-(*ss.begin()).a-(*mm.begin()).a;
		if(y>x){
			su+=y;
			ss.erase(ss.begin());
			pair<llo,llo> no=*(mm.begin());
			mm.erase(mm.begin());
			tt.erase({-kk[no.b].b,no.b});
			ss.insert({kk[no.b].a-kk[no.b].b,no.b});
		}
		else{
			pair<llo,llo> no=*(tt.begin());
			mm.erase({-kk[no.b].a,no.b});
			tt.erase(tt.begin());
			su+=x;
		}
	}
	cout<<su<<endl;

	






	
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	8 ms	896 KB	Output is correct
8	Correct	7 ms	640 KB	Output is correct
9	Correct	7 ms	768 KB	Output is correct
10	Correct	7 ms	768 KB	Output is correct
11	Correct	9 ms	1024 KB	Output is correct
12	Correct	9 ms	1024 KB	Output is correct
13	Correct	30 ms	3440 KB	Output is correct
14	Correct	131 ms	10856 KB	Output is correct
15	Correct	290 ms	22760 KB	Output is correct
16	Correct	455 ms	24268 KB	Output is correct
17	Correct	332 ms	26056 KB	Output is correct
18	Correct	318 ms	28384 KB	Output is correct
19	Correct	447 ms	31200 KB	Output is correct
20	Correct	537 ms	36440 KB	Output is correct