Submission #1516041

---

Source Code Expand

// 簡易競プロテンプレ
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n; ll a[114514], s[114514];

bool ok(int m){
 if (m<0) return false;
 if (m>=n) return true;
 ll w = s[m+1];
 for(int i=m+1;i<n;i++){
  if (w * 2 < a[i]) return false;
  w += a[i];
 }
 return true;
}
int main(void){
 cin >> n;
 for(int i=0;i<n;i++) cin >> a[i];
 sort(&a[0], &a[n]);
 for(int i=0;i<n;i++) s[i+1] = s[i] + a[i];

 int mini = 0, maxi = n, med;
 while(1){
  med = (mini + maxi + rand()%2)/2;
  if (ok(med-1)) {maxi = med-1;}
  else if (!ok(med)) {mini = med+1;}
  else break;
 }
 cout << med << endl;
 return 0;
}

Submission Info

Judge Result