Submission #1314241

#TimeUsernameProblemLanguageResultExecution timeMemory
1314241namhhGym Badges (NOI22_gymbadges)C++20
100 / 100
123 ms12224 KiB
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 5e5+5;
int n,x[N],l[N];
vector<pii>v;
priority_queue<int>pq;
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> x[i];
	for(int i = 1; i <= n; i++) cin >> l[i];
	for(int i = 1; i <= n; i++) v.push_back({x[i]+l[i],i});
	sort(v.begin(),v.end());
	int ans = 0;
	int cnt = 0;
	for(int i = 0; i < v.size(); i++){
		int id = v[i].se;
		if(ans <= l[id]){
			ans += x[id];
			pq.push(x[id]);
			cnt++;
		}
		else if(x[id] < pq.top()){
			ans -= pq.top();
			ans += x[id];
			pq.pop();
			pq.push(x[id]);
		}
	}
	cout << cnt;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...