# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
676304 | vjudge1 | Schools (IZhO13_school) | C++17 | 204 ms | 13868 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;
const int N = 3e5 + 5;
/*
i < j
a[i] + b[j] > a[j] + b[i]
<=> a[i] - a[j] > b[i] - b[j]
--> just choose prefix
*/
int id[N];
int a[N], b[N];
int n, m, s;
int64_t pre[N], suf[N];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> s;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
}
sort(id + 1, id + n + 1, [&](int i, int j) {
return a[i] - a[j] > b[i] - b[j];
});
{
multiset<int> ss;
int64_t cur = 0;
for (int i = 1; i <= n; i++) {
cur += a[i];
ss.insert(a[i]);
if (ss.size() > m) {
cur -= *ss.begin();
ss.erase(*ss.begin());
}
pre[i] = cur;
}
}
{
multiset<int> ss;
int64_t cur = 0;
for (int i = n; i >= 1; i--) {
cur += b[i];
ss.insert(b[i]);
if (ss.size() > s) {
cur -= *ss.begin();
ss.erase(*ss.begin());
}
suf[i] = cur;
}
}
int64_t best = 0;
for (int i = m; i <= n - s; i++) {
best = max(best, pre[i] + suf[i + 1]);
}
cout << best;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |