Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. pair<int, int> box[100000];
  9. int d[1000][1000];
  10.  
  11. bool q(pair<int, int> a, pair<int, int> b) {
  12. if (a.first + a.second == b.first + b.second)
  13. return a.first < b.first;
  14. return a.first + a.second < b.first + b.second;
  15. }
  16.  
  17. int main() {
  18. ios_base::sync_with_stdio(false);
  19. cin.tie(0);
  20. cout.tie(0);
  21. int n;
  22. cin >> n;
  23. for (int i = 0; i < n; i++)
  24. cin >> box[i].first >> box[i].second;
  25.  
  26. sort(box, box + n, q);
  27. priority_queue<int> used;
  28. int sum = 0;
  29. for (int i = 0; i < n; i++) {
  30. if (sum <= box[i].second) {
  31. used.push(box[i].first);
  32. sum += box[i].first;
  33. } else if (box[i].first < used.top()) {
  34. sum -= used.top();
  35. used.pop();
  36. used.push(box[i].first);
  37. sum += box[i].first;
  38. }
  39. }
  40.  
  41. cout << used.size();
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement