Submission #1162819

#TimeUsernameProblemLanguageResultExecution timeMemory
1162819veehjGym Badges (NOI22_gymbadges)C++20
100 / 100
263 ms16432 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
ll n;
vector<pair<ll, pair<ll, ll>>> xl;
priority_queue<ll> q;

void f() {
  ll n;
  cin >> n;
  xl.resize(n);
  for (auto& u : xl) cin >> u.se.fi; 
  for (auto& u : xl){ cin >> u.se.se; u.fi=u.se.fi+u.se.se; }
  sort(all(xl));
  ll ans=0, curr=0;
  for(ll i=0; i<n; i++){
    if(xl[i].se.se >= curr){
      curr+=xl[i].se.fi;
      q.push(xl[i].se.fi);
      ans++;
    } else {
      if(q.empty()) continue;
      if(q.top() <= xl[i].se.fi) continue;
      if(curr-q.top() > xl[i].se.se) continue;
      curr-=q.top();
      ans--;
      q.pop();
      if(xl[i].se.se >= curr){
        curr+=xl[i].se.fi;
        q.push(xl[i].se.fi);
        ans++;
      } 
    }
  }
  cout << ans;
}

int main() {
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; i++) {
    // cout << '#' << i << endl;
    f();
    if (i != tc) cout << endl;
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...