Submission #942309

#	Time	Username	Problem	Language	Result	Execution time	Memory
942309		vjudge1	Gym Badges (NOI22_gymbadges)	C++17	9 / 100	149 ms	25124 KiB

Main

#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";
}

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