Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "optimization.h"
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <cstdio>
- #include <vector>
- #include <queue>
- #include <set>
- #include <bitset>
- #include <unordered_map>
- #include <cassert>
- #include <cstring>
- #include <time.h>
- #include <math.h>
- #include <random>
- #include <unordered_map>
- #include <functional>
- using namespace std;
- /// custom defines
- #define IS_FIN_FOUT__
- #define INFILE "file"
- //#define IS_TEST
- typedef int64_t ll;
- typedef __uint128_t bll;
- typedef uint64_t ull;
- typedef __uint128_t ubll;
- #define ff first
- #define ss second
- #define array_bounds(a) a.begin(), a.end()
- /// end custom defines
- vector<pair<int, int>> boxes;
- int main() {
- #ifdef IS_FIN_FOUT__
- freopen(INFILE".in", "r", stdin);
- freopen(INFILE".out", "w", stdout);
- #endif
- int n = readInt();
- for (int i = 0; i < n; ++i) {
- boxes.push_back({readInt(), readInt()});
- }
- sort(boxes.begin(), boxes.end(), [](auto lhs, auto rhs) -> bool {
- return lhs.first + lhs.second < rhs.first + rhs.second;
- });
- auto compare = [](auto &lhs, auto &rhs) -> bool {
- return lhs.first > rhs.first;
- };
- set<pair<int, int>, decltype(compare)> heap(compare);
- uint64_t weight = 0;
- for (auto box : boxes) {
- if (box.second >= weight) {
- heap.insert(box);
- weight += box.first;
- } else {
- if (box.first < heap.begin()->first) {
- weight -= heap.begin()->first;
- heap.erase(heap.begin());
- heap.insert(box);
- weight += box.first;
- }
- }
- }
- writeInt(heap.size());
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement