Advertisement
Guest User

Untitled

a guest
Dec 18th, 2018
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. #define b first
  8. #define a second
  9.  
  10. const int N = int(2 * 1e5 + 10);
  11.  
  12. pair<long long, long long> v[N];
  13. multiset<long long> s;
  14.  
  15. int main() {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0), cout.tie(0);
  18.  
  19.     int n;
  20.     cin >> n;
  21.  
  22.     for (int i = 0; i < n; ++i) {
  23.         cin >> v[i].a >> v[i].b;
  24.         v[i].b += v[i].a;
  25.     }
  26.  
  27.     sort(v, v + n);
  28.  
  29.     int res = -1;
  30.  
  31.     long long cnt = 0;
  32.  
  33.     for (int i = 0; i < n; ++i)
  34.     {
  35.         s.insert(v[i].a);
  36.         cnt += v[i].a;
  37.  
  38.         while (res != -1 && res <= s.size()) {
  39.             cnt -= *(s.begin());
  40.             s.erase(s.begin());
  41.         }
  42.  
  43.         while (cnt >= v[i].b)
  44.         {
  45.             res = s.size();
  46.             cnt -= *(s.begin());
  47.             s.erase(s.begin());
  48.         }
  49.     }
  50.  
  51.     cout << res << endl;
  52.  
  53.     return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement