oj.uz

Submission #676590

# Submission time Handle Problem Language Result Execution time Memory
676590 2022-12-31T11:29:32 Z QwertyPi Schools (IZhO13_school) C++14
15 / 100
 224 ms 17512 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 3 ms 596 KB Output isn't correct
8 Incorrect 3 ms 468 KB Output isn't correct
9 Incorrect 3 ms 468 KB Output isn't correct
10 Incorrect 3 ms 468 KB Output isn't correct
11 Incorrect 4 ms 596 KB Output isn't correct
12 Incorrect 4 ms 596 KB Output isn't correct
13 Incorrect 21 ms 1864 KB Output isn't correct
14 Incorrect 52 ms 5888 KB Output isn't correct
15 Incorrect 96 ms 11320 KB Output isn't correct
16 Incorrect 145 ms 12508 KB Output isn't correct
17 Incorrect 155 ms 13364 KB Output isn't correct
18 Incorrect 157 ms 14312 KB Output isn't correct
19 Incorrect 224 ms 15108 KB Output isn't correct
20 Incorrect 203 ms 17512 KB Output isn't correct