Advertisement
Guest User

Untitled

a guest
Apr 26th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include "optimization.h"
  2. #include <iostream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <vector>
  7. #include <queue>
  8. #include <set>
  9. #include <bitset>
  10. #include <unordered_map>
  11. #include <cassert>
  12. #include <cstring>
  13. #include <time.h>
  14. #include <math.h>
  15. #include <random>
  16. #include <unordered_map>
  17. #include <functional>
  18.  
  19.  
  20. using namespace std;
  21.  
  22.  
  23. /// custom defines
  24.  
  25. #define IS_FIN_FOUT__
  26. #define INFILE "file"
  27.  
  28. //#define IS_TEST
  29.  
  30. typedef int64_t ll;
  31. typedef __uint128_t bll;
  32. typedef uint64_t ull;
  33. typedef __uint128_t ubll;
  34. #define ff first
  35. #define ss second
  36. #define array_bounds(a) a.begin(), a.end()
  37.  
  38. /// end custom defines
  39.  
  40. vector<pair<int, int>> boxes;
  41.  
  42. int main() {
  43.  
  44. #ifdef IS_FIN_FOUT__
  45.   freopen(INFILE".in", "r", stdin);
  46.   freopen(INFILE".out", "w", stdout);
  47. #endif
  48.  
  49.   int n = readInt();
  50.  
  51.   for (int i = 0; i < n; ++i) {
  52.     boxes.push_back({readInt(), readInt()});
  53.   }
  54.  
  55.   sort(boxes.begin(), boxes.end(), [](auto lhs, auto rhs) -> bool {
  56.     return lhs.first + lhs.second < rhs.first + rhs.second;
  57.   });
  58.  
  59.   auto compare = [](auto &lhs, auto &rhs) -> bool {
  60.     return lhs.first > rhs.first;
  61.   };
  62.  
  63.   set<pair<int, int>, decltype(compare)> heap(compare);
  64.  
  65.   uint64_t weight = 0;
  66.  
  67.   for (auto box : boxes) {
  68.     if (box.second >= weight) {
  69.       heap.insert(box);
  70.       weight += box.first;
  71.     } else {
  72.       if (box.first < heap.begin()->first) {
  73.         weight -= heap.begin()->first;
  74.         heap.erase(heap.begin());
  75.  
  76.         heap.insert(box);
  77.         weight += box.first;
  78.       }
  79.     }
  80.   }
  81.  
  82.   writeInt(heap.size());
  83.  
  84.   return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement