Submission #319083

#	Time	Username	Problem	Language	Result	Execution time	Memory
319083		sofapuden	Schools (IZhO13_school)	C++14	75 / 100	272 ms	12920 KiB

school

#include <bits/stdc++.h>

using namespace std;

bool com(array<int,3> a, array<int,3> b){
	return a[1] > b[1];
}

int main(){
	int n, m, s; cin >> n >> m >> s;
	vector<array<int,3>> v(n), ori;
	priority_queue<int> PQ;
	vector<int> used(n,0);
	for(auto &x : v){cin >> x[0] >> x[1]; x[2] = 0;}
	sort(v.rbegin(),v.rend());
	for(int i = 0; i < n; ++i){
		v[i][2] = i;
	}
	ori = v;
	int cn = m, cn2 = 0;
	int ans = 0;
	for(int i = 0; i < m; ++i){
		ans+=v[i][0];
		used[i] = true;
		PQ.push({v[i][1]-v[i][0]});
	}
	sort(v.begin(),v.end(), com);
	while(s--){
		int x;
		if(PQ.empty())x = INT_MIN;
		else x = PQ.top();
		while(used[cn])cn++;
		while(used[v[cn2][2]])cn2++;
		if(x + ori[cn][0] > v[cn2][1]){
			PQ.pop();
			ans += x + ori[cn][0];
			used[cn] = true;
			PQ.push({ori[cn][1]-ori[cn][0]});
		}
		else{
			ans += v[cn2][1];
			used[v[cn2][2]] = true;
		}
	}
	cout << ans << "\n";
}
	

• Subtask 1: 75 / 100