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:
def main():
    N = int(input())
    A = list(map(int,input().split()))

    A.sort()

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

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
numbers = [int(x) for x in input().split()]
numbers.sort()

csum = [0] * (N + 1)

for i in range(N):
  csum[i + 1] = csum[i] + numbers[i]

count = 1  # 一番大きい数は常にOK

for i in range(N - 1, -1, -1):
  if csum[i] * 2 < numbers[i]:
    break
  count += 1
  
print(count)

Submission status: Accepted

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

A = sorted(A)

set_A = set(A)
if len(set_A) == 1:
    print(len(A))
    exit()
    
tmp_slime = A[0]
tmp_flag = True
for i in range(1, len(A)):
    if tmp_slime*2 >= A[i]:
        tmp_slime += A[i]
    else:
        tmp_flag = False
        break
if tmp_flag:
    print(len(A))
    exit()

low = 0
high = len(A)-1
mid = (low + high) // 2
while True:
    tmp = mid
    slime = sum(A[0:mid+1])
    flag = True
    for i in range(mid+1, len(A)):
        if slime*2 >= A[i]:
            slime += A[i]
        else:
            flag = False
            break
    if flag:
        high = mid
        mid = (low + high) // 2
    else:
        low = mid
        mid = (low + high) // 2
    if mid == tmp:
        break
    
print(len(A) - len(A[0:mid+1]))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = sorted([int(_) for _ in input().split()])
    B = [0] * (N+1)
    for i in range(N):
        B[i+1] = A[i]+B[i]
    output = 1
    for i in range(N-1)[::-1]:
        if 2*B[i+1] >= A[i+1]:
            output += 1
            continue
        else: break
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from itertools import accumulate
acc = [0]+a
acc = list(accumulate(acc))

mi = 0
for i in reversed(range(1,n)):
    if acc[i]*2 < a[i]:
        mi = i
        break

print(n-mi)

Submission status: Accepted

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

l = -1
r = n
while r - l > 1:
    m = l + (r-l)//2
    b = a[:]
    b[m] += sum(b[:m])
    flag = 1
    for i in range(m, n-1):
        if b[i+1] <= 2*b[i]:
            b[i+1] += b[i]
        else:
            flag = 0
            break

    if flag == 1:
        r = m
    else:
        l = m


print(n-r)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
def solve(i):
    size = sum(a[:i+1])
    for j in range(i+1, n):
        if a[j]>2*size:
            return False
        size += a[j]
    return True

ok = n-1
ng = -1
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(n-ok)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
def MIIZ(): return list(map(lambda x: x-1, MII()))
## dp ##
def DD2(d1,d2,init=0): return [[init]*d2 for _ in range(d1)]
def DD3(d1,d2,d3,init=0): return [DD2(d2,d3,init) for _ in range(d1)]
## math ##
def to_bin(x: int) -> str: return format(x, 'b') # rev => int(res, 2)
def to_oct(x: int) -> str: return format(x, 'o') # rev => int(res, 8)
def to_hex(x: int) -> str: return format(x, 'x') # rev => int(res, 16)
MOD=10**9+7
def divc(x,y) -> int: return -(-x//y)
def divf(x,y) -> int: return x//y
def gcd(x,y):
    while y: x,y = y,x%y
    return x
def lcm(x,y): return x*y//gcd(x,y)
def enumerate_divs(n):
    """Return a tuple list of divisor of n"""
    return [(i,n//i) for i in range(1,int(n**0.5)+1) if n%i==0]
def get_primes(MAX_NUM=10**3):
    """Return a list of prime numbers n or less"""
    is_prime = [True]*(MAX_NUM+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(MAX_NUM**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, MAX_NUM+1, i): is_prime[j] = False
    return [i for i in range(MAX_NUM+1) if is_prime[i]]
def prime_factor(n):
    """Return a list of prime factorization numbers of n"""
    res = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0: res.append(i); n //= i
    if n != 1: res.append(n)
    return res
## libs ##
from itertools import accumulate as acc, combinations as combi, product, combinations_with_replacement as combi_dup
from collections import deque, Counter
from heapq import heapify, heappop, heappush
from bisect import bisect_left
#======================================================#
def main():
    n = II()
    aa = MII()
    aa.sort()
    c = list(acc([0]+aa))
    c.pop()
    cnt = 0
    for ai, ci in zip(aa, c):
        if ai <= 2*ci:
            cnt += 1
        else:
            cnt = 0
    print(cnt+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n=int(input())
a= list(map(int, input().split()))
a.sort()
aa = list(itertools.accumulate(a))
ans=1

for i in range(n-1):
    if aa[n-2-i]*2>=a[n-1-i]:
        ans+=1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
As.sort()
from itertools import accumulate
cum = list(accumulate(As))
cnt = 0
for n in range(N-1):
    if cum[n]*2>=As[n+1]:
        cnt += 1
    else:
        cnt = 0
cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))
fusion = sum(A)
ans = 1
A.sort()

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

print(ans)

Submission status: Accepted

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

for i in range(N-1):
    sums.append(sums[-1] + A[i])

sums = list(reversed(sums))
A = list(reversed(A))

ans = 1
flag = True
for i in range(N):
    if sums[i] * 2 >= A[i] and flag:
        ans += 1
    else:
        flag = False

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort()
S=[0]
for i in range(N):
    S.append(S[i]+A[i])

lose=0
for i in range(N-1):
    if S[i+1]*2<A[i+1]:
        lose=i+1
print(N-lose)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
a = na()

a.sort()
cu = [0] * (n + 1)
for i in range(n):
    cu[i + 1] = cu[i] + a[i]

ans = 1
for i in range(n - 2, -1, -1):
    if cu[i + 1] * 2 >= a[i + 1]:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=sorted(limii())

s = [0]
for i in range(0, n):
    s.append(s[i] + arr[i])

#arr 1 3 4
#s [0, 1, 4, 8]

ans=0

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

Submission status: Accepted

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

creatures.sort()

accumulation = []

for i in range(len(creatures)):
    if i == 0:
        accumulation.append(0)
    else:
        accumulation.append(creatures[i-1]+accumulation[i-1])
        
creatures.reverse()
accumulation.reverse()

ans = 0

for i in range(len(creatures)):
    if i == 0:
        ans += 1
    else:
        if creatures[i-1] > (creatures[i] + accumulation[i])*2:
            break
        else:
            ans += 1
            
print(ans)

Submission status: Accepted

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

A.sort()
from itertools import accumulate
C = [0]+A
C = list(accumulate(C))

def is_ok(x):
    if x == n-1:
        return True
    y = C[x+1]
    flag = True
    for i in range(x+1, n):
        if A[i] > 2*y:
            flag = False
        y += A[i]
    if flag:
        return True
    else:
        return False

if is_ok(0):
    print(n)
    exit()

l = 0
r = n-1
while l+1 < r:
    c = (l+r)//2
    if is_ok(c):
        r = c
    else:
        l = c
print(n-r)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import accumulate
from bisect import bisect_left

n, *a = map(int, read().split())
a.sort()
cumsum = list(accumulate(a))
index = bisect_left(cumsum, a[-1] / 2)
cnt = 0
for (bf, af) in zip(cumsum[:index], a[1:index + 1]):
    cnt += 1
    if bf * 2 < af:
        cnt = 0
print((n - index) + cnt)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    A=[int(_) for _ in input().split()]
    A.sort()
    A_cum=[0]*n
    A_cum[0]=A[0]
    for i in range(1,n):
        A_cum[i]=A_cum[i-1]+A[i]
    for i in range(n-2,-1,-1):
        if 2*A_cum[i]<A[i+1]:
            print(n-1-i)
            break
    else:
        print(n)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc011/tasks/agc011_b
from copy import deepcopy
n = int(input())
nums = [int(i) for i in input().split()]
nums.sort()
cums = deepcopy(nums)
for i in range(1, n):
    cums[i] += cums[i - 1]

t = 1
for i in range(n - 1)[::-1]:
    if nums[i + 1] <= cums[i] * 2:
        t += 1
    else:
        break
print(t)

Submission status: Accepted

Solution code:
N = int(input())
A = sorted(list(map(int, input().split())))
dp = {}
quota = 0
res = 0
size = 0
streak = 1
for i in range(N-1):
  a = A[i]
  size += a
  if A[i+1] <= size*2:
    streak += 1
  else:
    streak = 1

print(streak)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
n=int(input())
a=sorted(map(int,input().split()))
c=0
for i in range(n-1):
    if a[i]*2<a[i+1]:
        c=i+1
    a[i+1]+=a[i]
print(n-c)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
d=[0]*n
d[0]=1
s=[0]*n
s[0]=a[0]

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

Submission status: Accepted

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

ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect

def CS1D(lis): #listを渡す
    ret=[lis[0]]
    for i in range(1,len(lis)):
        ret.append(ret[i-1]+lis[i])
    return ret
  
N=int(input())
A=[int(a) for a in input().split()]
A.sort()
CS=CS1D(A)
ans=0
for i in range(N):
  w=CS[i]
  prev=-1
  while True:
    tmp=bisect.bisect(A,2*w)-1
    if tmp==N-1:
      ans+=1
      break
    if prev==tmp:
      break
    w=CS[tmp]
    prev=tmp
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = sorted([int(x) for x in input().strip().split()])

    def judge(i):
        m = A[i]
        for j, a in enumerate(A):
            if i == j:
                continue
            if a <= 2 * m:
                m += a
            else:
                return False
        return True
    
    l = -1
    r = N
    while l + 1 < r:
        m = (l + r) // 2
        if judge(m):
            r = m
        else:
            l = m
    
    print(N - (l + 1))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy

N = int(input())
A = list(map(int, input().split()))
A.sort()
cum_A = copy.copy(A)

for i in range(N-1):
  cum_A[i+1] += cum_A[i]
#print(cum_A)
t = 0
for i in range(N-1, 0, -1):
  if A[i] <= 2 * cum_A[i-1]:
    t = i-1
  else:
    break
 
print(N-t)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from itertools import accumulate

def ok(x,A,Acum):
    size = Acum[x]
    for creature in A[x + 1:]:
        if creature  <= 2*size:
            size += creature
    if size == Acum[-1]:
        return True
    return False

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    Acum = list(accumulate(A))
    
    l = -1
    r = N
    while r - l > 1:
        mid = (r + l)//2
        if ok(mid,A,Acum):
            r = mid
        else:
            l = mid
    print(N - r)  
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
s=[0]
si=0
for ai in a:
    si+=ai
    s.append(si)
import bisect
ans=0
#色iにたいして2xAi以下の
for ai in a:
    b0=0
    b1=1
    c=ai
    while b0!=b1:
        b0=b1
        b1=bisect.bisect_right(a,2*c)
        c=s[b1]
    if b1==n:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    A.sort()
    ans = 1
    S = sum(A)
    for i in reversed(range(N-1)):
        S -= A[i+1]
        if A[i+1] <= 2*S:
            ans += 1
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A.sort()

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

for i in reversed(range(N-1)):
    if cum[i] * 2 >= A[i+1]:
        continue
    else:
        print(N-1-i)
        break
else:
    print(N)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

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

    tot=0
    maxind=-1
    for i in range(N-1):
        tot+=A[i]
        if tot*2<A[i+1]:
            maxind=i
    print(N-(maxind+1))


resolve()

Submission status: Accepted

Solution code:
N,*A = map(int, open(0).read().split())
A.sort(reverse=True)
s = sum(A)
ans = 1
for i in range(N):
  s -= A[i]
  if 2*s<A[i]:
    break
  ans += 1
print(ans)

Submission status: Accepted

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


# print(A)
# t = 0
# for k in range(1, n):
#     # print("A[0:{}]={}".format(k, A[:k]))
#     # print("{} <? {}".format(2 * sum(A[:k]), A[k]))
#     if 2 * sum(A[:k]) < A[k]:
#         t = max(t, k)

t = 0
value = A[0]
for k in range(1, n):
    # print("A[0:{}]={}".format(k, A[:k]))
    # print("{} <? {}".format(2 * sum(A[:k]), A[k]))
    if 2 * value < A[k]:
        t = max(t, k)
    value += A[k]


print(n - t)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
M = [0] + sorted(list(map(int, input().split())))
C = np.cumsum(M)
#print(M, C)
#2分探索とかでも良さそうだけど
for i in range(N-1, -1, -1):
  #print(M[i], C[i+1])
  if C[i]*2 < M[i+1]:
    #print(i)
    break
print(N-i)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = sorted(list(map(int, input().split())))
    ruiseki = [0] * n
    ruiseki[0] = A[0]
    for i in range(1, n):
        ruiseki[i] = ruiseki[i - 1] + A[i]

    idx = 0
    for i in range(n - 1):
        if ruiseki[i] * 2 < A[i + 1]:
            idx = i + 1

    print(n - idx)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

ind = 0
s = animals[0]
for i, a in enumerate(animals[:-1]):
    if animals[i+1] > 2*s:
        ind = i+1
    s += animals[i+1]
print(n-ind)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()

    ans = N
    while True:
        res = A[0]
        cnt = 1
        flag = False
        for i in range(1, len(A)):
            a = A[i]
            if a > 2 * res:
                ans = min(ans, len(A) - i)
                A = [res + a] + A[i + 1:]
                flag = True
                break
            else:
                res += a
        if flag:
            continue
        else:
            break

    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
U = N
L = -1
while U - L > 1:
    m = (U+L)//2
    x = A[m]
    x1 = A[m]
    f = True
    f1 = True
    for a in A:
        if a == x1 and f1:
            f1 = False
            continue
        if a <= 2 * x:
            x += a
        else:
            f = False
            break
    if f:
        U = m
    else:
        L = m
print(N-U)

Submission status: Accepted

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

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

left=0
for left in range(N-2,-1,-1):
  if B[left]*2>=A[left+1]:
    pass
  else:
    break
else:
  left=-1

num=N-left-1
#print(left)
print(num)

#cnt=0
#for i in range(num,N-1):
#  if A[num]

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

a.sort()

su = 0

po = a[0]

for i in range(1,n):
    if 2 * po < a[i]:
        su = i
    po += a[i]



print(n - su)

Submission status: Accepted

Solution code:
from itertools import accumulate

N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
S = list(accumulate(A))
AS = []
flg = False
count = 0

for i in range(N-1):
  AS.append(S[i]*2 - A[i+1])
for j in range(N-2,-1,-1):
  if AS[j] < 0:
    count = j+1
    break
print(len(A)-count)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
a.sort()
ans = [0]*n
ans[n-1] = 1

su = 0
for i in range(n-1):
    su += a[i]
    if su*2 >= a[i+1]:
        ans[i] = 1
        
aa = 0
for i in range(n-1,-1,-1):
    if ans[i] == 1:
        aa += 1
    else:
        break

print(aa)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
aaa = list(map(int, input().split()))
cnt = Counter(aaa)
aaa_unique = list(set(aaa))
aaa_unique.sort(reverse=True)

rs = sum(aaa)

ans = 0
for a in aaa_unique:
    rs -= a * cnt[a]
    ans += cnt[a]
    if a > 2 * rs:
        break
print(ans)

Submission status: Accepted

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

a.sort()
max_a = a[-1]
ans = 1

l, r = 0, n-1
while r-l > 1:
  key = (r+l)//2
  sub = a[key]
  judge = False
  if sub*2 >= max_a:
    judge = True
  for i in range(n):
    if judge:
      break
    if i == key:
      continue
    if a[i] <= sub*2:
      sub += a[i]
    if sub*2 >= max_a:
      judge = True
      break
  if judge:
    r = key
  else:
    l = key
key = r
if r == n-1 or r == 1:
  sub = a[l]
  judge = False
  if sub*2 >= max_a:
    judge = True
  for i in range(n):
    if judge:
      break
    if i == l:
      continue
    if a[i] <= sub*2:
      sub += a[i]
    if sub*2 >= max_a:
      judge = True
      break
  if judge:
    key = l
print(n-key)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
sum_=[]
total=0
for i in range(n):
    total+=a[i]
    sum_.append(total)
a=sorted(a,reverse=True)
ans=1
max_=a[0]
for i in range(1,n):
    if max_<=a[i]*2:
        ans+=1
        max_=a[i]
    else:
        if max_<=sum_[(n-1)-i]*2: #自分以下の数を吸収
            ans+=1
            max_=a[i]
        else:
            break
print(ans)

Submission status: Accepted

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

A.sort()
import copy
cum = copy.copy(A)
for i in range(1,N):
    cum[i] = cum[i-1]+A[i]

def solve(A,cum,N):
    ans = 1
    for i in range(N-1,0,-1):
        if A[i]<=cum[i-1]*2:
            # print(A[i],cum[i-1])
            ans += 1
        else:
            break
    return ans
print(solve(A,cum,N))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    B = [0]*(N-1)
    B[0] = A[0]
    for i in range(1, N - 1):
        B[i] = B[i - 1] + A[i]
    i = N - 2
    # print(A, B)
    while i >= 0:
        if A[i + 1] <= B[i] * 2:
            i -= 1
        else:
            break
    print(N - i - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
cum_A = A[:]
for i in range(N-1):
  cum_A[i+1] += cum_A[i]
t = 0
for i in range(N-1, 0, -1):
  if A[i] <= 2 * cum_A[i-1]:
    t = i-1
  else:
    break

print(N-t)

Submission status: Accepted

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

cumulative = [0]
A.sort()
for i in range(N):
    cumulative.append(cumulative[i] + A[i])
# print(A)
# print(cumulative)

for i in range(N - 1, 0, -1):
    # print(i)
    if A[i] > cumulative[i] * 2:
        print(N - i)
        break
else:
    print(N)

Submission status: Accepted

Solution code:
import itertools
N = int(input())
A = list(map(int,input().split()))
A.sort()
acum = list(itertools.accumulate(A))

def solve():
    unreachable = None
    for i in range(N-2,-1,-1):
        if 2*acum[i] < A[i+1]:
            unreachable = i
            break
    if unreachable is None:
        return N
    return N - 1 - unreachable

print(solve())

Submission status: Accepted

Solution code:
import bisect

N = int(input())
A = list(map(int,input().split()))
assert len(A) == N
A.sort()
largest = A[-1]

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


def solve():
    unreachable = None
    for i in range(N-2,-1,-1):
        bi = bisect.bisect(A, 2*A[i])
        if 2*acum[bi-1] < A[i+1]:
            unreachable = i
            break
    if unreachable is None:
        return N
    return N - unreachable - 1


print(solve())

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import bisect

N=int(input())

A=list(map(int,input().split()))

A.sort()

sum_A=[]
for item in A:
    if sum_A:
        sum_A.append(sum_A[-1]+item)
    else:
        sum_A.append(item)

ans=0
for i in range(len(A)):
    while i!=len(A):
        index=bisect.bisect_right(A,2*sum_A[i])-1
        if i==index:
            break
        else:
            i=index
    if i==len(A)-1:
        ans+=1

print(ans)

Submission status: Accepted

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

a.sort()
count1=0
count2=0
for i in range(n-1):
    count1+=a[i]
    if 2*count1<a[i+1]:
        count2=i+1
print(n-count2)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cumlsum=[0]*N
su=0
for i in range(N):
    su=su+A[N-1-i]
    cumlsum[N-1-i]=su
#print(A,cumlsum)
cnt=1
for i in range(1,N,1):
    #print(A[i-1],cumlsum[i])
    if A[i-1]/2<=cumlsum[i]:
        cnt=cnt+1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(10 ** 9)


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = list(accumulate(A))
    for i in range(N - 1):
        if B[N - i - 2] * 2 >= A[N - i - 1]:
            continue
        else:
            print(i + 1)
            return
    print(N)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
A.sort()
cumsum = np.cumsum(A)
ans = 1

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#B
from itertools import accumulate

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
accum = list(accumulate(a))

accum.reverse()
a.reverse()
ind = 1
while(ind < n):
    if accum[ind]*2 >= a[ind-1]:
        ind += 1
    else:
        break
    
print(ind)

Submission status: Accepted

Solution code:
N=int(input())
A=sorted(list(map(int,input().split(' '))))
acc=[A[0]]
ans =1
for i in A[1:]:
    acc.append(acc[-1]+i)
for i in range(N-1,0,-1):
    if A[i]>acc[i-1]*2:
        print(N-i)
        exit()
print(N)

Submission status: Accepted

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())))
B=[A[0]]
for i in range(1,n):
  B.append(B[-1]+A[i])
ans=0
j=-1
for i in range(n-1):
  if B[i]*2<A[i+1]:
    ans=ans+i-j
    j=i
print(n-ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc011/tasks/agc011_b

# 色は最後に食ったcreatureになる
# 食って自分の色を残したまま多くなる→小さすぎる生物は食われるしか無い(その色は失われる)
# ソートして、連結していって、連結できなくなった部分はその色に成ることはできない

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


N = read_a_int()
A = read_ints()
A.sort()
no_idx = 0  # 初めてその色になれないidx [0,no_idx)の色を取ることはできない
s = 0
# いわゆる累積和でどうにかなる
for i, a in enu(A):
    if s * 2 < a:
        no_idx = i
    s += a

print(N - no_idx)