# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
873763 | MilosMilutinovic | Schools (IZhO13_school) | C++14 | 213 ms | 25560 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, s;
cin >> n >> m >> s;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return a[i] > a[j] || (a[i] == a[j] && b[i] < b[j]);
});
vector<int> new_a(n), new_b(n);
for (int i = 0; i < n; i++) {
new_a[i] = a[order[i]];
new_b[i] = b[order[i]];
}
a = new_a;
b = new_b;
order.clear();
for (int i = m; i < n; i++) {
order.push_back(i);
}
sort(order.begin(), order.end(), [&](int i, int j) {
return b[i] > b[j];
});
long long ans = 0;
for (int i = 0; i < m; i++) {
ans += a[i];
}
for (int i = 0; i < s; i++) {
ans += b[order[i]];
}
multiset<int> L;
for (int i = 0; i < m; i++) {
L.insert(-a[i] + b[i]);
}
multiset<pair<int, int>> R;
multiset<int> Ra;
multiset<pair<int, int>> Rab;
for (int i = 0; i < s; i++) {
R.emplace(-b[order[i]], order[i]);
Rab.emplace(-b[order[i]] + a[order[i]], order[i]);
}
for (int i = s; i < (int) order.size(); i++) {
Ra.insert(a[order[i]]);
}
long long res = ans;
while (!L.empty() && !R.empty()) {
assert(!Rab.empty());
res += *prev(L.end());
L.erase(prev(L.end()));
if (Ra.empty() || prev(Rab.end())->first > prev(R.end())->first + *prev(Ra.end())) {
auto it = prev(Rab.end());
res += it->first;
int i = it->second;
R.erase(R.find({-b[i], i}));
Rab.erase(it);
} else {
{
auto it = prev(R.end());
res += it->first;
int i = it->second;
R.erase(R.find({-b[i], i}));
Rab.erase(Rab.find({-b[i] + a[i], i}));
Ra.insert(a[i]);
}
{
auto it = prev(Ra.end());
res += *it;
Ra.erase(it);
}
}
ans = max(ans, res);
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |