제출 #1314644

#제출 시각아이디문제언어결과실행 시간메모리
1314644joshjuiceGym Badges (NOI22_gymbadges)C++20
100 / 100
139 ms12472 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;

#define ppf pop_front
#define ppb pop_back
#define pf push_front
#define pb push_back
#define ef emplace_front
#define eb emplace_back
#define fr first
#define sc second
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define sr(a) sort(all(a))
#define sz(a) a.size()
#define lbv(a, x) lb(all(a), x)
#define ubv(a, x) ub(all(a), x)
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)

const ll INF1 = 1e18;
const ll INF2 = 1e15;
const ll INF3 = 1e14;
const ll XMIN = -1e9, XMAX = 1e9;
const ll LMIN = LLONG_MIN, LMAX = LLONG_MAX;
const int IMIN = INT_MIN, IMAX = INT_MAX;

bool comp(pll a, pll b) {
  if (a.fr+a.sc == b.fr+b.sc) return a.fr < b.fr;
  return a.fr+a.sc < b.fr+b.sc;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n;
  cin >> n;
  vector<pll> a(n);
  pqll pq;
  ll ans = 0, cur = 0;
  rep(i, 0, n) cin >> a[i].fr;
  rep(i, 0, n) cin >> a[i].sc;
  sort(all(a), comp);
  rep(i, 0, n) {
    if (cur <= a[i].sc) {
      ans++;
      cur += a[i].fr;
      pq.push(a[i].fr);
    } else if (a[i].fr < pq.top()) {
      cur += a[i].fr-pq.top();
      pq.pop();
      pq.push(a[i].fr);
    }
  }
  cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...