Submission #1185457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185457		epicci23	Gym Badges (NOI22_gymbadges)	C++20	100 / 100	114 ms	12488 KiB

Main

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;

void _(){
  int n;
  cin >> n;
  vector<array<int,2>> v(n);
  for(int i=0;i<n;i++) cin >> v[i][0];
  for(int i=0;i<n;i++) cin >> v[i][1];
  sort(all(v),[&](array<int,2> a,array<int,2> b){
    return a[0] + a[1] < b[0] + b[1];
  });

  priority_queue<int> pq;
  int tot = 0;
  for(int i=0;i<n;i++){
  	//cout << v[i][0] << ' ' << v[i][1] << ' ' << tot << '\n';
  	if(tot <= v[i][1]){
  	  tot += v[i][0];
  	  pq.push(v[i][0]);
  	  continue;
  	}
  	if(!pq.empty() && v[i][0] < pq.top()){
  	 tot -= pq.top();
  	 pq.pop();
  	 tot += v[i][0];
     pq.push(v[i][0]);
  	}
  }

  cout << sz(pq) << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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