Submission #1009479

#TimeUsernameProblemLanguageResultExecution timeMemory
1009479bornagSchools (IZhO13_school)C++14
20 / 100
223 ms18108 KiB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 4e5+7;

pair<int, int> ppl[maxn];
int n, m, s;

int main(){
	cin >> n >> m >> s;
	
	for(int i = 0; i < n; i++){
		cin >> ppl[i].first >> ppl[i].second;
	}
	
	sort(ppl, ppl+n, greater<pair<int,int>>());
	
	int sol = 0;
	priority_queue<pair<int, int>> musicbest;
	priority_queue<pair<int, int>> remsports;
	set<int> rmsprts;
	
	for(int i = 0; i < m; i++){
		sol+=ppl[i].first;
		musicbest.push({ppl[i].second-ppl[i].first, i});
	}
	
	for(int i = m; i < n; i++){
		remsports.push({ppl[i].second, i});
		rmsprts.insert(i);
	}
	
	while(s--){
		while(!remsports.empty() and rmsprts.count(remsports.top().second)){
			remsports.pop();
		}
		
		if(remsports.empty() or (!musicbest.empty() and musicbest.top().first + ppl[*rmsprts.begin()].first > remsports.top().first)){
			sol += musicbest.top().first + ppl[*rmsprts.begin()].first;
			musicbest.pop();
			musicbest.push({ppl[*rmsprts.begin()].second - ppl[*rmsprts.begin()].first, *rmsprts.begin()});
			rmsprts.erase(rmsprts.begin());
			
		} else {
			sol += remsports.top().first;
			rmsprts.erase(remsports.top().second);
			remsports.pop();
		}
	}
	
	cout << sol << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...