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
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort(reverse=True)
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 1
	A = sum(a)
	for i in range(N):
		if (A-sum_list[i])*2 >= a[i]:
			count += 1
		else:
			break

	print(count)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
	N = int(input())
	a = list(map(int,input().split()))
	a.sort()
	sum_list = [a[0]]
	for i in range(N-1):
		sum_list.append(sum_list[i]+a[i+1])
	count = 0
	for i in range(N-1):
		if 2*sum_list[i] < a[i+1]:
			count = i+1

	print(N-count)

if __name__ == "__main__":
	main()

Submission status: Accepted

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

A.sort()
a = 0
failed = 0
for i in range(N - 1):
    a += A[i]
    if A[i + 1] > 2 * a:
        failed = i + 1
print(N - failed)

Submission status: Accepted

Solution code:
def main():

    N = int(input())
    A = list(map(int, input().split()))
    A.sort(reverse = True)
    totA = sum(A)
    count = 1
    for i in range(N):
        totA -= A[i]
        if 2 * totA >= A[i]:
            count += 1
        else:
            break
    return count

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(i) for i in input().split()])
ans = 0
c = 0
for i in range(N):
    if c*2 < A[i]:
        ans = 1
    else:
        ans += 1
    c += A[i]
print(ans)

Submission status: Accepted

Solution code:
# 2019/09/09

from itertools import accumulate

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

acc=[0]+list(accumulate(a))
acc.pop()
acc.pop()
cnt=1
next=a.pop()

while a and acc:
    aa=a.pop()
    ac=acc.pop()
    if (aa+ac)*2>=next:
        cnt+=1
    else:break
    next=aa

print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n = I()
L = sorted(LI())


left = 0
right = n
while left <= right:
    mid = (left + right) // 2
    ret = sum(L[:mid + 1])
    i = mid + 1
    flag = False
    while ret * 2 >= L[i]:
        ret += L[i]
        i += 1
        if i >= n:
            flag = True
            break
    if flag:
        right = mid - 1
    else:
        left = mid + 1



if flag:
    print(n - mid)
else:
    print(n - mid - 1)

Submission status: Accepted

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


def main():
    from itertools import accumulate

    n = int(input())
    # 大きさを基準に昇順で並び替えておく
    a = sorted(list(map(int, input().split())))
    sum_a = list(accumulate([0] + a))
    # 色は最大でN種類
    ans = [False for _ in range(n)]
    # 初期化：最も大きいモンスターは，確実に最後まで生き残る
    ans[n - 1] = True

    # KeyInsight
    # あるモンスターiが最後まで残る
    # =吸収を繰り返していき，自分の2倍以上大きなモンスターが存在しないことを満たす，と言い換える
    # サイズの大きなモンスターから順に判定
    for i in range(n - 2, -1, -1):
        if a[i + 1] <= 2 * a[i]:
            if ans[i + 1]:
                ans[i] = True
        # サイズの小さいモンスターjは，事前に自分より小さいモンスターを全て吸収しておく
        # それからモンスターjとモンスターj+1のサイズを比較
        elif a[i + 1] <= 2 * sum_a[i + 1]:
            if ans[i + 1]:
                ans[i] = True
        else:
            ans[i] = False

    print(sum(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from itertools import accumulate

    n = int(input())
    a = sorted(list(map(int, input().split())))
    sum_a = list(accumulate([0] + a))
    ans = [False for _ in range(n)]
    ans[n - 1] = True

    for i in range(n - 2, -1, -1):
        if a[i + 1] <= 2 * a[i]:
            if ans[i + 1]:
                ans[i] = True
        elif a[i + 1] <= 2 * sum_a[i + 1]:
            if ans[i + 1]:
                ans[i] = True
        else:
            ans[i] = False

    print(sum(ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq as hp

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

B = []
for a in A:
    hp.heappush(B, a)

ans = 1
for _ in range(N-1):
    ans += 1
    a1 = hp.heappop(B)
    a2 = hp.heappop(B)
    if a1*2 < a2:
        ans = 1
    hp.heappush(B, a1+a2)
print(ans)

Submission status: Accepted

Solution code:
import bisect, copy

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

b = copy.deepcopy(a)
for i in range(n - 1):
    b[i + 1] += b[i]

def ok(x):
    while True:
        y = bisect.bisect_right(a, b[x] * 2)
        if x == y - 1:
            return False
        if y == n:
            return True
        x = y - 1
    

lo = -1
hi = n
while abs(lo - hi) > 1:
    mi = (lo + hi) // 2
    if ok(mi):
        hi = mi
    else:
        lo = mi

print(n - hi)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  l.sort()
  for i in range(n-1):
    l[i+1]+=l[i]

  # print(l)
  
  ans=n
  c=1
  for i in range(n-1):
    if l[i+1]-l[i]>l[i]*2:
      ans-=c
      c=1
    else:
      c+=1

  return ans

# main()
print(main())

Submission status: Accepted

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

Submission status: Accepted

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

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

  if tmp *2 >=  a[i+1]:
    ans += 1
  else:
    ans = 1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

def accmulate(arr):
    global cs
    N = len(arr)
    cs = [0]*(N+1)
    for i in range(N):
        cs[i+1] = cs[i] + arr[i]

# [l,r)
def query(l,r):
    return cs[r] - cs[l]

A = sorted(A)
accmulate(A)

ans = N

for i in range(N-1,0,-1):
    if not A[i] <= 2*query(0,i):
        ans -= i
        break

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    a = sorted(list(map(int, input().split())))

    s = [a[0]]
    for i in range(1, N):
        s.append(s[-1] + a[i])
    # print(a)
    # print(s)
    ans = 1
    for i in range(N-2, -1, -1):
        if s[i] * 2 >= a[i+1]:
            ans += 1
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, *A = map(int, open(0).read().split())
A.sort()
t, acc = 0, 0
for i in range(N - 1):
    acc += A[i]
    if 2 * acc < A[i + 1]:
        t = i + 1
print(N - t)

Submission status: Accepted

Solution code:
# AGC011B - Colorful Creatures
def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    total, ng = 0, 0
    for i, a in enumerate(A):
        if a > total * 2:
            ng = i
        total += a
    ans = N - ng
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC011B - Colorful Creatures
from itertools import accumulate


def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    cs = [0] + list(accumulate(A))  # cs: cumulative sum
    ng = [i for i, (a, c) in enumerate(zip(A, cs)) if c * 2 < a]
    ans = N - max(ng)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC011B - Colorful Creatures
from itertools import accumulate


def main():
    N = int(input())
    A = sorted(map(int, input().split()))
    ac = list(accumulate(A))
    ans = 1
    for i, j in zip(ac[:-1][::-1], A[1:][::-1]):
        if i * 2 >= j:
            ans += 1
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    sumA = sum(A)
    ans = 0
    for i in range(N)[:: -1]:
        sumA -= A[i]
        if sumA * 2 < A[i]:
            ans = N - i
            break
    print(ans)


sol()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

A.sort()
total = sum(A)

def test(i):
    # i番の色の人が最大になれる
    size = sum(A[:i+1])
    for x in A[i+1:]:
        if size*2 >= x:
            size += x
        else:
            break
    return size == total

left = -1 # 最大になれない
right = N-1 # 最大になれる
while right > left + 1:
    mid = (left + right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = N-right
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N = int(input())
A = sorted(list(map(int, input().split())))
t = 0
for i in range(N-1):
    if 2*A[i] < A[i+1]:
        t = i+1
    A[i+1] += A[i]
print(N-t)

Submission status: Accepted

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

A.sort()

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

print (ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
s=0
flag=0
for i,j in enumerate(a):
    if j>2*s:
        flag=i
    s+=j
print(n-flag)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

A = np.array(A, dtype=int)
A.sort()
cs = A.cumsum()

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

Submission status: Accepted

Solution code:
n=int(input())
l=sorted(list(map(int,input().split())))
ls=[]
tmp=0
for i in l:
    tmp+=i
    ls.append(tmp)
l.reverse()
ls.reverse()
l=[0]+l
ans=0
for i in range(n):
    if ls[i]*2>=l[i]:ans+=1
    else:print(ans);exit()
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
nums= list(map(int,input().split(" ")))
nums.sort()
temp = nums[0]
cleared = nums[0]
for i in range(1,N ):
    if temp * 2 >= nums[i]:
        pass
    else:
        cleared = nums[i]
    temp += nums[i]
ans = 0
for temp in nums:
    if temp >= cleared:
        ans += 1
print(ans)

Submission status: Accepted

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

a.sort()

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0
    total = 0
    for a in A:
        if total * 2 < a:
            ans = 1
        else:
            ans += 1
        total += a
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC11 B
import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n = int(input())
a = list(map(int,input().split()))
a.sort()
b = list(accumulate(a))
b = list(map(lambda x:2*x,b))
ans = 1
for i in range(n-1):
    if a[i+1] <= b[i]:
        ans += 1
    else:
        ans = 1
print(ans)

Submission status: Accepted

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

A = sorted(A)

ans = 1

cum = [0]*N
for i, a in enumerate(A) :
    if i == 0 :
        cum[i] = a
    
    else :
        cum[i] = cum[i-1] + a

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    b = LI()
    ans = []
    for j in range(n):
        for i in range(len(b))[::-1]:
            if b[i] == i+1:
                x = b.pop(i)
                ans.append(x)
                break
    if b:
        print(-1)
    else:
        print(*ans[::-1],sep = "\n")
    return

#B
def B():
    n,a,b,c,d = LI()
    s = S()
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    k = b
    while b < d:
        if s[b+1] == ".":
            b += 1
        else:
            if s[b+2] == "#":
                print("No")
                return
            b += 2
    b = k
    if c < d:
        while a < c:
            if s[a+1] == ".":
                a += 1
            else:
                if s[a+2] == "#":
                    print("No")
                    return
                a += 2
        print("Yes")
    else:
        for i in range(b-1,d):
            if s[i:i+3].count(".") == 3:
                print("Yes")
                return
        print("No")
    return

#C
def C():
    n,a,b,c,d = LI()
    if abs(b-a) > (n-1)*d:
        print("NO")
        return
    if 2*c <= (n-1)*(d-c):
        print("YES")
        return
    mi = a-(n-1)*d
    m = c+d
    f = 1+(n-1)*(d-c)
    if f >= m:
        print("YES")
        return
    if (b-mi)%m < f:
        print("YES")
    else:
        print("NO")
    return

#D
def D():
    s = S()
    n = len(s)
    ans = 0
    for i in range(n):
        if s[i] == "U":
            ans += n-i-1
            ans += 2*i
        else:
            ans += 2*(n-i-1)
            ans += i
    print(ans)
    return

#E
def E():
    n = I()
    a = LI()
    a.sort()
    b = [a[i] for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
    for i in range(n-1)[::-1]:
        if a[i+1] > 2*b[i]:
            break
    else:
        print(n)
        return
    print(n-i-1)
    return

#F
def F():
    n = I()

    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Accepted

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

def check(i,A):
    a = sum(A[:i+1])
    for b in A[i+1:]:
        if a*2>=b:
            a += b
        else:return False
    return True

def binary_search(A,func):
    l = 0
    r = len(A)
    if func(0,A):return -1
    if not func(r,A):return r
    while l+1<r:
        i = (l+r)//2
        if func(i,A):
            r = i
        else:
            l = i
    return l

l = binary_search(A,check)
print(N-l)

Submission status: Accepted

Solution code:
#二分探索
N = int(input())
A = [0] + sorted(map(int,input().split()))

def check(i):
    a = sum(A[:i+1])
    for b in A[i+1:]:
        if a*2>=b:
            a += b
        else:return False
    return True

l = 0
r = N
while l+1<r:
    i = (l+r)//2
    if check(i):
        r = i
    else:
        l = i

print(N-l)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n = ni()
a = list(li())

a.sort()

cum = list(accumulate(a))

ans = 1

for i in range(len(a) - 2, -1, -1):
    if a[i+1] > 2*cum[i]:
        break

    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

A = sorted(A)
C = np.cumsum(A)

ans = 0
cnt = 0

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

ans = cnt + 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
creature_list = [ int(v) for v in input().split() ]

def cumsum(inlist):
    s = 0
    outlist = []
    for i in inlist:
        s += i
        outlist.append(s)
    return outlist
creature_list = sorted(creature_list)
creature_list_0 = list(reversed(creature_list))
creature_list = cumsum(creature_list)
creature_list = list(reversed(creature_list))

ans = None
for i in range(1,n):
    if creature_list_0[i-1] > creature_list[i] * 2:
        ans = i
        break
if ans == None:
    ans = n
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np


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


def main():
    n = int(input())
    al = sorted([int(e) for e in input().split()])

    ans = 0
    size = 0
    for a in al:
        if size * 2 < a:
            ans = 1
        else:
            ans += 1
        size += a
    print(ans)


main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort()
l=0
h=n-1
while l<h:
    t=(l+h)//2
    b=sum(a[:t+1])
    for i in range(t+1,n):
        if b*2>=a[-1]:
            h=t
            break
        if b*2<a[i]:
            l=t+1
            break
        b+=a[i]
    else:
        h=t
print(n-l)

Submission status: Accepted

Solution code:
N=int(input())
A=[0]+sorted(map(int,input().split()))
l=0
r=N
while l+1<r:
    i = (l+r)//2
    a = sum(A[:i+1])
    for j in range(i+1,N):
        if a*2<A[j]: l = i;break
        a += A[j]
    else:
        r = i
print(N-r+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import *

N = int(input())
*A, = map(int, input().split())
creatures = [(a, 1) for a in A]
heapify(creatures)
ans = N
while len(creatures) > 1:
    a, m = heappop(creatures)
    b, n = heappop(creatures)
    if 2*a < b: ans -= m; m = 0;
    heappush(creatures, (a+b, m+n))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

# Aを昇順ソートした列をBとして、
# B_{k + 1} > 2(B_1 + ... + B_k) を満たす最大のkを求める。
# N - k が解となる
B = sorted(A)
S = list(accumulate([0] + B))
ans = N - next(
    i
    for i in reversed(range(N))
    if B[i] > 2 * S[i]
)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(n-ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate
from bisect import bisect

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

A_cs = list(accumulate(A))

def can_survive(i): #ソート済みAのi番目(0-index)の生き物が生き残る
  can_absorb = i
  while True:
    cur_volume = A_cs[can_absorb]
    can_absorb_v = A_cs[can_absorb]*2
    if can_absorb_v >= max_a:
      return True
    next_can_absorb = bisect(A,can_absorb_v)-1
    if can_absorb == next_can_absorb:
      return False
    else:
      can_absorb = next_can_absorb

#print([can_survive(i) for i in range(N)])

def search(l,r): #surviveする最小のi
  if r==l+1:
    if can_survive(l):
      return l
    else:
      return r
  c = (l+r)//2
  if can_survive(c):
    return search(l,c)
  else:
    return search(c,r)

x = search(0,N)
print(N-x)

Submission status: Accepted

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

A.sort()

def judge(i,A):
    size = A[i]
    flag = True
    for j in range(N):
        if j!=i:
            if 2*size >= A[j]:
                size+=A[j]
            else:
                flag=False
                break
    return flag

def bisect(s,t,A):
    if t-s==1:
        return t
    else:
        i = (s+t)//2
        if judge(i,A):
            return bisect(s,i,A)
        else:
            return bisect(i,t,A)

if judge(0,A):
    print(N)
else:
    print(N-bisect(0,N,A))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
x,s=1,sum(a)
for i in a[::-1]:
    s-=i
    if 2*s<i:break
    x+=1
print(x)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
A.sort()
def f(x):
    a=0
    for i in range(x+1):
        a+=A[i]
    for i in range(x+1,N):
        if 2*a<A[i]:
            return False
        a+=A[i]
    return True
if f(0):
    print(N)
    exit()
mi=0
ma=N-1
while ma-mi>1:
    mid=(ma+mi)//2
    if f(mid):
        ma=mid
    else:
        mi=mid
print(N-mi-1)

Submission status: Accepted

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

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

Submission status: Accepted

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

def solve(m):
    size = sum(a[:m])
    for j in range(m,n):
        if size*2 >= a[j]:
            size += a[j]
        else:
            return False
    return True

def binary_search(l,r):
    while abs(r-l) >1:
        mid = (l+r)//2
        if solve(mid):#判定のとこは別で
            r = mid
        else:
            l = mid
    return l
print(n-binary_search(0,n))

Submission status: Accepted

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

def check(mid):
    size = a[mid]
    for i in range(n):
        if i == mid:
            continue
        if size*2 < a[i]:
            return False
        size += a[i]
    return True
    
if check(0):
    print(n)
else:
    ok, ng = n-1, 0
    while ok-ng > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(n-ok)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
a.sort()
v=0
k=0
for i in range(n-1):
    v+=a[i]
    if v*2<a[i+1]:
        k=i+1
print(n-k)

Submission status: Accepted

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

a.sort()
a.reverse()
asum = sum(a)

ans = 1

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

A.sort()

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

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

print(ans+1)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
alist = [(a, 1) for a in map(int, input().split())]

heapq.heapify(alist)

for _ in range(n-1):
  a1 = heapq.heappop(alist)
  a2 = heapq.heappop(alist)
  if a1[0] < a2[0]:
    if a1[0] * 2 < a2[0]:
      heapq.heappush(alist, (a1[0]+a2[0], a2[1]))
    else:
      heapq.heappush(alist, (a1[0]+a2[0], a1[1]+a2[1]))
  elif a2[0] < a1[0]:
    if a2[0] * 2 < a1[0]:
      heapq.heappush(alist, (a1[0]+a2[0], a1[1]))
    else:
      heapq.heappush(alist, (a1[0]+a2[0], a1[1]+a2[1]))
  else:
    heapq.heappush(alist, (a1[0]+a2[0], a1[1]+a2[1]))

print(alist[0][1])

Submission status: Accepted

Solution code:
def solve():
  n = int(input())
  a = list(int(i) for i in input().split())
  a.sort()
  t = 0
  suma = 0
  for i in range(n):
    if a[i] > 2*suma:
      t = i
    
    suma += a[i]
  print(n-t)

  
solve()

Submission status: Accepted

Solution code:
#累積和で毎回sumしない
N=int(input())
A=sorted(map(int,input().split()))
b=0
c=0
for n in range(N-1):
  b += A[n]
  if b*2 >= A[n+1]:
    c+=1
  else:
    c=0
print(c+1)

Submission status: Accepted

Solution code:
n =int(input())
a = list(map(int,input().split()))
a.sort()
l,r=0,n
while l != r - 1:
  t = (l + r) // 2
  s = sum(a[:t])
  for m in a[t:]:
    if s * 2 < m:
      l = t
      break
    s += m
  else:
    r = t
print(n - l)

Submission status: Accepted

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