Submission #1185498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185498		NotLinux	Gym Badges (NOI22_gymbadges)	C++20	24 / 100	94 ms	12476 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
void solve(){
    int n;
    cin >> n;
    pair<int,int>arr[n];// level cap , rating gain
    for(int i = 0;i<n;i++)cin >> arr[i].second;
    for(int i = 0;i<n;i++)cin >> arr[i].first;
    sort(arr , arr + n , [&](auto a , auto b){
    	return a.first + a.second < b.first + b.second;
    });
    int sum = 0;
    priority_queue<int>pq;
    for(int i = 0;i<n;i++){
    	if(sum <= arr[i].first){
    		sum += arr[i].second;
    		pq.push(arr[i].second);
    	}
    	else{
    		if(!pq.empty() and pq.top() > arr[i].second and sum - pq.top() + arr[i].second <= arr[i].first){
    			sum -= pq.top();
    			pq.pop();
    			sum += arr[i].second;
    			pq.push(arr[i].second);
    		}
    	}
    }
    cout << sz(pq) << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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