제출 #1009479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009479		bornag	학교 설립 (IZhO13_school)	C++14	20 / 100	223 ms	18108 KiB

school

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

• Subtask 1: 20 / 100