제출 #757966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757966		Dexva	Gym Badges (NOI22_gymbadges)	C++14	24 / 100	187 ms	16852 KiB

Main

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

#define lln long long

void solve() {
    lln n; cin >> n;
    lln gain[n], cap[n];
    for (lln i=0;i<n;i++) cin >> gain[i];
    for (lln i=0;i<n;i++) cin >> cap[i];

    lln ans = 0;
    if (n <= 10) {
        vector<lln> cur;
        for (lln i=0;i<n;i++) cur.push_back(i);

        do {
            lln level = 0, badges = 0;
            for (auto index : cur) {
                if (level <= cap[index]) {
                    level += gain[index];
                    badges++;
                }
            }
            ans = max(ans, badges);
        } while (next_permutation(cur.begin(),cur.end()));
    }
    else { // if cap is constant for all gyms
        vector<pair<lln,lln> > gyms; //gain, cap
        for (lln i=0;i<n;i++) gyms.push_back(make_pair(gain[i], cap[i]));

        sort(gyms.begin(),gyms.end());

        lln level = 0, badges = 0;
        for (lln i=0;i<n;i++) {
            if (level <= get<1>(gyms[i])) {
                level += get<0>(gyms[i]);
                badges++;
            }
        } 
        ans = max(ans, badges);
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while (t--) solve();
    return 0;
}

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