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: Runtime Error

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = set()
    dp.add(0)
    ans = set(x for x in range(max(0, K - A[n] + 1), K))
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K - a - 1, -1, -1):
            if j in dp:
                if j + a in ans:
                    rst = True
                    break
                else:
                    dp.add(j + a)
        else:
            rst = False
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
def solve(n):
    global N, K
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(K + 1):
            dp[i + 1][min(K, j + a)] |= dp[i][j]
            dp[i + 1][j] |= dp[i][j]
    rst = any(dp[N][k] for k in range(K - A[n], K))
    return rst


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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Runtime Error

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[False]*K
        dp[0]=True
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

def check(x):
  dp = [0] * (K + 1)
  dp[0] = 1
  for i in range(N):
    for j in range(K - 1, -1, -1):
      if i == x: continue
      if dp[j]:
        dp[min(K, j + a[i])] = dp[j]
  for j in range(max(0, K - a[x]), K):
    if dp[j]: return True
  return False
#for i in range(N): print(check(i))

if check(0):
  print(0)
  exit(0)
ok = N + 1
ng = 0
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m
print(ok)

Submission status: Runtime Error

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[k]はkが作れる時True
    #保持する情報はTrue/Falseのみで良いので1次元DPを上書きしていく(1回でまとめて)
    dp[0] = True
    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 any(dp[K-a[i]:]) #K-a[i]~K-1のうちどれか作れるならa[i]は必要=True

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

print (ua)

Submission status: Runtime Error

Solution code:
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(n)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(n-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[n-1][K-a[num]:])

    left = 0
    right = N-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&(1<<k)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&1<<k
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[-1] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
l = 0
r = m-1
while l<r:
  mid = (l+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    l = mid+1
print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[-1] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
l = 0
r = m-1
while l<r:
  mid = (l+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    l = mid+1
print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[-1] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
l = 0
r = m-1
while l<r:
  mid = (l+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if x < n-1:
    if maxsum(a[x+1:],k)+sumx >= k:
      r = mid
    else:
      l = mid+1
  else:
    r -= 1
print(sepa[r]+1)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    return N, K, Ai


def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)

    x, y = N, K + 10
    MEMO = [[None for _ in range(y)] for _ in range(x)]

    def recur(ei, i, total):
        if not MEMO[ei][total] is None:
            return MEMO[ei][total]

        if not i < N:
            MEMO[ei][total] = True
            return

        if i == ei:
            # 選ばない
            recur(ei, i + 1, total)
        else:
            # 選ぶ
            if total + Ai[i] < K:
                recur(ei, i + 1, total + Ai[i])

            # 選ばない
            recur(ei, i + 1, total)

    for i in range(N):
        recur(i, 0, 0)

    c = 0
    for i in range(N):
        is_useless = True
        for j in range(K - Ai[i], K):
            if MEMO[i][j]:
                is_useless = False
                break
        if is_useless:
            c += 1
    return c


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    return N, K, Ai


def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)

    def search():
        def recur(i, total, target_card, range_head):
            if range_head <= total < K:
                if not MEMO[i][total] is None:
                    return

            if range_head <= total < K:
                MEMO[i][total] = True
                return

            if not i < N or total > K:
                return

            if i == target_card:
                recur(i + 1, total, target_card, range_head)
            else:
                if not total > K:
                    # 選ぶ
                    recur(i + 1, total + Ai[i], target_card, range_head)

                    # 選ばない
                    recur(i + 1, total, target_card, range_head)

        count = 0
        for target_card in range(N):
            # 2次元配列の生成: table[x][y]
            x, y = N + 1, K + 1
            MEMO = [[None for _ in range(y)] for _ in range(x)]

            range_head = K - Ai[target_card]

            if range_head <= 0:
                MEMO[0][0] = True
            else:
                recur(0, 0, target_card, range_head)

            for i in range(N):
                if 0 < MEMO[i].count(True):
                    count += 1
                    break

        return count

    res = search()
    return res


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    return N, K, Ai


def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)

    def search():
        def recur(i, total, target_card, range_head):
            if range_head <= total < K:
                if not MEMO[i][total] is None:
                    return

            if range_head <= total < K:
                MEMO[i][total] = True
                return

            if not i < N or total > K:
                return

            if i == target_card:
                recur(i + 1, total, target_card, range_head)
            else:
                if total < range_head:
                    # 選ぶ
                    recur(i + 1, total + Ai[i], target_card, range_head)

                    # 選ばない
                    recur(i + 1, total, target_card, range_head)

        count = 0
        for target_card in range(N):
            # 2次元配列の生成: table[x][y]
            x, y = N + 1, K + 1
            MEMO = [[None for _ in range(y)] for _ in range(x)]

            range_head = K - Ai[target_card]

            if range_head <= 0:
                MEMO[0][0] = True
            else:
                recur(0, 0, target_card, range_head)

            for i in range(N):
                if 0 < MEMO[i].count(True):
                    count += 1
                    break

        return count

    res = search()
    return res


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))
 
    return N, K, Ai
 
def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N
 
    Ai = sorted(Ai)
    
    def search():
        def recur(i, total, target_card, range_head):

            if range_head <= total < K:
                if not MEMO[i][total] is None:
                    return

            if range_head <= total < K:
                MEMO[i][total] = True
                return

            if not i < N:
                return

            if i == target_card:
                recur(i + 1, total, target_card, range_head)
            else:
                if total < range_head:
                    # 選ぶ
                    recur(i + 1, total + Ai[i], target_card, range_head)

                    # 選ばない
                    recur(i + 1, total, target_card, range_head)

        count = 0
        for target_card in range(N):
            x, y = N + 1, K + 100
            MEMO = [[None for _ in range(y)] for _ in range(x)]

            range_head = K - Ai[target_card]
            recur(0, 0, target_card, range_head)

            for i in range(N):
                if 0 < MEMO[i].count(True):
                    count += 1
                    break

        return count

    res = search()
    return res
 
 
if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))
 
    return N, K, Ai
 
def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N
 
    Ai = sorted(Ai)
    
    def search():
        def recur(i, total, target_card, range_head):

            if range_head <= total < K:
                if not MEMO[i][total] is None:
                    return

            if range_head <= total < K:
                MEMO[i][total] = True
                return

            if not i < N:
                return

            if i == target_card:
                recur(i + 1, total, target_card, range_head)
            else:
                if total < range_head:
                    # 選ぶ
                    recur(i + 1, total + Ai[i], target_card, range_head)

                    # 選ばない
                    recur(i + 1, total, target_card, range_head)

        count = 0
        for target_card in range(N):
            x, y = N + 1, K + 1
            MEMO = [[None for _ in range(y)] for _ in range(x)]

            range_head = K - Ai[target_card]
            if range_head <= 0:
                MEMO[0][0] = True
            else:
                recur(0, 0, target_card, range_head)

            for i in range(N):
                if 0 < MEMO[i].count(True):
                    count += 1
                    break

        return count

    res = search()
    return res
 
 
if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    # print("N", N, "K", K)
    # print(Ai)

    # N, K = 5, 7
    # Ai = [5, 2, 8, 11, 15]

    return N, K, Ai

def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)
    
    def search():
        x, y = N + 1, K + 1
        MEMO = [[None for _ in range(y)] for _ in range(x)]

        def recur(i, total, target_card, range_head):
            if range_head <= total < K:
                if not MEMO[i][total] is None:
                    return

            if range_head <= total < K:
                MEMO[i][total] = True
                return

            if not i < N:
                return

            if i == target_card:
                recur(i + 1, total, target_card, range_head)
            else:
                if total < range_head:
                    # 選ぶ
                    recur(i + 1, total + Ai[i], target_card, range_head)

                    # 選ばない
                    recur(i + 1, total, target_card, range_head)

        count = 0
        for target_card in range(N):
            range_head = K - Ai[target_card]
            if range_head <= 0:
                MEMO[i][0] = True
            else:
                recur(0, 0, target_card, range_head)

            for i in range(N):
                if 0 < MEMO[i].count(True):
                    count += 1
                    break

        return count

    res = search()
    return res


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def need(m):
        s=1
        for i in range(m+1,n):
            s|=s<<aa[i]
            s&=mask
        #print(m,bin(s),bin(s>>k-aa[m]))
        if s>>k-aa[m]:return True
        return False

    n,k=MI()
    mask=(1<<k)-1
    #print(bin(mask))
    aa=LI()
    aa.sort()
    for i in range(n):
        if aa[i]>k:
            aa=aa[:i]
            break
    n=len(aa)
    #print(aa)
    l=-1
    r=n
    while l+1<r:
        m=(l+r)//2
        while aa[m-1]==aa[m]:m-=1
        #print(m,aa[m],need(m))
        if need(m):r=m
        else:l=m
    print(l+1)

main()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def need(m):
        s=1
        for i in range(m+1,n):
            a=aa[i]
            s|=s<<a
            s&=mask
        #print(m,bin(s))
        for i in range(max(0,k-aa[m]),k):
            if s>>i&1:return True
        return False

    n,k=MI()
    mask=(1<<k+1)-1
    #print(bin(mask))
    aa=LI()
    aa.sort()
    #print(aa)
    l=-1
    r=n
    while l+1<r:
        m=(l+r)//2
        while aa[m-1]==aa[m]:m-=1
        #print(m,aa[m],need(m))
        if need(m):r=m
        else:l=m
    print(l+1)

main()

Submission status: Runtime Error

Solution code:
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.values():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Submission status: Runtime Error

Solution code:
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Submission status: Runtime Error

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n
while l!=r:
    i=(l+r)//2
    ta = a[i]
    na = a[:i]+a[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(n-1):
        for m in range(k,0,-1):
            if m-na[j]>=0:
                dp[m]=dp[m] or dp[m-na[j]]
    flag = False
    for j in range(k-ta,k):
        if dp[j]:
            flag = True
            break
    if flag:
        r=i
    else:
        l=i+1
print(l)

Submission status: Runtime Error

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
fa.reverse()
nn = len(fa)
for i in range(nn):
    flag = 0
    ta = fa[i]
    na = fa[:i]+fa[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(nn-1):
        for l in range(k,0,-1):
            if l-na[j]>=0:
                dp[l]=dp[l] or dp[l-na[j]]
    for j in range(k-ta,k):
        if dp[j]:
            flag = 1
            break
    if flag == 0:
        res = i
        break
print(nn-i)

Submission status: Runtime Error

Solution code:
class cumsum:
    def __init__(self, A):
        self.n = len(A)
        self.data = [0]*self.n
        for i in range(self.n):
            self.data[i] = self.data[i-1]+A[i]
    def query(self, l, r):
        if n<=l:
            return 0
        if r<0:
            return 0
        if l<0:
            x = 0
        else:
            x = self.data[l]
        if r>=self.n:
            y = self.data[-1]
        else:
            y = self.data[r]
        return y-x

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
a.reverse()
for i in range(N):
    x = dp1[i-1]
    y = dp2[(i+2)%(N+1)]
    sy = cumsum(y)
    for j in range(K+1):
        if x[j]:
            if sy.query(K-a[i]-1-j, K-1-j):
                ans+=1
                break
print(N-ans)

Submission status: Runtime Error

Solution code:
import itertools

def fff(x):
    dp=[0]*k
    dp[0]=1
    for u in itertools.chain(a[:x],a[x+1:]):
        h=dp[:]
        for i in range(u,k):
            h[i]=h[i]|dp[i-u]
        dp=h
    cnt=0
    for i in range(k-a[x],k):
        cnt+=dp[i]
    if cnt==0:
        return True
    else:
        return False

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if fff(mid):    #不必要
        low=mid
    else:
        high=mid

if fff(high):
    print(high+1)
else:
    print(low+1)

Submission status: Runtime Error

Solution code:
import itertools

def fff(x):
    dp=[0]*k
    dp[0]=1
    for u in itertools.chain(a[:x],a[x+1:]):
        h=dp[:]
        for i in range(u,k):
            h[i]=max(h[i],dp[i-u])
        dp=h
    for i in range(k-a[x],k):
        if dp[i]==1:
            return False
            break
    else:
        return True
        

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if fff(mid):    #不必要
        low=mid
    else:
        high=mid

if fff(high):
    print(high+1)
else:
    print(low+1)

Submission status: Runtime Error

Solution code:
def f(x):
    global a
    dp=[0]*k
    dp[0]=1
    for i in range(n):
        if i==x:
            continue
        else:
            h=[0]*k
            b=a[i]
            for i in range(k):
                if dp[i]==1:
                    h[i]=1
                    if i+b<k:
                        h[i+b]=1
        dp=h
    for i in range(k-a[x],k):
        if dp[i]==1:
            return True
    else:
        return False
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high>low+1:
    h=(high+low)//2
    if f(h):
        high=h
    else:
        low=h
if f(low):
    print(max(0,low-1)+1)
else:
    if f(high):
        print(low+1)
    else:
        print(high+1)

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp1 = np.zeros((N+1, K), dtype=bool)
dp1[0][0] = 1
for i, a in enumerate(A, 1):
    dp1[i, :] = dp1[i-1, :]
    dp1[i, a:] += dp1[i-1, :-a]
dp2 = np.zeros((N+1, K), dtype=bool)
dp2[N][0] = 1
for i, a in zip(range(N-1, -1, -1), A[::-1]):
    dp2[i, :] = dp2[i+1, :]
    dp2[i, a:] += dp2[i+1, :-a]
ans = 0
for a, d1, d2 in zip(A, dp1[:-1], dp2[1:]):
    d2_ = np.zeros(K+a, dtype=np.int32)
    d2_[a:] = d2
    d2_cum = np.cumsum(d2_)
    d2_diff = d2_cum[a:] - d2_cum[:-a]
    d = d2_diff[::-1] * d1
    if (d == 0).all():
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1) for i in range(n+1)]
DP1 = np.full((n+1, k+1), False)
DP1[0][0] = True
DP2 = [[False]*(k+1) for i in range(n+1)]
DP2 = np.full((n+1, k+1), False)
DP2[0][0] = True

for i in range(n):
    DP1[i+1] = DP1[i]
    DP1[i+1][a[i]:] |= DP1[i][:k-a[i]+1]
    DP2[i+1] = DP2[i]
    DP2[i+1][a[n-1-i]:] |= DP2[i][:k-a[n-1-i]+1]

hoge = []
for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    hoge.append(q)

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if hoge[n-i-1][right] - hoge[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)