#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 1;
int f[nmax];
struct str {
int a, b, i; // iarasi ichb gipsy trap idol in str
} v[nmax], init[nmax];
bool ca(str x, str y) {
return x.a > y.a;
}
bool cb(str x, str y) {
return x.b > y.b;
}
int main() {
int n, ka, kb;
cin >> n >> ka >> kb;
multiset<pair<int, int>> ra, rb, a, b;
for(int i = 1; i <= n; i ++) {
cin >> v[i].a >> v[i].b;
v[i].i = i;
init[i] = v[i];
}
sort(v + 1, v + n + 1, ca);
for(int i = 1; i <= ka; i ++) {
a.insert({-v[i].a, v[i].i});
f[v[i].i] ++;
}
for(int i = ka + 1; i <= n; i ++) {
ra.insert({-v[i].a, v[i].i});
}
sort(v + 1, v + n + 1, cb);
for(int i = 1; i <= kb; i ++) {
b.insert({-v[i].b, v[i].i});
f[v[i].i] ++;
}
for(int i = kb + 1; i <= n; i ++) {
rb.insert({-v[i].b, v[i].i});
}
while(true) {
bool ac = 0;
auto it = a.begin();
while(it != a.end()) {
int i = (*it).second, x = (*it).first;
if(b.find({-init[i].b, i}) == b.end()) {
it ++;
continue;
}
ac = 1;
if(!rb.size()) {
auto cp = it;
it ++;
a.erase(a.lower_bound(*cp));
a.insert((*ra.begin()));
ra.erase(ra.lower_bound(*ra.begin()));
continue;
}
if(!ra.size()) {
b.erase(b.lower_bound({-init[i].b, i}));
b.insert((*rb.begin()));
rb.erase(rb.lower_bound(*rb.begin()));
it ++;
continue;
}
int na = (*ra.begin()).second, nb = (*rb.begin()).second;
if(init[i].a + init[nb].b > init[i].b + init[na].a) {
// eliminam b-ul, adaugam b nou
b.erase(b.lower_bound({-init[i].b, i}));
b.insert((*rb.begin()));
rb.erase(rb.lower_bound((*rb.begin())));
it ++;
} else if(init[i].a + init[nb].b < init[i].b + init[na].a){
auto cp = it;
it ++;
a.erase(a.lower_bound(*cp));
a.insert((*ra.begin()));
ra.erase(ra.lower_bound(*ra.begin()));
} else {
if(a.find({-init[nb].a, nb}) == a.end()) {
b.erase(b.lower_bound({-init[i].b, i}));
b.insert((*rb.begin()));
rb.erase(rb.lower_bound((*rb.begin())));
it ++;
} else if(b.find({-init[na].b, na}) == b.end()) {
auto cp = it;
it ++;
a.erase(a.lower_bound(*cp));
a.insert((*ra.begin()));
ra.erase(ra.lower_bound(*ra.begin()));
}
}
}
// cout << ac << '\n';
if(ac == 0) {
break;
}
}
// cout << "a:\n";
long long ans = 0;
for(auto it : a) {
ans += it.first;
// cout << it.first << " " << it.second << "\n";
}
// cout << "\nb:\n";
for(auto it : b) {
ans += it.first;
// cout << it.first << " " << it.second << '\n';
}
cout << -ans;
return 0;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:49:29: warning: unused variable 'x' [-Wunused-variable]
49 | int i = (*it).second, x = (*it).first;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 7 |
Incorrect |
4 ms |
2904 KB |
Output isn't correct |
| 8 |
Incorrect |
50 ms |
2908 KB |
Output isn't correct |
| 9 |
Incorrect |
10 ms |
2792 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
2908 KB |
Output isn't correct |
| 11 |
Incorrect |
4 ms |
2908 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
2908 KB |
Output isn't correct |
| 13 |
Incorrect |
73 ms |
6156 KB |
Output isn't correct |
| 14 |
Incorrect |
62 ms |
10064 KB |
Output isn't correct |
| 15 |
Runtime error |
53 ms |
5964 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
52 ms |
5972 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
62 ms |
5964 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
54 ms |
5968 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
62 ms |
5976 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
53 ms |
5920 KB |
Execution killed with signal 11 |
