#include <bits/stdc++.h>
using namespace std;
const int maxN = 1<<19;
using ll = long long;
struct Pair {
int a, b, id;
} arr[maxN], temp_arr[maxN];
int n, m, s;
int invS[maxN], pS[maxN];
ll ds[maxN];
pair<int, ll> ft[maxN];
void update(int x, int u, int v) {
while (x <= n) {
ft[x].first += u;
ft[x].second += v;
x += x&-x;
}
}
ll query(int need) {
ll ans = 0, cur = 0;
for (int pos = 18; pos >= 0; --pos) {
if (need >= ft[cur + (1<<pos)].first) {
ans += ft[cur + (1<<pos)].second;
need -= ft[cur + (1<<pos)].first;
cur += (1<<pos);
}
}
return ans;
}
const int maxAB = maxN / 3;
int cnt[maxAB];
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &arr[i].a, &arr[i].b);
cnt[arr[i].b] += 1;
}
for (int i = 1; i <= maxAB; ++i) {
cnt[i] += cnt[i-1];
}
ll add = 0;
for (int i = 0, j = 0; i < n; ++i) {
int cur_pos = cnt[arr[i].b]--;
arr[i].id = n - cur_pos;
if (arr[i].id < s) {
ds[j++] = arr[i].a - arr[i].b;
add += arr[i].b;
}
}
sort(ds, ds+s, greater<>());
for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
for (int i = 0; i < n; ++i) {
cnt[arr[i].a] += 1;
temp_arr[i] = arr[i];
}
for (int i = 1; i <= maxAB; ++i) {
cnt[i] += cnt[i-1];
}
for (int i = 0; i < n; ++i) {
int cur_pos = cnt[temp_arr[i].a]--;
arr[n - cur_pos] = temp_arr[i];
}
for (int i = 0, j = 0; i < n; ++i) {
if (arr[i].id < s) continue;
invS[arr[i].id] = ++j;
pS[arr[i].id] = i;
update(invS[arr[i].id], 1, arr[i].a);
}
priority_queue<int, vector<int>, greater<>> kSet;
int posS = 0;
ll ans = -1e18;
for (int i = 0; i <= m; ++i) {
ans = max(ans, add + query(m - i));
if (i == m) break;
auto new_element = arr[pS[s+i]];
update(invS[s+i], -1, -new_element.a);
add += new_element.a;
int delta = new_element.b - new_element.a;
while (!kSet.empty() && delta > kSet.top()) {
if (posS >= s || ds[posS] + kSet.top() < 0) {
add -= kSet.top();
kSet.pop();
posS -= 1;
add -= ds[posS];
} else break;
}
if (posS >= s) {
if (!kSet.empty() && kSet.top() < delta) {
add += delta - kSet.top();
kSet.pop();
kSet.push(delta);
}
} else {
if (delta + ds[posS] > 0) {
add += delta + ds[posS++];
kSet.push(delta);
}
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
38 | scanf("%d%d%d", &n, &m, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
school.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
40 | scanf("%d%d", &arr[i].a, &arr[i].b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
school.cpp:44:10: warning: iteration 174761 invokes undefined behavior [-Waggressive-loop-optimizations]
44 | cnt[i] += cnt[i-1];
| ~~~~~~~^~~~~~~~~~~
school.cpp:43:20: note: within this loop
43 | for (int i = 1; i <= maxAB; ++i) {
| ~~^~~~~~~~
school.cpp:56:42: warning: iteration 174762 invokes undefined behavior [-Waggressive-loop-optimizations]
56 | for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
| ~~~~~~~^~~
school.cpp:56:20: note: within this loop
56 | for (int i = 0; i <= maxAB; ++i) cnt[i] = 0;
| ~~^~~~~~~~
school.cpp:62:10: warning: iteration 174761 invokes undefined behavior [-Waggressive-loop-optimizations]
62 | cnt[i] += cnt[i-1];
| ~~~~~~~^~~~~~~~~~~
school.cpp:61:20: note: within this loop
61 | for (int i = 1; i <= maxAB; ++i) {
| ~~^~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 2 |
Correct |
2 ms |
896 KB |
Output is correct |
| 3 |
Correct |
2 ms |
1024 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
1024 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
1024 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
1024 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
1280 KB |
Output isn't correct |
| 8 |
Correct |
4 ms |
1280 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
1280 KB |
Output isn't correct |
| 10 |
Incorrect |
4 ms |
1280 KB |
Output isn't correct |
| 11 |
Incorrect |
4 ms |
1280 KB |
Output isn't correct |
| 12 |
Incorrect |
4 ms |
1280 KB |
Output isn't correct |
| 13 |
Incorrect |
17 ms |
2688 KB |
Output isn't correct |
| 14 |
Incorrect |
30 ms |
4480 KB |
Output isn't correct |
| 15 |
Incorrect |
56 ms |
8440 KB |
Output isn't correct |
| 16 |
Correct |
75 ms |
7160 KB |
Output is correct |
| 17 |
Incorrect |
87 ms |
9848 KB |
Output isn't correct |
| 18 |
Incorrect |
97 ms |
11384 KB |
Output isn't correct |
| 19 |
Incorrect |
100 ms |
11952 KB |
Output isn't correct |
| 20 |
Correct |
124 ms |
13688 KB |
Output is correct |
