Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- #include <map>
- #include <set>
- #include <ctime>
- #include <cassert>
- #include <queue>
- using namespace std;
- #define f first
- #define s second
- #define mp make_pair
- #define pb push_back
- #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
- #define f0(a) memset(a, 0, sizeof(a))
- #define all(v) v.begin(), v.end()
- #define pii pair<int,int>
- #define vi vector<int>
- #define ll long long
- #ifdef WIN32
- #define I64 "%I64d"
- #else
- #define I64 "%lld"
- #endif
- const int maxn = (int)1e6;
- ll H[maxn];
- int n, M, S;
- pii a[maxn];
- priority_queue<int, vector<int> , greater<int> > pq;
- priority_queue<int> pqm;
- int main() {
- scanf("%d%d%d", &n, &M, &S);
- for (int i = 0; i < n; ++i) {
- int u, v;
- scanf("%d%d", &u, &v);
- a[i] = mp(u, v);
- }
- sort(a, a + n);
- reverse(a, a + n);
- ll ans = 0, sum = 0;
- for (int i = 0; i < M + S; ++i) {
- sum += a[i].s;
- if (pq.size() != M) {
- sum += a[i].f - a[i].s;
- pq.push(a[i].f - a[i].s);
- }
- else
- if (M > 0 && pq.top() < a[i].f - a[i].s) {
- sum -= pq.top();
- pq.pop();
- sum += a[i].f - a[i].s;
- pq.push(a[i].f - a[i].s);
- }
- H[i] = sum;
- ans = max(ans, H[i]);
- }
- int rem = n - M - S;
- sum = 0;
- for (int i = n - 1; i >= M; --i) {
- sum += a[i].s;
- if (pqm.size() != rem) {
- sum -= a[i].s;
- pqm.push(a[i].s);
- } else
- if (rem > 0 && pqm.top() > a[i].s)
- {
- sum += pqm.top();
- pqm.pop();
- sum -= a[i].s;
- pqm.push(a[i].s);
- }
- if (pqm.size() == rem)
- ans = max(ans, (i == 0) ? 0 : H[i - 1] + sum);
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment