Submission #886677

#	Time	Username	Problem	Language	Result	Execution time	Memory
886677		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	351 ms	33944 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<array<ll, 3>> G(n);
	for(int i = 0; i < n; i++){
		G[i] = {L[i] + X[i], L[i], X[i]};
	}
	sort(all(G));

	priority_queue<ll> vals;
	ll score = 0, ans = 0;
	for(int i = 0; i < n; i++){
		auto [a, 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;

}

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