Submission #319084

#	Time	Username	Problem	Language	Result	Execution time	Memory
319084		sofapuden	Schools (IZhO13_school)	C++14	100 / 100	279 ms	18140 KiB

school

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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

int main(){
	ll n, m, s; cin >> n >> m >> s;
	vector<array<ll,3>> v(n), ori;
	priority_queue<ll> PQ;
	vector<ll> 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;
	ll cn = m, cn2 = 0;
	ll 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--){
		ll x;
		if(PQ.empty())x = LONG_LONG_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: 100 / 100