Problem:


Score : 600 points

Problem Statement

AtCoDeer the deer has N cards with positive integers written on them. The number on the i-th card (1≤i≤N) is a_i.
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.

Then, for each card i, he judges whether it is unnecessary or not, as follows:

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

Otherwise, card i is NOT unnecessary.

Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

1≤a_i≤10^9 (1≤i≤N)

Partial Score

300 points will be awarded for passing the test set satisfying N,K≤400.

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

There are two good sets: {2,3} and {1,2,3}.

Card 1 is only contained in {1,2,3}, and this set without card 1, {2,3}, is also good. Thus, card 1 is unnecessary.

For card 2, a good set {2,3} without card 2, {3}, is not good. Thus, card 2 is NOT unnecessary.

Neither is card 3 for a similar reason, hence the answer is 1.

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
A = []
ans = 0
for a in _A:
    if a >= K:  # 一つで良い集合
        ans += 1
    else:
        A.append(a)

M = len(A)
A.sort(reverse=True)
confilm = [0 for _ in range(N)]

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

left = 0
right = 1
while right < M:
    while sumA[right] - sumA[left] >= K:
        left += 1
    for check in range(right, M):
        if (sumA[right] - sumA[left]) + A[check] >= K:
            confilm[check] = 1
            for i in range(left, right):
                confilm[i] = 1
    right += 1

ans += sum(confilm)
print(N - ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,k = [int(i) for i in readline().split()]
a= [int(i) for i in readline().split()]

from bisect import *

a.sort()
l = bisect_left(a,k) # a[:l] のみを考える
ans = n-l

m = sum(a[:l])

#print(a[:l])
dp = [0]*(k+1)
dp[0] = 1
for ai in reversed(a[:l]):
#    print(m)
    for i in range(max(0,k-m),k):
        if dp[i]: break
    else: break
    ans += 1
    m -= ai
    for i in range(k-ai,-1,-1):
        if dp[i] == 1: dp[i+ai] = 1 
#    print(dp)

print(n-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
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
"""
iが必要←→iを使わずに[k-ai,k)内の和を作れる→累積和問題(O(nk))
必要性は単調性を満たす(iが必要→jも必要(aj>ai))→二部探索(O(logn))
後は高速化をがんばる
合計O(nklogn)
"""
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma+1,k-ai))[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

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
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma+1,k-ai))[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Accepted

Solution code:
def hersCode(l, r):
  ok = r
  ng = l - 1
  while ok - ng > 1:
    mid = (ok + ng) // 2
    if nasu(a[mid]):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(x):
  if x >= K:
    return True
  D = [0] * K
  L = [0]
  f = 0
  for i in a:
    if i == x and f == 0:
      f = 1
      continue
    for jj in range(len(L) - 1, -1, -1):
      j = L[jj]
      if i + j < K:
        if i + j + x >= K:
          return True
        if D[i + j] == 0:
          D[i + j] = 1
          L.append(i + j)
  return False


N, K = list(map(int, input().split()))
a = list(map(int, input().split()))

a.sort()
a.append(10 ** 9 + 1)
ans = hersCode(0, N)
print(ans)

Submission status: Accepted

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

import numpy as np

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

sys.setrecursionlimit(2147483647)
INF = float("inf")

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


def bisect_left_callable(fn, x, lo, hi):
    """
    (memo) いっぱい呼ぶなら np.searchsorted のほうがベクトル化されててはやそう
    lo から hi-1 のうち、fn の結果が x 以上となる、最も左の値
    bisect.bisect_left と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if fn(mid) < x:
            lo = mid + 1
        else:
            hi = mid
    return lo


def is_necessary(ai):
    # A[ai] が必要かどうか
    # A[ai] を使わずに K-A[ai] 以上 K 未満を作れるか

    # dp[j]: j を作れる
    dp = np.zeros(K, dtype=bool)
    dp[0] = 1
    for i, a in enumerate(A):
        if i == ai:
            continue
        dp[a:] = dp[a:] | dp[:-a]
    return any(dp[K - A[ai]:])


A.sort()
unnecessary = bisect_left_callable(is_necessary, 1, lo=0, hi=N)
print(unnecessary)

Submission status: Accepted

Solution code:
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort(reverse=True)
	no_need = 0
	sub = 0
	for ai in A:
		if sub+ai < K:
			sub += ai
			no_need += 1
		else:
			no_need = 0

	print(no_need)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

def check(i): #i番目のカードを使わなかった時
    dp = np.zeros(K, dtype = np.bool) #配列の初期化 
    #本来dp[x][y]の配列を用意すべきだけど、一回見たらそれ以降は見ないから上書きしていく
    #xが何であろうか、作れるかどうかだけが大切
    #dp: kが作れるかどうかだけを記録している
    dp[0] = True
    # print (dp)
    for j in itertools.chain(a[:i], a[i+1:]): #i番目を除いたリストを走査
        dp[j:] = np.logical_or(dp[j:], dp[:-j]) #ある数jを使うと、j以降のもの(N-j)個と前から(N-j)個のどちらかがTrueのものは作れる
    return not dp[-a[i]:].any() #dpのK-a[i]からKの範囲どれかにTrueがあるとFalseを返す

#詳しくはノート参照


# aを昇順並べた後の走査で、
# a_iが必要な時、a_(i+1)も必要
# -->二分探索によりlog Nで探索

la = -1
ua = N
while ua - la > 1:
    mid = (ua + la)//2
    if check(mid):
        la = mid
    else:
        ua = mid

print (ua)

Submission status: Accepted

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

a.sort(reverse = True)

ans = 0
tmp = 0
for i in a:
    if tmp + i < K:
        ans += 1
        tmp += i
    else:
        ans = 0 #リセット

print (ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
*l, = list(map(int,input().split()))
l.sort(reverse=True)
m = 0
ans = 0
for i in l:
  if m+i < k:
    m += i
    ans += 1
  else:
    ans = 0
print(ans)

Submission status: Accepted

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

N, K = map(int, input().split())
a = list(map(int, input().split()))

a.sort(reverse = True)

subtotal = 0
need = 0
for i in range(N):
    if subtotal + a[i] < K:
        subtotal += a[i]
    else:
        need = i+1
print(N - need)

Submission status: Accepted

Solution code:
# x < yでyが不要とする。y抜きで[K-y,K)を作れる。
# このときにxを使っていないのならば、xも不要。
# xを使っているのならば、xy抜きで[K-x-y,K-x)を作れる。
# yを加えて、x抜きで[K-x,K)を作れる。
# よってy不要ならばx不要。
import numpy as np
import itertools

N,K = map(int,input().split())
A = [int(x) for x in input().split()]
A.sort()

# カードは[0,N)-indexed

def test(i):
  # i番目のカードは不要
  dp = np.zeros(K,dtype=np.bool)
  dp[0] = True
  for a in itertools.chain(A[:i],A[i+1:]):
    dp[a:] = np.logical_or(dp[a:],dp[:-a])
  return not dp[-A[i]:].any()

left = -1 # 不要だと判明
right = N # 不要でないと判明
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    left = mid
  else:
    right = mid

   
answer = left+1
print(answer)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
s = 0 #sum a which may not be necessary
need = 0
for i in range(n):
    if s + a[i] < k:
        s += a[i]
    else:
        need = i+1
print(n - need)

Submission status: Accepted

Solution code:
n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

count = 0
asum = 0
for item in a:
    if asum + item < k:
        asum += item
        count += 1
    else:
        count = 0

print(count)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
S=0
ans=0
for a in A:
    if S+a<K:
        S+=a
        ans+=1
    else:ans=0
print(ans)

Submission status: Accepted

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

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

SUM=0
for a in A:
    SUM+=a
    if SUM>=K:
        MAX_NO_NEED=a
        break

else:
    print(N)
    sys.exit()
        

MAX=A.index(MAX_NO_NEED)-1

A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=min(MAX,L-1)

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)

Submission status: Accepted

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

a.sort(reverse=True)

temp = 0
ans = 0

for x in a:
    if temp + x < k:
        temp += x
        ans += 1
    else:
        ans = 0

print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
x=[int(p) for p in input().split()]
x.sort()
x = x[::-1]
pp=0
ans=0
for a in x:
  if pp+a < K:
    pp+=a
    ans+=1
  else:
    ans=0
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
A.sort()
cards = 0
tail = N
needs = N
while tail:
  for i in range(tail):
    if A[i] + cards >= K:
      cards += A[i - 1]
      tail = i - 1
      needs = i
      break
  else:
    cards += A[i]
    tail = i
print(needs)

Submission status: Accepted

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

def f(N,K,a):
    a.sort()
    if a[0] >= K:
        print(0)
        exit()

    a = [a[i] for i in range(N) if a[i]<K]
    N = len(a)
    ans = N
    dp = [False]*K
    dp[0] = True
    Smax = 0
    for i,a_ in reversed(list(enumerate(a))):
        if Smax + a_ >= K:
            ans = i
        updated = True
        for j in range(min(Smax,K-a_-1),-1,-1):
            if dp[j]:
                dp[j+a_]=True
                if updated:
                    Smax = max(Smax,j+a_)
                    updated = False
    return ans

print(f(N,K,a))

Submission status: Accepted

Solution code:
N, K = map( int, input().split())
A = list( map( int, input().split()))
RA = sorted(A)
RA = RA[::-1]
s = 0
ans = 0
for i in range(N):
    a = RA[i]
    if s+a < K:
        s += a
        ans += 1
    else:
        ans = 0
print(ans)
#反例
#5 12
#6 4 3 2 1

Submission status: Accepted

Solution code:
N, K = map( int, input().split())
A = list( map( int, input().split()))
RA = sorted(A)
RA = RA[::-1]
s = 0
ans = 0
for i in range(N):
    a = RA[i]
    if s+a < K:
        s += a
        ans += 1
    else:
        ans = 0
print(ans)

Submission status: Accepted

Solution code:
def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    A.sort()
    a_sorted = A[:bisect_left(A, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in reversed(list(enumerate(a_sorted))):
        if current_max + a >= K:
            ans = idx  # これを満たさないaは不必要

        # current_maxはループの中で1回だけ更新する。
        # jを変化させるたびに代入すると時間がかかるため
        updated = True
        for j in range(min(current_max, K - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True  # 和をjにできているなら、j+aにもできる
                if updated:
                    current_max = max(current_max, j + a)
                    updated = False
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))
# https://beta.atcoder.jp/contests/arc070/submissions/2980516 参考
# https://medaka.5ch.net/test/read.cgi/prog/1534548265/ の>>75によると
# 8 100
# 1 1 8 8 8 25 26 50
# に対して2や5を返すsubmissionが見られるとのこと(実際は0)

Submission status: Accepted

Solution code:
def d_no_need(N, K, A):
    from bisect import bisect_left
    # 値がK以上の要素は単体で不必要でない要素になれる
    A.sort()
    a_sorted = A[:bisect_left(A, K)]
    ans = len(a_sorted)  # a_sortedの要素は不必要となりうる

    dp = [False] * K  # dp[k]:a_sortedの一部の和を取った値をKにできるか？
    dp[0] = True
    current_max = 0
    for idx, a in reversed(list(enumerate(a_sorted))):
        if current_max + a >= K:
            ans = idx

        first_update = True
        for j in range(min(current_max, K - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if first_update:
                    current_max = max(current_max, j + a)
                    first_update = False
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in set(stack):
                if need[key]:
                    continue
                else:
                    need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

Submission status: Accepted

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

a = sorted(a)[::-1]
ans = n
sm = 0

for i in range(n):
    if sm + a[i] < k:
        sm += a[i]
    else:
        ans = min(ans, n - i - 1)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K, A):
    A.sort()

    s = 0
    ans = N
    for i in range(N-1, -1, -1):
        if s + A[i] < K:
            s += A[i]
        else:
            ans = min(ans, i)
    return ans


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#N,K = 5000,5000
#A = [1]*N

# K以上のものはAから省く
B = []
for a in A:
    if a<K:
        B.append(a)

B.sort(reverse=True)

isNeeded = [False]*(len(B))
# iをスタックに入れる
for i in range(len(B)-1):
    res = B[i]
    stack = [i]
    for j in range(i+1,len(B)):
        res += B[j]
        stack.append(j)
        if res >= K:
            for s in stack:
                if isNeeded[s]:
                    continue
                else:
                    isNeeded[s] = True
            stack.pop()
            res -= B[j]
            
noNeed = len(B) - sum(isNeeded)
print(noNeed)

Submission status: Accepted

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

# K以上のものはAから省く
B = []
for a in A:
    if a<K:
        B.append(a)

B.sort(reverse=True)

isNeeded = [False]*(len(B))
# iをスタックに入れる
for i in range(len(B)-1):
    res = B[i]
    stack = [i]
    for j in range(i+1,len(B)):
        res += B[j]
        stack.append(j)
        if res >= K:
            for s in stack:
                isNeeded[s] = True
            stack.pop()
            res -= B[j]
            
noNeed = len(B) - sum(isNeeded)
print(noNeed)

Submission status: Accepted

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

a = sorted(a)
sum_a = 0
ans = 0
for i in range(n-1, -1, -1):
    if sum_a+a[i] < k:
        sum_a += a[i]
        ans += 1
    else:
        ans = 0
    # print(ans)
print(ans)

Submission status: Accepted

Solution code:
import bisect
from collections import deque
N, K = map(int, input().split())
a = sorted(map(int, input().split()))

# K以上のカードは単体で条件を満たすから考えない
a_k = bisect.bisect_left(a, K, lo=0, hi=N)
A = a[:a_k][::-1]
tmp = 0
N = result = N-(N-a_k)

for n, i in enumerate(A):
    if tmp+i >= K:
        result = N-(n+1)
    else:
        tmp += i

print(result)

Submission status: Accepted

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

count = N
s = 0
for i in range(N-1,-1,-1):
    if s + a[i] < K:
        s += a[i]
    else:
        count = i
print(count)

Submission status: Accepted

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

count = N
s = 0
for i in range(N-1,-1,-1):
    if s + a[i] < K:
        s += a[i]
    else:
        count = min(i,count)
print(count)

Submission status: Accepted

Solution code:
n,k = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
a,num,ans = sorted(a),0,n
for i in range(n-1,-1,-1):
	if num+a[i]<k: num+=a[i]
	else: ans = i
print(ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
su=0
ans=0
for a in A:
  if su+a < K:
    su+=a
    ans+=1
  else:
    ans=0
print(ans)

Submission status: Accepted

Solution code:
def d_no_need(N, K, A):
    card = sorted(A, reverse=True)
    s = 0  # カードの値の総和
    ans = 0  # 不必要なカードの枚数
    # Aのうち要素が大きいものから見ていったとき、
    # その要素を入れても総和がK未満のものだけ加えていく
    # 最後に連続して加えた要素の個数が解となる
    # (それら以外の要素の組み合わせでK以上にでき、かつ、
    #  それらの総和がK未満になるため)
    for a in card:
        if s + a < K:
            s += a
            ans += 1
        else:
            ans = 0
    return ans

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Accepted

Solution code:
from collections import Counter
N,K=map(int, raw_input().split())
a=map(int, raw_input().split())
a.sort()
a.reverse()

tmp=[]
tmp_sum=0
b=[]
for i in a:
	if tmp_sum+i>=K:
		b.append(i)	
	else:
		tmp.append(i)
		tmp_sum+=i

if len(b)==0:
	print N
else:
	min_num=b[-1]
	c=Counter(a)
	print N-(a.index(min_num)+c[min_num])

Submission status: Accepted

Solution code:
import random
N, K = map(int, input().split())
*V, = map(int, input().split())
A = [0]*(N+1)
B = [0]*(N+1)
MASK = 2**(K+1)-1
A[0] = 1
for i in range(N):
    if K <= V[i]:
        A[i+1] = A[i]
    else:
        A[i+1] = (A[i] | ((A[i] << V[i]) & MASK))
B[N] = 1 << K
for i in range(N-1, -1, -1):
    if K <= V[i]:
        B[i] = B[i+1]
    else:
        B[i] = (B[i+1] | (B[i+1] >> V[i]))

ans = N
for i in range(N):
    if K <= V[i]:
        ans -= 1
        continue
    a = A[i]; b = B[i+1]
    VM = 2**(V[i]+1)-2
    l = 1
    while a and b and l:
        if a & 1 and b & VM:
            ans -= 1
            break
        l = max((a & -a).bit_length()-1, (b & -b).bit_length()-V[i]-1)
        a >>= l; b >>= l
print(ans)

Submission status: Accepted

Solution code:
def d_NoNeed(N, K, A):
    a = sorted(A)
    s = t = 0
    # aのうち要素が大きいものから見ていったとき、
    # その要素を入れても総和がK未満のものだけ加えていく
    # 最後に連続して加えた要素の個数が解となる
    # (それら以外の要素の組み合わせでK以上にでき、かつ、
    #  それらの総和がK未満になるため)
    for i in range(N - 1, -1, -1):
        if s + a[i] < K:
            s += a[i]
            t += 1
        else:
            t = 0
    return t

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_NoNeed(N, K, A))

Submission status: Accepted

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

result = 0
S = sum(A)
n = len(A)
s = 0
if S<K:
    result = n
elif S == K:
    result = 0
else:
    for i in range(n):
        if s+A[i] >= K:
            result = n - i - 1
        else:
            s += A[i]

print(result)

Submission status: Accepted

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

a = sorted(a)
ans = N
psum = 0
for i in range(N-1, -1, -1) :
    if psum+a[i] < K :
        psum += a[i]
    else :
        ans = min(ans, i)

print(ans)

Submission status: Accepted

Solution code:
import sys

# sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve(n, k, a):
    filter(lambda x: x < k, a)
    n = len(a)
    a.sort()
    s = 0
    lowest = None
    for i in range(n - 1, -1, -1):
        if k - a[i] <= s:
            # a[i] is not unnecessary
            lowest = i
        else:
            # maybe a[i] is unnecessary
            s += a[i]
    if lowest is None:
        return n
    return lowest

n, k = read_int_list()
a = read_int_list()
res = solve(n, k, a)
print(res)

Submission status: Accepted

Solution code:
import sys
N,K=map(int, input().split())
a=list(map(int, input().split()))
sum=0
for i in range(0,N):
  sum+=a[i]
if sum<K:#全部不必要
  print(N)
  sys.exit()
if sum==K:#全部必要
  print(0)
  sys.exit()
a.sort()
a.reverse()
 
#K未満の最大の数字のラベルはどこ？
l=N
for i in range(N-1,-1,-1):
  if a[i]<K:
    l=i
  else:
    break
 
if l==N:
  print(0)
  sys.exit()
 
count=N
#lまでの要素が必要か不要かチェック(使いまわし可能)
sum=0
l_list=[]
for j in range(l,N):
  if sum+a[j]<K:
    sum+=a[j]
    l_list.append(a[j])
for i in range(0,l):  
  if sum+a[i]>=K:#必要ってことだ
    count-=1
#lからの要素は自分のことを抜かないといけないことに注意
for i in range(l,N):
  if a[i] in l_list:
    sum=0
    b=a[:]
    C=b.pop(i)
    for j in range(l-1,N-1):
      if sum+b[j]<K:
        sum+=b[j]
    if sum+C>=K:#必要ってことだ
      count-=1
  else:
    count-=1
print(count)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))

Submission status: Runtime Error

Solution code:
from itertools import accumulate
import numpy as np

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = np.array([0] * (K+1))
    dp[0] = 1
    nonzeros = [np.array([0])]
    for a in As:
        ndp = np.array([0] * (K+1))
        nonzero = []
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t > 0:
                nonzero.append(i)
                ndp[i] = 1
        nonzeros.append(np.array(nonzero))
        dp = ndp
    
    dp = np.array([0] * (K+1))
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = np.array([0] * (K+1))
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            if t > 0:
                ndp[i] = 1
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in nonzero:
                t = K-y-a-1
                if acc[K-y-1] > acc[t if t >= 0 else -1]:
                    break
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Submission status: Runtime Error

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

    rdp_shift = [N + 1] * K  # rdp_shift[j] = (右からi個を使って部分和jを作れるような最初のi)
    rdp_shift[0] = 0
    rdp = [0] * K  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0] = 1
    for i in range(N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                # print(j - A[i])
                rdp2[j] = 1
                rdp_shift[j] = i
                # print(rdp_shift)
        rdp = rdp2
    # print(rdp_shift)
    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # ここで一つ一つチェックしている！！
        # A[i]が不要かチェック
        for j in range(K):
            S[j + 1] = S[j]
            # print(N - i, rdp_shift[j])
            if rdp_shift[j] <= N - i:
                print(S, rdp_shift, j, N - i, A[i])
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0:
                continue
            # print(K - A[i] - lval)
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            # print(S, K - lval, K - A[i] - lval, rval)
            if rval > 0:
                no_need = False
                break
        if no_need:
            ans += 1

        # ldp[i][:]の計算
        ldp2 = [0] * K
        for j in range(K):
            if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
                ldp2[j] = 1
        ldp = ldp2
    print(ans)
    # print(S)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

sum_A = sum(A)
if sum_A < K:
    print(len(A))
    exit()
elif sum_A == K:
    print(0)
    exit()

dp = [[False] * len(A) for i in range(len(A))]
sum_A_list = []
for i in range(N):
    if i == 0:
        sum_A_list.append(A[i])
        continue

    sum_A_list.append(sum_A_list[i - 1] + A[i])

idx = 0
for i in range(N - 1, -1, -1):
    if sum_A_list[i] < K:
        idx = i
        break

for i in range(idx + 1):
    if sum_A_list[idx + 1] - sum_A_list[i] >= K:
        continue
    else:
        idx = i - 1
        break

print(idx + 1)