0564.cpp

#include <cstdio>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;
  
int n;
pair<int, long long int> microbe[300000]; // 微生物の値(b, a)のpair

/*
    k個の微生物をシャーレに入れられるか判定する。
    シャーレに入れられるかどうかは、
    選んだk個の微生物のaの値、bの値の集合をal, blとして、
    sum(al)/k <= min(bl) ⇔  sum(al) <= k * min(bl)が成り立つかで分かる。
    今、微生物を配列microbeの区間[0, t]からk個選ぶ時、
    microbeはbの値で降順に並べられているから、
    任意のblについてmin(bl) >= b(t)である。
    ∴ sum(al) <= k * b(t) <= k * min(bl) ー ①
        または k * b(t) <= sum(al) <= k * min(bl) ー ②
            が成り立つのは自明
    ここで、② が成り立つとき、それはb(t)∉blであることを意味していて、
    [0, t]より小さな区間[0, s](k-1 <= s <= t-1)を予め考えていた時、
    その区間において既に① が成り立っているはずである。
    よって、区間[0, t]について① のみを考えれば良い。
    次にalについて、「sum(al)が最小となるal」をminalと定義した時、
    minalで① が成り立たないならば、任意のalについて① は成り立たない。
    以上から
    区間[0, t]でminalとb(t)と比較することをk-1 <= t <= n-1の範囲で繰り返せば良いことが分かる。
    今、[0, t]におけるminalをsetで管理しているなら、
    [0, t+1]におけるminalはsetにa(t+1)を追加した上で
    set内の最も大きい値を1つ削除すれば求まる。
    よって、setへの挿入、削除をn-k+1回繰り返すからO(nlogn)である。
 */
int check(int k) {
     long long int sum = 0; // sum(minal)
     set<long long int, greater<long long int> > order; // aを降順に並べる
   
     if (k == 0) return 1; // k=0の時常に成立
  
     /* とりあえず[0, k-1]におけるalは1通りしかないので
        sum(al)を求めて、これをsetで管理する */
     for (int i=0; i<k; i++) {
          sum += microbe[i].second;
          order.insert(microbe[i].second);
     }
     if (sum <= k*microbe[k-1].first) return 1; // 既に不等式が成り立つなら1を返す
  
     /* k <= t <= n-1について考える */
     for (int i=k; i<n; i++) { 
          /* [0, t]におけるsum(minal)を求める */
          sum += microbe[i].second;
          order.insert(microbe[i].second);
          sum -= *order.begin();
          order.erase(order.begin());
           
          if (sum <= k*microbe[i].first) return 1; //不等式が成り立つなら1を返す
     }
     return 0; //全てのtで成り立たないなら0を返す
}
  
int main() {
     int high;
     int low;

     scanf("%d", &n);
     for (int i=0; i<n; i++) {
           long long int a;
           int b;

           scanf("%lld %d", &a, &b);
           microbe[i] = make_pair(b, a); //b, aの順にpairにする
     }
     sort(microbe, microbe+n, greater<pair<int, long long int> >()); //bで降順にソート
  
     /* 区間(-1, n+1) ⇔  [0, n]をcheck関数で二分探索 */
     low = -1;
     high = n+1;
     while (high-low > 1) {
          int mid = (low+high)/2;
          if (check(mid)) low = mid;
          else high = mid;
     }
     printf("%d\n", low);
}