#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";
}
# |
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 |
364 KB |
Output is correct |
7 |
Correct |
4 ms |
620 KB |
Output is correct |
8 |
Correct |
6 ms |
768 KB |
Output is correct |
9 |
Correct |
5 ms |
620 KB |
Output is correct |
10 |
Correct |
5 ms |
748 KB |
Output is correct |
11 |
Correct |
5 ms |
620 KB |
Output is correct |
12 |
Correct |
5 ms |
620 KB |
Output is correct |
13 |
Correct |
32 ms |
2916 KB |
Output is correct |
14 |
Correct |
74 ms |
5088 KB |
Output is correct |
15 |
Correct |
163 ms |
9316 KB |
Output is correct |
16 |
Correct |
174 ms |
10724 KB |
Output is correct |
17 |
Correct |
199 ms |
13660 KB |
Output is correct |
18 |
Correct |
229 ms |
14940 KB |
Output is correct |
19 |
Correct |
239 ms |
15964 KB |
Output is correct |
20 |
Correct |
279 ms |
18140 KB |
Output is correct |