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

A.sort()
tmp = 0
l = 0
for i in range(N-1):
    tmp += A[i]
    if 2*tmp < A[i+1]: l = i+1
print(N-l)

Submission status: Accepted

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

Submission status: Accepted

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

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+=[b[-1]+a[i]]
j=0
while a[-1-j]<=b[-2-j]*2:
  j+=1
  if j+1==n:break
print(j+1)

Submission status: Accepted

Solution code:
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
# import sys
# input = sys.stdin.readline

import itertools as it

N=one_int()

A=many_int()

A=sorted(A)
sums_A=list(it.accumulate(A))

for i in range(N-1, -1, -1):
    if 2*sums_A[i-1] < A[i]: 
        break

print(N-i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
cs = [A[0]]
ans = 1
for a in A[1:]:
    cs.append(cs[-1]+a)
for i in range(N-2, -1, -1):
    if cs[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()

color = [1] * n
for i in range(n):
    if i == 0:
        continue
    if a[i - 1] * 2 >= a[i]:
        color[i] += color[i - 1]
    a[i] += a[i - 1]

print(color[-1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls.sort()
s_ls = [i for i in accumulate(a_ls)]
cnt = 1
for i in range(n-2, -1, -1):
    if s_ls[i] * 2 >= a_ls[i+1]:
        cnt += 1
    else:
        break
print(cnt)

Submission status: Accepted

Solution code:
import itertools as it

N=int(input())
A=list(map(int,input().split()))
A.sort()
B=list(it.accumulate(A))
cB=[B[i]*2>=A[i+1] for i in range(len(A)-1)]

ans=1
i=N-2
while i>=0 and cB[i]:
    ans+=1
    i-=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
a = list(map(int,input().split()))
a.sort()
ac = list(accumulate(a))
a.reverse()
ac.reverse()
p = [0] * n
p[0] = 1
for i in range(1,n):
  if a[i-1] <= ac[i] * 2:
    p[i] = p[i-1]
print(sum(p))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    A = sorted(A)

    now = N
    A_cumsum = [A[0]]
    for i in range(1,N):
        A_cumsum.append(A_cumsum[-1]+A[i])
    ans = 0
    for i in range(1,N):
        if A_cumsum[i-1]*2>=A[i]:
            pass
        else:
            ans = i
    print(N-ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

A=sorted(A)

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

print(f)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
now = a[0]
ans = n
for k,v in enumerate(a[1:]):
  if now * 2 < v:
    ans = n - k - 1
  now += v
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from itertools import accumulate

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    v.sort()
    s = [0] + list(accumulate(v))
    ans = 0
    for i in range(1, n):
        if 2 * s[i] >= v[i]:
            ans += 1
        else:
            ans = 0
    ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import bisect
n = int(input())
a = list(map(int, input().split()))
a.sort()
acc = list(itertools.accumulate(a))
ans = 0
for i in range(n):
    index = bisect.bisect_right(a, acc[i]* 2)
    #print("index > {} i > {}  value > {}".format(index, i, acc[i] * 2))
    if index <= i + 1 and index < n:
        ans = i+1
print(n - ans)

Submission status: Accepted

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

A.sort()

B = [0 for _ in range(N)]
b = 0
for i in range(N):
    b += A[i]
    B[i] = b

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
cs = [0] * (N + 1)
for i in range(N):
  cs[i + 1] = cs[i] + a[i]
def check(x):
  t = cs[x + 1]
  for i in range(x + 1, N):
    if a[i] <= 2 * t:
      t += a[i]
    else: return False
  return True
ok = N - 1
ng = -1
m = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m):
    ok = m
  else:
    ng = m
print(N - ok)

Submission status: Accepted

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

A.sort()

B = [0 for _ in range(N)]
b = 0
for i in range(N):
    b += A[i]
    B[i] = b

ans = 1
for i in range(N-1):
    if 2*B[i]>=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.sort()
l = [0] * N

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

ans = 1
i = N-1
while i > 0 and 2 * l[i-1] >= a[i]:
  ans += 1
  i -= 1

print(ans)

Submission status: Accepted

Solution code:
#自分以下をまず食べてしまう
#その後小さいほうから食べる
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split( )))
a.sort()
a_sm =[]
sm = 0
for i in range(n):
    sm += a[i]
    a_sm.append(sm)
mn = 0
tmp = a[0]
for i in range(1,n):
    if tmp*2 >= a[i]:
        tmp+=a[i]
    else:
        tmp = a_sm[i]
        mn = i
print(n-mn)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())))
sum_A=sum(A)
cnt=1
for i in reversed(range(n)):
    sum_A -=A[i]
    if sum_A*2>=A[i]:
        cnt +=1
    else:break
print(cnt)

Submission status: Accepted

Solution code:
import copy
n=int(input())
A=sorted(list(map(int,input().split())))
B=copy.deepcopy(A)
for i in range(1,n):
    B[i]=B[i]+B[i-1]

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

Submission status: Accepted

Solution code:

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

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

B.reverse()
A.reverse()

# print(A)
# print(B)

# [40, 30, 20, 7, 2, 1]
# [100, 60, 30, 10, 3, 1]


i = 1
while i < N:
    if A[i-1] > B[i] * 2:
        break
    i += 1

print(i)

Submission status: Accepted

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

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

print(cnt+1)

Submission status: Accepted

Solution code:
# 2019-11-23 01:09:31(JST)
import sys
import itertools



def main():
    n, *a = map(int, sys.stdin.read().split())
    a.sort()
    
    b = list(itertools.accumulate(a))

    count = 1
    for i in range(n-1, 0, -1):
        if a[i] <= b[i-1] * 2:
            count += 1
        else:
            break
    
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

acc = (0,) + tuple(accumulate(a))

ng = 0
for idx, (acc_, a_) in enumerate(zip(acc, a)):
    if a_ > acc_ * 2:
        ng = idx  # 0-indexed -> 注目しているa_より前の要素数を表す
print(n - ng)

Submission status: Accepted

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

Submission status: Accepted

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

def isOk(n):
    now = sum(A[:n + 1])
    for a in A[n + 1:]:
        if a <= now * 2:
            now += a
        else:
            return False
    return True

ok = N - 1
ng = -1

while ok - ng > 1:
    mid = (ok + ng) // 2

    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - (ng + 1))

Submission status: Accepted

Solution code:
import itertools
n = int(input())
a = list(map(int,input().split()))
a.sort()
#print(a)[1, 2, 7, 20, 30, 40]
A = list(itertools.accumulate(a))
#print(A)[1, 3, 10, 30, 60, 100]
cnt = 0
for i in range(n-1):
  s = A[i]
  #この条件を満たしていないとそれ以上他のスライムを取り込めない
  if s*2 < a[i+1] :
    cnt = i+1

print(n-cnt)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate


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

    A.sort()
    a = list(accumulate(A))
    answer = N

    for i in range(N - 2, -1, -1):
        if a[i] * 2 < A[i + 1]:
            answer = N - (i + 1)
            break

    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate


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

    A.sort()
    a = list(accumulate(A))
    answer = N

    for i in range(N - 1):
        if a[i] * 2 < A[i + 1]:
            answer = N - (i + 1)

    print(answer)


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 = list(accumulate(A))
answer = N

for i in range(N - 1):
    if a[i] * 2 < A[i + 1]:
        answer = N - (i + 1)

print(answer)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# https://misteer.hatenablog.com/entry/AGC011-B
def solve(n, a):
    a.sort()

    res = 0
    sum_ = 0
    for i in range(n):
        if sum_ * 2 < a[i]:
            res = 0
            # a[i-1]までの累積和がa[i]を吸収できないとき、
            # a[i]までの累積和の生き物の色候補は、i一色だけとなる（res+=1で表現）
        sum_ += a[i]
        res += 1
    return res


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    print(solve(n, a))

# 自身の2倍以下の大きさの生き物を吸収できる
# 「残れるかどうか」は、生き物の大きさについて単調性が成り立つ
# ある生き物が残れるなら、それより大きい生き物はすべて残れる

# a[i]までの累積和の生き物の色を考える
# i色は必ず使える
# a[i]以下の生き物をa[i]ベースで吸収すればいいから
# a[i-1]までの累積和がa[i]を吸収できるなら、
# a[i-1]までの累積和の生き物の色が使える

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
sumA = sum(A)-A[N-1]
memo = 0

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

Submission status: Accepted

Solution code:
n = int(input())
A = sorted(list(map(int, input().split())))
c = 1
sumA = sum(A)
for i in range(n-1, 0, -1):
  sumA -= A[i]
  if sumA*2 >= A[i]:
    c += 1
  else:
    print(c)
    exit()
print(n)

Submission status: Accepted

Solution code:
import numpy as np

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

A.sort()
answer = 1
B = A.cumsum()
C = A[1:] <= (2 * B)[:-1]
C = reversed(list(C))
for c in C:
    if not c:
        break
    else:
        answer += 1
print(answer)

Submission status: Accepted

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

can = [False for x in range(N-1)] + [True]
for i in range(N-2,-1,-1):
  if pre[i] >= A[i+1] / 2 and can[i+1]:
    can[i] = True
print(can.count(True))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import math
#import copy
#import sys
#import bisect
#input = sys.stdin.readline
mod=10**9+7
def swap(a,b):
    c=a
    a=b
    b=c
    return a,b
def factorial(x): #階乗計算
    n=1
    for i in range(x):
        n=(n*(i+1))%mod
    return n

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcm(a, b):
    return((a*b)//gcd(a,b))
def div(x): #約数配列
    div=[1]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        if(x%check==0):
            div.append(check)
            while(x%check==0):
                x=x//check
        check+=1
    if x != 1:
      div.append(x)
    return div
def div2(x): #素因数分解配列
    div2=[]
    check=2
    while(x!=1 and check <= int(x**0.5)+2):
        while x%check==0:
            div2.append(check)
            x/=check
        check+=1
    if x != 1:
      div2.append(x)
    return div2

def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト atcoder
    # ord(c) chr(2) alphabet <=> number
    n=int(input())
    a = list(map(int,input().split()))
    ans=1
    k=0
    a.sort()
    for i in range(n-1):
        k+=a[i]
        if k*2>=a[i+1]:
            ans+=1
        else:
            ans=1
    print(ans)

main()

Submission status: Accepted

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

print(n-cnt)

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):

    if s * 2 >= A[i]:
        ans += 1

    else:
        ans = 1

    s += A[i]

print (ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

print(n-t-1)

Submission status: Accepted

Solution code:
# sortして累積和と元のリストを後ろから比較。
N = int(input())
A = list(map(int, input().split()))
A.sort()
R = []
s = 0
for i in A:
  s += i
  R.append(s)
  
# R = [sum(A[:i]) for i in range(N)]

A.sort(reverse=True)
R.sort(reverse=True)
#print(A)
#print(R)

cnt = 1
for i,j in zip(R[1:], A[:-1]):
#  print(i,j)
  if i * 2 >= j:
    cnt += 1
  else:
    break
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists)
sums=0
uselist=[0]*(n+1)
for i in range(n):
    sums+=lists[i]
    uselist[i]=sums
uselist[n]=0

count=0
for i in range(n):
    if uselist[-(i+1)]<=uselist[-(i+2)]*3:
        count+=1
    else:
        break
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
chk=0
d=[]
for i in range(n):
    d.append(chk+a[i])
    chk=d[-1]
ans=1
for i in range(n-2,-1,-1):
    if d[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()))

def cumsum(s):
    n = len(s)
    cs = [0] * (n+1)
    for i in range(n):
        cs[i+1] = cs[i] + s[i]
    return cs

a.sort()
acum = cumsum(a)
ans = 1

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
ans = 0
cnt = 1
ikimono = A[0]
for i in range(1,N):
    if ikimono*2 < A[i]:
        ans += cnt
        cnt = 1
        ikimono += A[i]
    else:
        cnt += 1
        ikimono += A[i]
print(N-ans)

Submission status: Accepted

Solution code:
from itertools import*
n,*a=map(int,open(0).read().split())
acc=list(accumulate(sorted(a)))[::-1]
c=1
i=0
while i<n-1:
  if acc[i]-acc[i+1]<=acc[i+1]*2:
    c+=1
    i+=1
  else:
    break
print(c)

Submission status: Accepted

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

# 方針：二分探索

# 最後の一匹になれれば True
def check(mid, A):
    x = A[mid]

    # 自分以下を全て吸収
    for i in range(mid):
        x += A[i]

    # 自分より大きいヤツを貪欲に吸収していって最後までいけたら True
    for i in range(mid+1, len(A)):
        if A[i] <= x*2:
            x += A[i]
        else:
            return False
    return True

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.append(0) # 二分探索のため、確実に最後の一匹になれないヤツを入れておく
    A.sort()

    lb,ub = 0,N
    while ub - lb > 1:
        mid = (lb + ub)//2
        if check(mid, A):
            ub = mid
        else:
            lb = mid
    # lb が最後の一匹になれない最大のモンスター
    print(N-lb)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0

l=[A[0]]
for i in range(len(A)-1):
    l.append(l[-1]+A[i+1])
    if (l[-1]-l[-2])>2*l[-2]:
        ans=0
    else:
        ans+=1

print(ans+1)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

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

Submission status: Accepted

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

Submission status: Accepted

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

s = 0
point = -1

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

ans = N - point - 1
print(ans)

Submission status: Accepted

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

ans=0
sum=0

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([int(_) for _ in input().split()])
summed = [0] * N
summed[0] = A[0]
for n in range(1, N):
    summed[n] = summed[n - 1] + A[n]

impossible = 0
for n in range(1, N):
    if summed[n - 1] * 2 < A[n]:
        impossible = n
print(N - impossible)

Submission status: Accepted

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

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

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

ans=1
for t in T:
  if t==0:
    ans=1
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# AGC011B - Colorful Creatures
def main():
    N, *A = map(int, open(0).read().split())
    A.sort()
    total, ng = 0, 0
    # ng := max index where A[i] > sum(A[:i]) * 2
    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:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
A = LIST()
A.sort()

# m番目の大きさのやつが、最後の1匹になれるか
def calc(m):
    # 番兵代わり
    if m == -1:
        return False
    # まず自分以下は全部取り込む
    a = sum(A[:m+1])
    # 自分の2倍まではいける
    idx = bisect_right(A, a*2)
    a += sum(A[m+1:idx])
    # 全て取り込んだ後で、その先に行ければ行く
    for i in range(idx, N):
        b = A[i]
        if a*2 >= b:
            a += b
        else:
            # 途中で取り込めなくなったらNG
            return False
    # 最後まで行けるなら、最後の1匹になれる
    return True

print(N-bisearch_min(-1, N-1, calc))

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
A = LIST()
A.sort()

# m番目の大きさのやつが、最後の1匹になれるか
def calc(m):
    # 番兵代わり
    if m == -1:
        return False
    # まず自分以下は全部取り込める
    a = sum(A[:m+1])
    # 全て取り込んだ後で、その先に行ければ行く
    for i in range(m+1, N):
        b = A[i]
        # 自分の2倍まではいける
        if a*2 >= b:
            a += b
        else:
            # 途中で取り込めなくなったらNG
            return False
    # 最後まで行けるなら、最後の1匹になれる
    return True

print(N-bisearch_min(-1, N-1, calc))

Submission status: Accepted

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

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
A = LIST()
A.sort()

# m番目の大きさのやつが、最後の1匹になれるか
def calc(m):
    if m == -1:
        return False
    a = A[m]
    a += sum(A[:m])
    # 自分の2倍まではいける
    idx = bisect_right(A, a*2)
    a += sum(A[m+1:idx])
    # 全て取り込んだ後で、その先に行ければ行く
    for i in range(idx, N):
        b = A[i]
        if a*2 >= b:
            a += b
        else:
            return False
    # 最後まで行けるなら、最後の1匹になれる
    return True

print(N-bisearch_min(-1, N-1, calc))

Submission status: Accepted

Solution code:
from sys import stdin, exit
N = int(stdin.readline().rstrip())
A = sorted([int(_) for _ in stdin.readline().rstrip().split()], reverse=True)
sum_A = sum(A)
ans = 1
for a in A:
    sum_A -= a
    if a > sum_A * 2:
        break
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

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,0,-1):
  if B[i-1]*2>=A[i]:
    cnt+=1
  else:
    break

print(cnt+1)

Submission status: Accepted

Solution code:
import heapq
N = int(input())
A = [[int(a),1] for a in input().split()]

heapq.heapify(A)
cur1 = heapq.heappop(A)

while A:
  cur2 = heapq.heappop(A)
  if cur2[0] <= cur1[0]*2:
    heapq.heappush(A,[cur1[0]+cur2[0],cur1[1]+cur2[1]])
  else:
    heapq.heappush(A,[cur1[0]+cur2[0],cur2[1]])
  cur1 = heapq.heappop(A)
print(cur1[1])

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
As.sort()
r = 1
s = sum(As)
for i in reversed(range(N)):
  s -= As[i]
  if As[i] <= 2*s:
    r += 1
  else:
    break
print(r)

Submission status: Accepted

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

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

Submission status: Accepted

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