fork download
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 234567
  13. #define MAX 1037471823
  14. #define Q 103
  15.  
  16. using namespace std;
  17.  
  18. int n, now, ans;
  19. struct node
  20. {
  21. int x, y;
  22. bool operator < (const node &k) const { return y < k.y || (y == k.y && x < k.x); }
  23. } m[MS];
  24.  
  25. int main()
  26. {
  27. priority_queue <int> q;
  28. scanf("%d", &n);
  29. rep(i, 1, n) scanf("%d%d", &m[i].x, &m[i].y);
  30. sort(m+1, m+1+n); now = 0;
  31. rep(i, 1, n) if (now + m[i].x <= m[i].y)
  32. {
  33. q.push(m[i].x); now += m[i].x; ans++;
  34. }
  35. else if (!q.empty() && q.top() > m[i].x)
  36. {
  37. now = now - q.top() + m[i].x;
  38. q.pop(); q.push(m[i].x);
  39. }
  40. printf("%d\n", ans);
  41. return 0;
  42. }
  43.  
Success #stdin #stdout 0s 5268KB
stdin
4
100 200
200 1300
1000 1250
2000 3200
stdout
3