#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << "\n"
/**
- we want to find to disjoint subsets of indices X (|X| = M) and Y (|Y| = S) so that sum{a[i]|i belongs to X} + sum{b[i]|i belongs to Y}
- it's easy to prove that if we sort the indices by b[i] - a[i] we will not use a a[i] and b[j] with i > j
- now we can see the best solution for a on prefix and the best solution for b on suffix and combine them
**/
const int N = 3e5;
int a[1 + N], b[1 + N];
int order[1 + N];
bool cmp (int x, int y) {
return b[x] - a[x] < b[y] - a[y];
}
ll pref[1 + N], suff[1 + N + 1];
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n, M, S;
cin >> n >> M >> S;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i];
order[i] = i;
}
sort (order + 1, order + n + 1, cmp);
/// make pref
ll sum = 0;
priority_queue <int> pq;
if (M == 0)
pref[0] = 0;
else
pref[0] = -1;
for (int i = 1; i <= n; i++) {
int index = order[i];
pq.push (-a[i]);
sum += a[i];
if (pq.size () > M) {
sum += pq.top ();
pq.pop ();
}
if (pq.size () == M)
pref[i] = sum;
else
pref[i] = -1;
}
/// make suff
while (pq.size ()) pq.pop ();
sum = 0;
if (S == 0)
suff[n + 1] = 0;
else
suff[n + 1] = -1;
for (int i = n; i > 0; i--) {
int index = order[i];
pq.push (-b[i]);
sum += b[i];
if (pq.size () > S) {
sum += pq.top ();
pq.pop ();
}
if (pq.size () == S)
suff[i] = sum;
else
suff[i] = -1;
}
ll ans = 0;
for (int i = 0; i <= n; i++)
if (pref[i] != -1 && suff[i + 1] != -1)
ans = max (ans, pref[i] + suff[i + 1]);
cout << ans << "\n";
return 0;
}
Compilation message
school.cpp: In function 'int main()':
school.cpp:49:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pq.size () > M) {
~~~~~~~~~~~^~~
school.cpp:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pq.size () == M)
~~~~~~~~~~~^~~~
school.cpp:46:13: warning: unused variable 'index' [-Wunused-variable]
int index = order[i];
^~~~~
school.cpp:69:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pq.size () > S) {
~~~~~~~~~~~^~~
school.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (pq.size () == S)
~~~~~~~~~~~^~~~
school.cpp:66:13: warning: unused variable 'index' [-Wunused-variable]
int index = order[i];
^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 8 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 9 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 10 |
Incorrect |
7 ms |
512 KB |
Output isn't correct |
| 11 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 12 |
Incorrect |
6 ms |
512 KB |
Output isn't correct |
| 13 |
Incorrect |
24 ms |
1536 KB |
Output isn't correct |
| 14 |
Incorrect |
45 ms |
2680 KB |
Output isn't correct |
| 15 |
Incorrect |
72 ms |
4728 KB |
Output isn't correct |
| 16 |
Incorrect |
88 ms |
6132 KB |
Output isn't correct |
| 17 |
Incorrect |
120 ms |
6900 KB |
Output isn't correct |
| 18 |
Incorrect |
141 ms |
7412 KB |
Output isn't correct |
| 19 |
Incorrect |
148 ms |
8048 KB |
Output isn't correct |
| 20 |
Incorrect |
171 ms |
9460 KB |
Output isn't correct |
