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...