Submission #833027

#	Time	Username	Problem	Language	Result	Execution time	Memory
833027		NK_	Gym Badges (NOI22_gymbadges)	C++17	100 / 100	358 ms	36684 KiB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);

int main() {
	cin.tie(0)->sync_with_stdio(0);
  	
	int N; cin >> N;

	vi A(N); for(auto& x : A) cin >> x;
	vi B(N); for(auto& x : B) cin >> x;

	vi ord(N); iota(begin(ord), end(ord), 0);
	sort(begin(ord), end(ord), [&](int x, int y) {
		if ((A[x]+B[x]) == (A[y]+B[y])) return B[x] < B[y];
		return (A[x]+B[x]) < (A[y]+B[y]);
	});

	multiset<int> S; int ans = 0; ll sum = 0;
	for(auto i : ord) {
		if (B[i] >= sum) ans++;
		S.insert(A[i]); sum += A[i];

		while(sz(S) > ans) {
		 	sum -= *rbegin(S);
		 	S.erase(prev(end(S)));
		}
	}

	cout << ans << nl;

    return 0;	
} 	

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