Advertisement
Guest User

Untitled

a guest
Jan 24th, 2013
326
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <algorithm>
  8. #include <cstring>
  9. #include <string>
  10. #include <cmath>
  11. using namespace std;
  12.  
  13. string problem = "school";
  14.  
  15. const int MAXN = 300000;
  16. int n, m, s;
  17. pair<int,int> p[MAXN];
  18.  
  19. void solve(){
  20.     scanf("%d%d%d",&n,&m,&s);
  21.     for (int i=0; i<n; ++i) scanf("%d%d",&p[i].first,&p[i].second);
  22.     sort(p, p+n);
  23.     priority_queue<pair<int,pair<int,int> > > q;
  24.     long long sa=0, sb=0, st=0;
  25.     for (int i=n-m; i<n; ++i) {
  26.         q.push(make_pair(-(p[i].first-p[i].second),p[i]));
  27.         sa += p[i].first;
  28.     }
  29.     multiset<int> h;
  30.     vector<int> bs;
  31.     for (int i=0; i<n-m; ++i) bs.push_back(p[i].second);
  32.     sort(bs.begin(), bs.end());
  33.     for (int i=0; i<s; ++i) {
  34.         h.insert(bs[bs.size()-i-1]);
  35.         st += bs[bs.size()-i-1];
  36.     }
  37.  
  38.     long long res = sa+st;
  39.     for (int i=n-m-1; i>=n-m-s; --i){
  40.         if (!h.empty() && *h.begin()<p[i].second){
  41.             st -= p[i].second;
  42.             h.erase(h.find(p[i].second));
  43.         } else {
  44.             st -= *h.begin();
  45.             h.erase(h.begin());
  46.         }
  47.         if (-q.top().first >= p[i].first-p[i].second){
  48.             sb += p[i].second;
  49.         } else {
  50.             sa -= q.top().second.first;
  51.             sb += q.top().second.second;
  52.             q.pop();
  53.             sa += p[i].first;
  54.             q.push(make_pair(-(p[i].first-p[i].second),p[i]));
  55.         }
  56.         if (sa+sb+st > res){
  57.             res=sa+sb+st;
  58.         }
  59.     }
  60.  
  61.     cout << res << endl;
  62. }
  63.  
  64.  
  65. int main(){
  66.  
  67. #ifdef KP_HOME
  68.     freopen("input.txt","r",stdin);
  69.     //freopen("output.txt","w",stdout);
  70. #else
  71.     freopen((problem+".in").c_str(),"r",stdin);
  72.     freopen((problem+".out").c_str(),"w",stdout);
  73.     //freopen("input.txt","r",stdin);
  74.     //freopen("output.txt","w",stdout);
  75. #endif
  76.  
  77.     solve();
  78.  
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement