Submission #1190437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190437		dzuizz	Gym Badges (NOI22_gymbadges)	C++20	100 / 100	116 ms	16424 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N=500000;
int x[N],l[N],ord[N];
priority_queue<int> pq;
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n; cin>>n;
  for(int i=0;i<n;++i) cin>>x[i];
  for(int i=0;i<n;++i) cin>>l[i];
  iota(ord,ord+n,0);
  sort(ord,ord+n,[&](const int&a,const int&b){
    return x[a]+l[a]<x[b]+l[b];
  });
  for(int i=0,r=0;i<n;++i){
    if(r<=l[ord[i]]){
      r+=x[ord[i]];
      pq.emplace(x[ord[i]]);
    }else if(pq.size()&&pq.top()>x[ord[i]]){
      r+=x[ord[i]]-pq.top();
      pq.pop(); pq.emplace(x[ord[i]]);
    }
  }
  cout<<pq.size()<<'\n';
  return 0;
}

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