Submission #757966

#TimeUsernameProblemLanguageResultExecution timeMemory
757966DexvaGym Badges (NOI22_gymbadges)C++14
24 / 100
187 ms16852 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...