Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <cmath>
- using namespace std;
- string problem = "school";
- const int MAXN = 300000;
- int n, m, s;
- pair<int,int> p[MAXN];
- void solve(){
- scanf("%d%d%d",&n,&m,&s);
- for (int i=0; i<n; ++i) scanf("%d%d",&p[i].first,&p[i].second);
- sort(p, p+n);
- priority_queue<pair<int,pair<int,int> > > q;
- long long sa=0, sb=0, st=0;
- for (int i=n-m; i<n; ++i) {
- q.push(make_pair(-(p[i].first-p[i].second),p[i]));
- sa += p[i].first;
- }
- multiset<int> h;
- vector<int> bs;
- for (int i=0; i<n-m; ++i) bs.push_back(p[i].second);
- sort(bs.begin(), bs.end());
- for (int i=0; i<s; ++i) {
- h.insert(bs[bs.size()-i-1]);
- st += bs[bs.size()-i-1];
- }
- long long res = sa+st;
- for (int i=n-m-1; i>=n-m-s; --i){
- if (!h.empty() && *h.begin()<p[i].second){
- st -= p[i].second;
- h.erase(h.find(p[i].second));
- } else {
- st -= *h.begin();
- h.erase(h.begin());
- }
- if (-q.top().first >= p[i].first-p[i].second){
- sb += p[i].second;
- } else {
- sa -= q.top().second.first;
- sb += q.top().second.second;
- q.pop();
- sa += p[i].first;
- q.push(make_pair(-(p[i].first-p[i].second),p[i]));
- }
- if (sa+sb+st > res){
- res=sa+sb+st;
- }
- }
- cout << res << endl;
- }
- int main(){
- #ifdef KP_HOME
- freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- #else
- freopen((problem+".in").c_str(),"r",stdin);
- freopen((problem+".out").c_str(),"w",stdout);
- //freopen("input.txt","r",stdin);
- //freopen("output.txt","w",stdout);
- #endif
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement