Submission #1023163

#TimeUsernameProblemLanguageResultExecution timeMemory
1023163avighnaGym Badges (NOI22_gymbadges)C++17
100 / 100
502 ms46512 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...