Submission #942309

#TimeUsernameProblemLanguageResultExecution timeMemory
942309vjudge1Gym Badges (NOI22_gymbadges)C++17
9 / 100
149 ms25124 KiB
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	vector<pair<int, int>> v(N);
	for(int i = 0; i < N; i++) cin >> v[i].second;
	for(int i = 0; i < N; i++) cin >> v[i].first;
	sort(v.begin(), v.end());
	multiset<int> hv;
	int margin = 0;
	int lvl = 0;
	for(pair<int, int>& p : v){
		int L = p.first;
		int X = p.second;
		if(lvl <= L){
			margin = max(margin - X, L - lvl);
			lvl += X;
			hv.insert(X);
		}else if(margin >= X){
			margin = min(margin - X, L - lvl);
			lvl += X;
			hv.insert(X);
		}else{
			int mx = *hv.rbegin();
			if(mx > X){
				hv.erase(hv.find(mx));
				lvl -= mx;
				margin += mx;
				if(lvl <= L){
					margin = max(margin - X, L - lvl);
					lvl += X;
					hv.insert(X);
				}else if(margin >= X){
					margin = min(margin - X, L - lvl);
					lvl += X;
					hv.insert(X);
				}
			}
		}
	}
	cout << (int)hv.size() << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...