oj.uz

Submission #319083

# Submission time Handle Problem Language Result Execution time Memory
319083 2020-11-03T22:36:24 Z sofapuden Schools (IZhO13_school) C++14
75 / 100
 272 ms 12920 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 368 KB Output is correct
7 Correct 4 ms 492 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 5 ms 492 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 30 ms 2028 KB Output is correct
14 Correct 66 ms 3428 KB Output is correct
15 Correct 135 ms 6500 KB Output is correct
16 Incorrect 159 ms 7520 KB Output isn't correct
17 Incorrect 191 ms 9568 KB Output isn't correct
18 Incorrect 206 ms 10336 KB Output isn't correct
19 Incorrect 224 ms 11104 KB Output isn't correct
20 Incorrect 272 ms 12920 KB Output isn't correct