#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int n, m, s;
pll x[300010];
set<pll> naja, najb, raz;
ll rez;
int main() {
ios;
cin >> n >> m >> s;
for(int i=0; i<n; ++i) {
cin >> x[i].xx >> x[i].yy;
}
sort(x, x+n, greater<pll>());
for(int i=0; i<m; ++i) {
rez+=x[i].xx;
raz.insert({x[i].yy-x[i].xx, (ll)i});
}
for(int i=m; i<n; ++i) {
naja.insert({x[i].xx, (ll)i});
najb.insert({x[i].yy, (ll)i});
}
for(int kk=0;kk<s;kk++){
bool uzeo1=0, uzeo2=0;
pll pr, dr, tr;
if(!najb.empty()) {
pr=*prev(najb.end());
uzeo1=1;
}
if(!raz.empty() && !naja.empty()) {
dr=*prev(raz.end());
tr=*prev(naja.end());
uzeo2=1;
}
if(!uzeo2) {
rez+=pr.xx;
if(!najb.empty()) najb.erase(prev(najb.end()));
auto it=naja.find({x[pr.yy].xx, pr.yy});
if(it!=naja.end() && !naja.empty()) naja.erase(it);
}
else if(!uzeo1) {
rez+=dr.xx+tr.xx;
if(!raz.empty()) raz.erase(prev(raz.end()));
if(!naja.empty()) naja.erase(prev(naja.end()));
raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy});
}
else if(pr.xx>dr.xx+tr.xx) {
rez+=pr.xx;
if(!najb.empty()) najb.erase(prev(najb.end()));
auto it=naja.find({x[pr.yy].xx, pr.yy});
if(it!=naja.end() && !naja.empty()) naja.erase(it);
}
else{
rez+=dr.xx+tr.xx;
if(!raz.empty()) raz.erase(prev(raz.end()));
if(!naja.empty()) naja.erase(prev(naja.end()));
raz.insert({x[tr.yy].yy-x[tr.yy].xx, tr.yy});
}
}
cout << rez;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
844 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
588 KB |
Output isn't correct |
| 9 |
Incorrect |
3 ms |
716 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
732 KB |
Output isn't correct |
| 11 |
Incorrect |
4 ms |
972 KB |
Output isn't correct |
| 12 |
Incorrect |
5 ms |
980 KB |
Output isn't correct |
| 13 |
Incorrect |
27 ms |
3400 KB |
Output isn't correct |
| 14 |
Incorrect |
90 ms |
10748 KB |
Output isn't correct |
| 15 |
Correct |
219 ms |
22620 KB |
Output is correct |
| 16 |
Incorrect |
324 ms |
24164 KB |
Output isn't correct |
| 17 |
Incorrect |
256 ms |
25796 KB |
Output isn't correct |
| 18 |
Incorrect |
262 ms |
28300 KB |
Output isn't correct |
| 19 |
Incorrect |
296 ms |
31040 KB |
Output isn't correct |
| 20 |
Incorrect |
327 ms |
36420 KB |
Output isn't correct |
