Question

У Арсения есть n зверьков. Каждый из них обладает характером, поэтому, если в клетке, где находится i-й зверек, есть не больше ci зверьков, то его агрессивность будет ai, а если больше, то его агрессивность будет bi (ai≤bi).

Также у Арсения есть клетка прочностью s, которая выдержит зверьков, суммарная агрессивность которых не больше s.

Помогите Арсению выяснить, какое наибольшее число зверьков он может хранить в клетке одновременно.

Входные данные
В первой строке через пробел заданы два целых числа n и s (1≤n≤105,0≤s≤109).

В следующих n строках задана характеристика животных числами ai, bi и ci (0≤ai≤bi≤109,1≤ci≤n).

Выходные данные
Выведите единственное число — наибольшее количество животных, которое Арсений может одновременно хранить в клетке.

Примеры
входные данные
2 6
2 4 1
2 4 2
выходные данные
2

входные данные
4 10
3 4 2
3 5 3
1 1 1
2 7 3
выходные данные
3

Answer 1

Код

• #include <iostream>
• #include <utility>
• #include <numeric>
• #include <vector>
• class Beast {
•    int trigger;
•    double aggression;
•    double rage_aggression;
• public:
•    Beast() = default;
•    Beast(int trigger, double aggression, double range_aggression)
•    : trigger(trigger), aggression(aggression), rage_aggression(range_aggression)
•    { }
•    Beast(const Beast&) = default;
•    Beast(Beast&&) = default;
•    Beast& operator=(const Beast&) = default;
•    Beast& operator=(Beast&&) = default;
•    [[nodiscard]] double calculate_aggression(unsigned long amount) const {
•        return amount > trigger ? rage_aggression : aggression;
•    }
•    void ReadFrom (std::istream& is) {
•        is >> aggression >> rage_aggression >> trigger;
•    }
•    void WriteTo(std::ostream &os) const {
•        os << aggression << " " << rage_aggression << " " << trigger;
•    }
• };
• std::istream& operator >>(std::istream &is, Beast &cls) {
•    cls.ReadFrom(is);
•    return is;
• }
• std::ostream& operator <<(std::ostream &os, const Beast &cls) {
•    cls.WriteTo(os);
•    return os;
• }
• class Cage {
•    double durability;
•    std::vector<Beast> container;
• public:
•    explicit Cage(double durability, std::vector<Beast> container)
•    : durability(durability), container(std::move(container))
•    { }
•    Cage(const Cage&) = default;
•    Cage(Cage&&) = default;
•    Cage& operator=(const Cage&) = default;
•    Cage& operator=(Cage&&) = default;
•    [[nodiscard]] double calculate_aggressive() const {
•        auto amount = container.size();
•        if (amount == 0) return 0;
•        return std::accumulate(container.begin(), container.end(), 0.0,
•        [amount](double total_aggressive, const Beast & beast){
•            return total_aggressive + beast.calculate_aggression(amount);
•        });
•    }
•    [[nodiscard]] bool is_it_normal() const {
•        auto aggressive = calculate_aggressive();
•        return aggressive <= durability;
•    }
•    [[nodiscard]] int get_capacity() const {
•        return container.size();
•    }
•    [[nodiscard]] double get_durability() const {
•        return durability;
•    }
• };
• template <typename T>
• void subsetsUtil(std::vector<T>& A, std::vector<std::vector<T> >& res,
•                 std::vector<T>& subset, int index)
• {
•    res.push_back(subset);
•    for (int i = index; i < A.size(); i++) {
•        // include the A[i] in subset.
•        subset.push_back(A[i]);
•        // move onto the next element.
•        subsetsUtil(A, res, subset, i + 1);
•        // exclude the A[i] from subset and triggers
•        // backtracking.
•        subset.pop_back();
•    }
• }
• template <typename T>
• std::vector<std::vector<T>> P(std::vector<T>& A)
• {
•    std::vector<T> subset;
•    std::vector<std::vector<T>> res;
•    int index = 0;
•    subsetsUtil(A, res, subset, index);
•    return res;
• }
• int main () {
•    int n, s;
•    Beast noname{};
•    std::vector<Beast> set_of_beasts;
•    std::cin >> n >> s;
•    for (auto i = 0; i < n; ++i) {
•        std::cin >> noname;
•        set_of_beasts.push_back(noname);
•    }
•    auto selections = P(set_of_beasts);
•    std::vector<Cage> variants;
•    std::transform(selections.begin(), selections.end(), std::back_inserter(variants), [s](std::vector<Beast> &selection){
•        return Cage(s, selection);
•    });
•    std::vector<Cage> true_variants;
•    std::copy_if(variants.begin(), variants.end(), std::back_inserter(true_variants), [](Cage& x) {return x.is_it_normal();});
•    auto the_best_of_the_best_variant = *std::max_element(true_variants.begin(), true_variants.end(), [](Cage & s1, Cage & s2){
•        return s1.get_capacity() < s2.get_capacity();
•    });
•    std::cout << the_best_of_the_best_variant.get_capacity();
•    return 0;
• }