Submission #676590

#	Time	Username	Problem	Language	Result	Execution time	Memory
676590		QwertyPi	Schools (IZhO13_school)	C++14	15 / 100	224 ms	17512 KiB

school

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct area{
	int a, b;
};

int32_t main(){
	int N, M, S;
	cin >> N >> M >> S;
	vector<area> A;
	for(int i = 0; i < N; i++){
		int a, b; cin >> a >> b;
		A.push_back({a, b});
	}
	sort(A.begin(), A.end(), [](area x, area y){
		return x.a > y.a;
	});
	
	int ans = 0;
	for(int i = 0; i < M; i++){
		ans += A[i].a;
	}
	
	priority_queue<pair<int, int>> pq, pqe, pq1, pq1e, pq2, pq2e;
	for(int i = M; i < N; i++){
		pq.push({A[i].a, i});
	}
	for(int i = 0; i < M; i++){
		pq1.push({A[i].b - A[i].a, i});
	}
	for(int i = M; i < N; i++){
		pq2.push({A[i].b, i});
	}
	for(int i = 0; i < S; i++){
		while(pq.size() && pqe.size() && pq.top() == pqe.top()) pq.pop(), pqe.pop();
		while(pq1.size() && pq1e.size() && pq1.top() == pq1e.top()) pq1.pop(), pq1e.pop();
		while(pq2.size() && pq2e.size() && pq2.top() == pq2e.top()) pq2.pop(), pq2e.pop();
		if(pq1.top().first + pq.top().first > pq2.top().first){
			ans += pq1.top().first + pq.top().first; pq1.pop(); int added = pq.top().second; pq.pop(); pq2e.push({A[added].b, added}); pq1.push({A[added].b - A[added].a, added});
		}else{
			ans += pq2.top().first; int added = pq.top().second; pqe.push({A[added].a, added}); pq2.pop();
		}
	}
	cout << ans << endl;
}

• Subtask 1: 15 / 100