Submission #1103963

#TimeUsernameProblemLanguageResultExecution timeMemory
11039630pt1mus23Gym Badges (NOI22_gymbadges)C++14
100 / 100
134 ms26400 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 5e5 +23, inf = LLONG_MAX, LL = 30;

void rush(){
    int n;
    cin>>n;

    vector<pair<int,pair<int,int>>> lst(n);

    int ans=0;
    for(int i=0;i<n;i++){
        cin>>lst[i].second.second;
    }
    for(int i=0;i<n;i++){
        cin>>lst[i].second.first;
        lst[i].first = lst[i].second.first + lst[i].second.second;
    }
    sort(all(lst));

    int gain =0;
    priority_queue<int> q;
    for(auto v:lst){
        int a = v.second.first;
        int b = v.second.second;
        // cout<<a<<" "<<b<<" => "<<gain<<endl;
        if(gain<=a){
            gain+=b;
            ans++;
            q.push(b);
        }
        else if(!q.empty() && q.top()>b){
            gain -= q.top();q.pop();
            gain += b;
            q.push(b);
        }
    }



    putr(ans);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    // cin>>tt;
    while(tt--){
        rush();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...