Submission #1157283

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;

bool check(const vector<int>& A, int k) {
  int N = A.size();
  ll tmp = 0LL;
  REP(i,k + 1) tmp += A[i];
  for(int i = k + 1; i < N; ++i) {
    if(tmp * 2 >= A[i]) {
      tmp += A[i];
    }else{
      return false;
    }
  }
  return true;
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i,N) cin >> A[i];
  sort(ALL(A));

  int lb = 0, ub = N;
  while(ub - lb > 1) {
    int mid = (lb + ub) / 2;
    if(check(A, mid)) ub = mid;
    else lb = mid;
  }
  int res;
  if(check(A, lb)) {
    res = N - lb;
  }else{
    res = N - ub;
  }
  cout << res << endl;
  return 0;
}

Submission Info

Judge Result