Submission #1023163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023163		avighna	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	502 ms	46512 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;

struct Gym {
    ll L, X;
};
bool operator<(const Gym &a, const Gym &b) {
    if (a.X != b.X) {
        return a.X < b.X;
    }
    return a.L < b.L;
}

int main() {
    ll n;
    std::cin >> n;
    std::vector<Gym> a(n);
    for (ll i = 0; i < n; ++ i) {
        std::cin >> a[i].X;
    }
    for (ll i = 0; i < n; ++ i) {
        std::cin >> a[i].L;
    }
    std::sort(a.begin(), a.end(), [](const Gym &i, const Gym &j) {
        return std::min(i.L, j.L - i.X) > std::min(j.L, i.L - j.X);
    });

    std::multiset<Gym> dp;
    ll level = 0;
    for (ll i = 0; i < n; ++ i) {
        if (dp.empty() || level <= a[i].L) {
            dp.insert(a[i]);
            level += a[i].X;
        } else if (level - dp.rbegin()->X <= a[i].L && dp.rbegin()->X > a[i].X) {
            level -= dp.rbegin()->X;
            dp.erase(--dp.end());
            dp.insert(a[i]);
            level += a[i].X;
        }
    }
    std::cout << dp.size() << "\n";
}

• Subtask 1: 15 / 15
• Subtask 2: 9 / 9
• Subtask 3: 27 / 27
• Subtask 4: 49 / 49