Submission #1369505

#TimeUsernameProblemLanguageResultExecution timeMemory
1369505gohchingjaykGym Badges (NOI22_gymbadges)C++20
100 / 100
89 ms12484 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

using namespace std;

using ll = long long;

#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int INF = 1e18 + 5;
constexpr int MAXN = 500000 + 5;
constexpr int MOD = 1e9 + 7;

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	
	int N; cin >> N;
	vector<ii> gyms(N);
	for (int i = 0; i < N; ++i) cin >> gyms[i].second;
	for (int i = 0; i < N; ++i) cin >> gyms[i].first;
	
	sort(gyms.begin(), gyms.end(), [](const ii &a, const ii &b) {
		return b.first - a.second > a.first - b.second;
	});
	int taken = 0;
	int lvl = 0;
	priority_queue<int> regret;
	for (int i = 0; i < N; ++i) {
		if (lvl <= gyms[i].first) {
			taken++;
			lvl += gyms[i].second;
			regret.emplace(gyms[i].second);
		}
		else if (!regret.empty() && lvl - regret.top() <= gyms[i].first && regret.top() > gyms[i].second) {
			lvl -= regret.top(); regret.pop();
			lvl += gyms[i].second; regret.emplace(gyms[i].second);
		}
	}
	
	cout << taken;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...