제출 #1174521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174521		khangrl	Gym Badges (NOI22_gymbadges)	C++20	0 / 100	299 ms	6484 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Gym {
    int levelCap;
    int levelGain;
};

// Comparator for sorting gyms by level cap
bool compareGyms(const Gym &a, const Gym &b) {
    return a.levelCap < b.levelCap;
}

int maxBadges(vector<Gym> &gyms) {
    sort(gyms.begin(), gyms.end(), compareGyms); // Sort gyms by level cap
    priority_queue<int> pq; // Max-heap to store level gains
    int currentLevel = 0, badgeCount = 0, i = 0, n = gyms.size();

    while (i < n || !pq.empty()) {
        // Add all gyms that are available to challenge
        while (i < n && gyms[i].levelCap >= currentLevel) {
            pq.push(gyms[i].levelGain);
            i++;
        }
        
        // If no gym can be challenged, break
        if (pq.empty()) break;

        // Challenge the gym with the highest level gain
        currentLevel += pq.top();
        pq.pop();
        badgeCount++;
    }

    return badgeCount;
}

int main() {
    int N;
    cin >> N;
    vector<Gym> gyms(N);

    for (int i = 0; i < N; i++) {
        cin >> gyms[i].levelCap >> gyms[i].levelGain;
    }

    cout << maxBadges(gyms) << endl;
    return 0;
}

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