Madiyar

Untitled

Jan 19th, 2013
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  21. #define f0(a) memset(a, 0, sizeof(a))
  22. #define all(v) v.begin(), v.end()
  23. #define pii pair<int,int>
  24. #define vi vector<int>
  25. #define ll long long
  26. #ifdef WIN32
  27.     #define I64 "%I64d"
  28. #else
  29.     #define I64 "%lld"
  30. #endif
  31. const int maxn = (int)1e6;
  32. ll H[maxn];
  33. int n, M, S;
  34.  
  35. pii a[maxn];
  36.  
  37. priority_queue<int, vector<int> , greater<int> > pq;
  38. priority_queue<int> pqm;
  39.  
  40. int main() {
  41.  
  42.     scanf("%d%d%d", &n, &M, &S);
  43.     for (int i = 0; i < n; ++i)  {
  44.         int u, v;
  45.         scanf("%d%d", &u, &v);
  46.         a[i] = mp(u, v);
  47.     }
  48.  
  49.     sort(a, a + n);
  50.     reverse(a, a + n);
  51.  
  52.     ll ans = 0, sum = 0;
  53.    
  54.     for (int i = 0; i < M + S; ++i) {
  55.         sum += a[i].s;
  56.  
  57.         if (pq.size() != M) {
  58.             sum += a[i].f - a[i].s;
  59.             pq.push(a[i].f - a[i].s);    
  60.         }
  61.         else
  62.         if (M > 0 && pq.top() < a[i].f - a[i].s) {
  63.             sum -= pq.top();
  64.             pq.pop();
  65.             sum += a[i].f - a[i].s;
  66.             pq.push(a[i].f - a[i].s);
  67.         }
  68.         H[i] = sum;
  69.         ans = max(ans, H[i]);
  70.     }
  71.  
  72.  
  73.     int rem = n - M - S;
  74.     sum = 0;
  75.  
  76.     for (int i = n - 1; i >= M; --i) {
  77.         sum += a[i].s;
  78.         if (pqm.size() != rem) {
  79.             sum -= a[i].s;
  80.             pqm.push(a[i].s);
  81.         } else
  82.         if (rem > 0 && pqm.top() > a[i].s)
  83.         {
  84.             sum += pqm.top();
  85.             pqm.pop();
  86.             sum -= a[i].s;
  87.             pqm.push(a[i].s);
  88.         }
  89.        
  90.         if (pqm.size() == rem)
  91.             ans = max(ans, (i == 0) ? 0 : H[i - 1] + sum);
  92.     }
  93.  
  94.     cout << ans << endl;            
  95.     return 0;
  96.  
  97. }
Advertisement
Add Comment
Please, Sign In to add comment