Submission #886533

#	Time	Username	Problem	Language	Result	Execution time	Memory
886533		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	24 / 100	2073 ms	26224 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
using namespace std;
typedef long long ll;

int main(){
	int n;
	cin >> n;
	vector<ll> L(n), X(n);
	for(int i = 0; i < n; i++)
		cin >> X[i];
	for(int i = 0; i < n; i++)
		cin >> L[i];
	vector<pair<ll, ll>> G(n);
	for(int i = 0; i < n; i++){
		G[i] = make_pair(L[i], X[i]);
	}
	sort(all(G));

	bool constant = 1;
	for(int i = 1; i < n; i++){
		if(L[i] != L[i-1]) constant = 0;
	}
	if(constant){
		

		priority_queue<ll> vals;
		ll score = 0, ans = 0;
		for(int i = 0; i < n; i++){
			auto [Li, Xi] = G[i];
			if(score <= Li){
				vals.push(Xi);
				score += Xi;
				ans++;
			}
			else if(vals.top() > Xi){
				score -= vals.top(); vals.pop();
				score += Xi; vals.push(Xi); 
			}
		}
		cout << ans << endl;
	}
	else{
		vector<int> perm(n);
		iota(all(perm), 0);
		int ok = 1;
		int cev = 0;
		while(ok){
			int score = 0, ans = 0;
			for(int cur = 0; cur < n; cur++){
				int i = perm[cur];
				auto [Li, Xi] = G[i];
				if(score <= Li){
					score+=Xi;
					ans++;
				}
			}
			cev = max(ans, cev);
			ok = next_permutation(all(perm));
		}

		cout << cev << endl;
	}

}

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