Problem:


Score : 400 points

Problem Statement

Snuke found N strange creatures.
Each creature has a fixed color and size. The color and size of the i-th creature are represented by i and A_i, respectively.

Every creature can absorb another creature whose size is at most twice the size of itself.
When a creature of size A and color B absorbs another creature of size C and color D (C \leq 2 \times A), they will merge into one creature of size A+C and color B.
Here, depending on the sizes of two creatures, it is possible that both of them can absorb the other.

Snuke has been watching these creatures merge over and over and ultimately become one creature.
Find the number of the possible colors of this creature.

Constraints

2 \leq N \leq 100000

1 \leq A_i \leq 10^9

A_i is an integer.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N

Output

Print the number of the possible colors of the last remaining creature after the N creatures repeatedly merge and ultimately become one creature.

Sample Input 1

3
3 1 4

Sample Output 1

2

The possible colors of the last remaining creature are colors 1 and 3.
For example, when the creature of color 3 absorbs the creature of color 2, then the creature of color 1 absorbs the creature of color 3, the color of the last remaining creature will be color 1.

Sample Input 2

5
1 1 1 1 1

Sample Output 2

5

There may be multiple creatures of the same size.

Sample Input 3

6
40 1 30 2 7 20

Sample Output 3

4



Sample input:
3
3 1 4


Sample output:
2

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n = int(input())
a = sorted(list(map(int, input().split())))

ruiseki = [0 for i in range(n)]
for i in range(n):
    if i == 0:
        ruiseki[i] = a[i]
    else:
        ruiseki[i] = a[i] + ruiseki[i - 1]
# print("ruiseki =", ruiseki)

ans = 1
for i in reversed(range(n - 1)):
    if ruiseki[i] * 2 < a[i + 1]:
        break
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = sorted([int(a) for a in input().split()])

res = 0
size = 0
for i in range(n-1):
    size += arr[i]
    if arr[i+1] > size * 2:
        res = 0
    else:
        res += 1
res += 1

print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
cnt=0
ans=1
for i,a in enumerate(A):
  #print(cnt,ans,a)
  if cnt*2>=a:    
    ans+=1
  else:
    ans=1
  cnt+=a
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()
A.sort()

cusum = [0]*N
cusum[0] = A[0]
for i in range(1,N):
    cusum[i] = cusum[i-1]+A[i]

lim = 0
for i in range(N-1)[::-1]:
    if cusum[i]*2 < A[i+1]:
        lim = i+1
        break

print(N-lim)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = np.array(read().split(), np.int64)[1:]

A.sort()
Acum = A.cumsum()

ng = Acum[:-1] * 2 < A[1:]
ng = np.logical_or.accumulate(ng[::-1])[::-1]
x = (~ng).sum() + 1
print(x)

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
a = list(map(int, input().split()))
a.sort()
total = [0] * n
total[0] = a[0]
for i in range(1, n):
    total[i] = a[i] + total[i - 1]
ans = 1
for i in range(n - 1, 0, -1):
    if a[i] <= total[i - 1] * 2:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
size=a[0]
num=1
for i in a[1:]:
  if size*2>=i:
    num+=1
  else:
    num=1
  size+=i
print(num)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AtoZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
L = IL()
L.sort()

i = 0
now = 0
flag = 0
while i<N:
  now += L[i]
  if i != N-1:
    if now*2 < L[i+1]:
      flag = i+1
  i += 1
  
  
print(N-flag)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from itertools import accumulate


def can_survive(prev):
    while True:
        idx = bisect_right(A, 2 * acc_A[prev]) - 1
        if idx == N - 1:
            return True
        if idx == prev:
            return False
        prev = idx


def binary_search(left, right):
    while right - left > 1:
        mid = (left + right) // 2
        if can_survive(mid):
            right = mid
        else:
            left = mid
    return left if can_survive(left) else right


N = int(input())
A = sorted(map(int, input().split()))
acc_A = list(accumulate(A))
print(N - binary_search(0, N))

Submission status: Accepted

Solution code:
from bisect import bisect_right
from itertools import accumulate


N = int(input())
A = sorted(map(int, input().split()))
acc_A = list(accumulate(A))
ans = 0
for i in range(N):
    prev = i
    while True:
        idx = bisect_right(A, 2 * acc_A[prev], lo=prev) - 1
        if idx == N - 1:
            ans += 1
            break
        if idx == prev:
            break
        prev = idx
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from itertools import accumulate


N = int(input())
A = sorted(map(int, input().split()))
acc_A = list(accumulate(A))
ans = 0
for i in range(N):
    prev = i
    while True:
        idx = bisect_right(A, 2 * acc_A[prev]) - 1
        if idx == N - 1:
            ans += 1
            break
        if idx == prev:
            break
        prev = idx
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    size = A[0]
    ret = 1
    for i in range(1, N):
        if A[i]<=2*size:
            size += A[i]
            ret += 1
        else:
            size += A[i]
            ret = 1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
L.sort()

from itertools import accumulate
li = list(accumulate(L))

cnt = 0
flag = False
for i in range(n-1):
    if li[i]*2 >= L[i+1]:
        flag =True
        cnt +=1
    else:
        flag =False
        cnt = 0
print(cnt+1)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))

ans = -1
for i in range(n-1):
    if a[i]*2 < a[i+1]:
        ans = i
    a[i+1] += a[i]
print(n-ans-1)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
imp = -1
size = 0

for i in range(n-1):
    size += a[i]
    if size*2 < a[i+1]:
        imp = i

print(n-imp-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_left

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    # print(A)
    ans = -1
    for i in range(N-1):
        if A[i]*2 < A[i+1]:
            ans = i
        A[i+1] += A[i]
    print(N-ans-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
c=[0]
for i in range(n):
    c.append(c[i]+a[i])
p=[0 for i in range(n)]
for i in range(n):
    if c[i]*2<a[i]:
        p[i]=1
for i in range(n):
    if p[n-i-1]:
        print(i+1)
        break
#print(a,c,p,sep='\n')

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = sorted(list(map(int,input().split())))
a2 = list(accumulate([2*i for i in a]))
l= [i+1 for i in range(n)]
#print(a)
#print(a2)
t = 0
for j,k,i in zip(a[1:],a2,l):
  if k<j:
    t = i
print(n-t)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

outs = -1
c = 0
for i in range(n-1):
    c += arr[i]
    if 2*c < arr[i+1]:
        outs = i

if outs >= 0:
    print(n - 1 - outs)
else:
    print(n)

Submission status: Accepted

Solution code:
def count(l):
    res = {}
    for d in l:
        if d in res:
            res[d] += 1
        else:
            res[d] = 1
    return res
n = int(input())
data = list(map(int, input().split()))
cnt = count(data)
monsters = sorted(cnt.keys())
total = sum(data)
ans = n
idx = len(monsters)-2
while idx >= 0:
    prev = monsters[idx+1]
    total -= prev*cnt[prev]
    if total*2 < prev:
        break
    idx -= 1
out = 0
while idx >= 0:
    m = monsters[idx]
    out += cnt[m]
    idx -= 1

ans -= out 
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=list(map(int, input().split()))
A=sorted(A, reverse=True)

#print(now) #普通に全部食える


cum=np.cumsum(A[::-1])[::-1]
adds=[-1]*(N)
adds[0]=cum[0]
for i in range(1,N):
    if cum[i]*2>=A[i-1]:
        adds[i]=adds[i-1]
    else:
        adds[i]=cum[i]
#print(A)
#print(cum)
#print(adds)
adds=np.array(adds)
ans=(adds==cum[0]).sum()

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_right

N = int(input())
*A, = map(int, input().split())
A.sort()

ac = [0]*(N+1)
for i in range(1, N+1):
    ac[i] = ac[i-1]+A[i-1]
ans = 0
for i in A:
    bef = bisect_right(A, i*2)
    aft = bisect_right(A, ac[bef]*2)
    while bef!=aft:
        v = ac[aft]
        bef = aft
        aft = bisect_right(A, ac[aft]*2)
    ans += int(aft==N)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A):
    A.sort()
    # Aの左側をすべて取り込む (S[x-1])
    # Aの右側を取り込めるところまで取り込む
    S = list(accumulate(A))
    ans = 1
    for i in range(N-2, -1, -1):
        if S[i] * 2 >= A[i+1]:
            ans += 1
        else:
            break
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(map(int, input().split()), reverse=True)
total = sum(a)

ans = 1
for x in a:
    total -= x
    if x > total * 2:
        break
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    A.sort()
    acc = list(accumulate(A))
    
    ans = N
    for i in range(N - 2, -1, -1):
        if 2 * acc[i] < A[i + 1]:
            ans -= i + 1
            break
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
size = 0
r = 0
ans = 0
for l in range(N):
    if l == r:
        r += 1
        size += A[l]
    while r < N and size * 2 >= A[r]:
        size += A[r]
        r += 1
    if r == N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()
size = A[0]
r = 1
ans = 0
for l in range(N):
    if l == r:
        r += 1
        size += A[l]
    while r < N and size * 2 >= A[r]:
        size += A[r]
        r += 1
    if r == N:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def m():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    B = [0] * N
    B[0] = A[0]
    for i in range(1, N):
        B[i] = B[i - 1] + A[i]
    prob = 0
    for i in range(N - 1):
        if B[i] * 2 < A[i + 1]:
            prob = 0
            continue
        prob += 1
    return prob+1


print(m())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
sm = []
sm.append(a[0])
for i in range(1,n):
    sm.append(sm[-1]+a[i])
num = 0
for i in range(1,n):
    if sm[i-1] * 2 < a[i]:
        num = i
        
print(n - num)

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
A = sorted(A,reverse = True)
total = sum(A)
cnt = 1
for i in range(n):
    total -= A[i]
    if 2 * total >= A[i]:
        cnt += 1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
# B - Colorful Creatures
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
ans = 1
num = sum(A)
for i in range(0,N-1):
    num -= A[i]
    if num*2<A[i]:
        break
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

N = int(input())
A = list(map(int,input().split()))
A.sort()
B = list(itertools.accumulate(A))
jdg = 0

for i in range(1,N):
    if A[i] > B[i-1]*2:
        #print(A[i],B[i-1])
        jdg = i
print(N-jdg)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()

cum = [0] * (n + 1)

for i in range(1, n + 1):
    cum[i] = cum[i - 1] + a[i - 1]

ans = 1

for i in range(n, 0, -1):
    if cum[i - 1] * 3 >= cum[i]:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L = sorted(map(int, input().split()))
S = [0] * n
S[0] = L[0]
cnt = 1
for i in range(n-1):
    S[i+1] = S[i] + L[i+1]
    if L[i+1] <= 2 * S[i]:
        cnt += 1
    else:
        cnt = 1
print(cnt)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
b=[0]
for i in a:
    b+=[i+b[-1]]
for i in range(n+1)[::-1]:
    if b[i]/3>b[i-1]:
        print(n-i+1)
        break

Submission status: Accepted

Solution code:
n = int(input())
dat = list(map(int, input().split()))
dat.sort()
total = 0
ind = 0
for i in range(n-1):
    total += dat[i]
    if total * 2 < dat[i+1]:
        ind = i+1
print(n-ind)

Submission status: Accepted

Solution code:
import numpy as np 
n = int(input())
size_ls = list(map(int, input().split()))
size_ls.sort()
csum_size = list(np.cumsum(size_ls))

can_ls = [0] * n
can_ls[-1] = 1
for i in range(n-1):
    if 2 * csum_size[i] >= size_ls[i+1]:
        can_ls[i] = 1
ans = 0
for i in range(n-1,-1,-1):
    if can_ls[i] != 1:
        break
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a.sort()

    idx = 0

    tmp_size = a[0]
    for i in range(1, n):
        if tmp_size < (a[i] + 1) // 2:
            idx = i
        tmp_size += a[i]

    print(n - idx)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()
    a = na()

    a.sort()

    idx = 0

    tmp_size = a[0]
    for i in range(1, n):
        if tmp_size >= (a[i] + 1) // 2:
            tmp_size += a[i]
            continue
        else:
            tmp_size += a[i]
            idx = i

    print(n - idx)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a,reverse=True)
sm=sum(a)
ans=1
pas=a[0]
for i in range(1,n):
    if a[i-1]>(sm-pas)*2:
        break
    ans += 1
    pas += a[i]
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys

n = int(input())
arr = np.array(list(map(int, input().split())))

arr.sort()
arr_cs = arr.cumsum()

ans = 0
for i in range(n - 1):
    if arr_cs[i] * 2 < arr[i + 1]:
        ans = i + 1
else:
    print(n - ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    a = sorted(A)
    asum = [0]*N
    asum[0]=a[0]
    for x in range(1, N):
        asum[x] = asum[x-1]+a[x]
    
    stop = -1
    for i in range(N-1):
        if asum[i] * 2 < a[i+1]:
            stop = i
    print(N-stop-1)


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(map(int,input().split()))

cum=[0]*(n+1)
for i in range(n):
    cum[i+1]=cum[i]+a[i]
ans=1
for i in reversed(range(n-1)):
    if cum[i+1]*2<a[i+1]:
        break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))

a = [0]*(N+1)

for i in range(N):
    a[i+1] = a[i]+A[i]

A.reverse()
a.reverse()
# print(A)
# print(a)

ans = 1
for i in range(N):
    if A[i]/2 > a[i+1]:
        break
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
s=[0]*n
s[0]=a[0]
for i in range(1,n):
  s[i]=s[i-1]+a[i]
ans=1
for i in range(1,n)[::-1]:
  if s[i-1]>=(a[i]+1)//2:
    ans+=1
  else:
    break
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
K = sorted(map(int,input().split()))
A = list(accumulate(K))
ans = 1
for i in range(n-2,-1,-1):
    if A[i]*2 >= K[i+1]:
        ans += 1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ns = sorted(list(map(int, input().split())))
cnt = 0
cum = [0]
for i in ns:
    cum.append(i + cum[-1])
for i in range(n):
    if cum[i] * 2 >= ns[i]:
        cnt += 1
    else:
        cnt = 0
print(cnt+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
a.sort()
idx = 0
tmp = a[0]
for i in range(1, n):
    if tmp * 2 < a[i]:
        idx = i  # ここで併合できなくなり、i 以上しか無理になる
    tmp += a[i]
print(n - idx)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int,input().split())))
ans = 0
buf = 0
for i in range(n-1):
    buf += a[i]
    if buf*2>=a[i+1]:
        ans += 1
    else:
        ans = 0
print(ans+1)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))

a.sort()

#2倍以下なら吸える
#3,1,4
#→3,4

suma=0
cnt=0
for i in range(n-1):
    suma+=a[i]
    if a[i+1]<=2*suma:
        cnt+=1
    else:
        cnt=0
    

print(cnt+1)

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]

    A.sort()

    impossible_num = 0
    ruiseki = 0

    for i, a in enumerate(A):
        if i == N - 1:
            continue
        ruiseki += a
        if A[i + 1] > ruiseki * 2:
            impossible_num = i + 1

    print(N - impossible_num)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
l= list(map(int,input().split()))
l.sort()
S=0
ans=0
for i in range(N-1):
   S+=l[i]
   if S*2<l[i+1]:
      ans=i+1
print(N-ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
A = list(map(int, input().split()))

A.sort()
num = 1
B = list(itertools.accumulate(A))
for i, a in enumerate(A[1:]):
    if B[i]*2 < a:
        num = 1
    else:
        num += 1
print(num)

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
a = sorted(list(map(int, input().split())))
asum = list(accumulate(a))

cnt= 1
for i in range(1,n):
    if asum[i - 1] * 2 >= a[i]:
        cnt += 1
    else:
        cnt = 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
cum_a = [a[0]]
for i in range(1, n):
    cum_a.append(cum_a[i-1]+a[i])
res = 0
for i in range(1, n):
    if cum_a[i-1]*2 < a[i]:
        res = i

print(n-res)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
c = list(map(int,input().split()))
c.sort()
ac = list(itertools.accumulate(c))
check = [1]*n
for i in range(n-1):
    if ac[i]*2<c[i+1]:
        check[i] = -1
    else:
        check[i] = 1
tmp=0
for i in range(n):
    if check[i]==1:
        tmp+=1
    else:
        tmp =0
print(tmp)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))

A.sort()

acum = 0
ans = 0
for i in range(N-1):
    acum += A[i]
    if acum * 2 >= A[i+1]:
        ans += 1
    else:
        ans = 0

print(ans+1)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()

cs_a = [0] * n
cs_a[0] = a[0]
for i in range(n-1):
    cs_a[i+1] = cs_a[i] + a[i+1]

ans = 0
for i in range(n-1):
    if a[i+1] <= cs_a[i] * 2:
        ans += 1
    else:
        ans = 0

print(ans+1)

Submission status: Accepted

Solution code:
def agc011_b():
    N = int(input())
    A = sorted([0] + list(map(int, input().split())))

    cumsum = [0]
    for i in range(1, N+1):
        cumsum.append(cumsum[-1] + A[i])

    ans = 1
    for i in range(N-1, 0, -1):
        if cumsum[i] * 2 < A[i+1]:
            break  # 2倍しても次に小さい個体を吸収できないので、これ以下は生き残れない
        else:
            ans += 1
    print(ans)

agc011_b()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate


def solve(N: int, A: "List[int]"):
    least = 0
    A.sort()
    acc = list(accumulate(A))
    for i, a in enumerate(A):
        if i == N - 1:
            print(N - least)
            break
        if A[i+1] > 2 * acc[i]:
            least = i + 1
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
rui = [a[0]]
for i in range(1, n):
    rui.append(rui[i-1] + a[i])
col = [1 for i in range(n)]
for i in range(n-1):
    if 2*rui[i] < a[i+1]:
        col[i] = 0
ans = 0
for i in range(n-1, -1, -1):
    if col[i] == 1:
        ans += 1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
a = np.array(a)
c = np.array([0]*n)
np.cumsum(a,out=c)
ans = n
for i in range(n-1,0,-1):
  if c[i-1]*2 < a[i]:
    ans -= i
    break
print(ans)