Submission #1325047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325047		illuminastorm	Gym Badges (NOI22_gymbadges)	C++20	0 / 100	125 ms	16052 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> X(N), L(N);
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < N; i++) cin >> L[i];

    // Store gyms as (Li, Xi)
    // We sort by Li (deadline / level cap)
    vector<pair<long long, long long>> gyms(N);
    for (int i = 0; i < N; i++) {
        gyms[i] = {L[i], X[i]};
    }

    // Sort by increasing Li
    // If two gyms have same Li, smaller Xi first doesn't matter,
    // because heap will handle optimal selection.
    sort(gyms.begin(), gyms.end());

    long long currentLevel = 0;

    // Max heap to store chosen Xi
    // We want to remove the largest Xi if we exceed a cap.
    priority_queue<long long> chosen;

    for (int i = 0; i < N; i++) {

        long long cap = gyms[i].first;
        long long gain = gyms[i].second;

        // Tentatively take this gym
        currentLevel += gain;
        chosen.push(gain);

        // If we now violate this gym's cap,
        // remove the largest Xi chosen so far.
        if (currentLevel > cap) {
            long long removed = chosen.top();
            chosen.pop();
            currentLevel -= removed;
        }
    }

    // The number of gyms we managed to keep
    cout << chosen.size();

    return 0;
}

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