1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <set>
#include <map>
#include <unordered_map>

int main()
{
    int spratCount = 0;
    std::cin >> spratCount;
    std::multiset<int, std::greater<>> weights;
    for (int s = 0; s < spratCount; s++) {
        int weight = 0;
        std::cin >> weight;
        weights.insert(weight);
    }
    int events = 0;
    std::cin >> events;
    for (int e = 0; e < events; e++) {
        int type = 0;
        std::cin >> type;
        if (type == 1) {
            unsigned long long curr, target;
            std::cin >> curr;
            std::cin >> target;
            if (curr == target) {
                std::cout << 0 << std::endl;
                continue;
            }

            std::unordered_map<int, int> uses;
            int toConsume = 0;
            bool continueLoop = false;
            while (curr < target) {
                auto maxAvailableWeightIter = weights.upper_bound(curr);
                if (maxAvailableWeightIter == weights.end()) {
                    std::cout << -1 << std::endl;
                    continueLoop = true;
                    break;
                }
                auto currUsesIter = uses.find(*maxAvailableWeightIter);
                while (currUsesIter != uses.end() && maxAvailableWeightIter != weights.end() &&
                        uses.at(*maxAvailableWeightIter) == weights.count(*maxAvailableWeightIter)) {
                    maxAvailableWeightIter++;
                    currUsesIter = uses.find(*maxAvailableWeightIter);
                }
                if (maxAvailableWeightIter != weights.end()) {
                    curr += *maxAvailableWeightIter;
                    currUsesIter = uses.find(*maxAvailableWeightIter);
                    if (currUsesIter == uses.end()) {
                        uses.insert(std::pair<int, int>(*maxAvailableWeightIter,  1));
                    } else {
                        auto toPut = uses.find(*maxAvailableWeightIter);
                        toPut->second = uses.at(*maxAvailableWeightIter) + 1;
                    }
                    toConsume++;
                } else if (curr < target) {
                    std::cout << -1 << std::endl;
                    continueLoop = true;
                    break;
                }
            }
            if (continueLoop) continue;
            std::cout << toConsume << std::endl;

        } else if (type == 2) {
            int weight = 0;
            std::cin >> weight;
            weights.insert(weight);
        } else if (type == 3) {
            int weight = 0;
            std::cin >> weight;
            weights.erase(weights.lower_bound(weight));
        }
    }
    return 0;
}