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: Time Limit Exceeded

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)
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = defaultdict(int)
    dp[0] = 1
    for i in range(n)[::-1]:
        if i == m:continue
        ai = a[i]
        d = list(dp.keys())
        for j in d:
            dp[j+ai] = 1
            if k_ <= j+ai < k:
                r = m
                break
        else:
            continue
        break
    else:
        l = m
print(r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)


def solve(N: int, K: int, a: "List[int]"):
    a.sort(reverse=True)
    dp = [False] * K
    dp[0] = True
    ret = 0
    for i in range(N):
        for j in range(K - 1, -1, -1):
            if dp[j]:
                if j + a[i] >= K:
                    ret = i + 1
                else:
                    dp[j + a[i]] = True
    print(N - ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


ans = N
for i, a in enumerate(A):
    ans -= is_necessary(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
ans=N
D=[[False]*K for i in range(N+1)]
D[N][0]=True
for i in range(N-1,-1,-1):
    D[i][0]=True
    if A[i]>=K:
        ans=i
        continue
    else:
        for k in range(K):
            if D[i+1][k]:
                if K-A[i]<=k:
                    ans=i
                D[i][k]=True
                if k+A[i]<K:
                    D[i][k+A[i]]=True
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
A=[a for a in A if a<K]
from collections import defaultdict
N=len(A)
bord=-1
can={0}
now=0
for i in range(N):
    flag=False
    canc=can.copy()
    for x in canc:
        if K-A[i]<=x<K:
            flag=True
        if x+A[i]<K:
            can|={x+A[i]}
    if flag:
        bord=i
print(N-bord-1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
A=[a for a in A if a<K]
from collections import defaultdict
N=len(A)
bord=-1
can={0}
now=0
for i in range(N):
    flag=False
    for j in range(K-A[i],K):
        if j in can:
            flag=True
            break
    if flag:
        bord=i
    canc=can.copy()
    for x in canc:
        if x+A[i]<K:
            can|={x+A[i]}
print(N-bord-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    def accumulate(X):
        ret = [X[0]]
        for x in X[1:]:
            ret.append(ret[-1] + x)
        return ret

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

    # K以上の数はすべて必要なのでA未満の数だけを考える
    A = sorted([a for a in A if a < K], reverse=True)
    N = len(A)

    # dp1[i][k] := 1 ~ iまでのカードを使って数kが作れるか
    dp1 = [[0] * (K + 1) for i in range(N + 1)]
    dp1[0][0] = 1
    # dp2[i][k] := N ~ iまでのカードを使って数kが作れるか
    dp2 = [[0] * (K + 1) for i in range(N + 1)]
    dp2[0][0] = 1

    # dpテーブルを計算
    for i in range(1, N + 1):
        for k in range(K + 1):
            dp1[i][k] = max(dp1[i][k], dp1[i - 1][k])
            if A[i - 1] <= k:
                dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - A[i - 1]])

            dp2[i][k] = max(dp2[i][k], dp2[i - 1][k])
            if A[N - i] <= k:
                dp2[i][k] = max(dp2[i][k], dp2[i - 1][k - A[N - i]])

    # 累積和を取っておく
    for i in range(N + 1):
        dp2[i] = list(accumulate(dp2[i]))

    # ansを計算
    need = 0
    for i in range(1, N + 1):
        for k in range(K + 1):
            # 1 ~ i番目まででkが作れない
            if not dp1[i - 1][k]:
                continue

            # 1 ~ i番目までだけで必要な条件が作れる
            if K - A[i - 1] <= k < K:
                need += 1
                break

            # 範囲外参照
            if K - A[i - 1] - k - 1 < 0:
                continue

            if dp2[N - i][K - k] - dp2[N - i][K - A[i - 1] - k - 1] > 0:
                need += 1
                break

    print(N - need)


main()

Submission status: Time Limit Exceeded

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

def check_needed(index):
    memo = [[0] * (max_k + 1) for _ in range(n+1)]
    memo[0][0] = 1
    for i in range(n):
        for j in range(max_k + 1):
            if memo[i][j] == 1: 
                memo[i+1][j] = 1 
                if i != index and j+a[i] <= max_k:
                    memo[i+1][j+a[i]] = 1 
    return (1 in memo[n][max(k-a[index], 0):k])

l = -1
r = n
while r-l > 1:
    mid = (l+r) // 2
    if not check_needed(mid):
        r = mid
    else:
        l = mid
if sum(a) < k:
    print(n)
else:
    print(n - r)

Submission status: Time Limit Exceeded

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

sum_possibility = [0] * 10001
sum_possibility[0] = 1

for i in range(n+1):
    if sum(sum_possibility[max(0, k-sum(a[i:])):k]) == 0:
        break
    for j in range(10000, -1, -1):
        if sum_possibility[j] is not 0 and j + a[i] < 10001:
            sum_possibility[j + a[i]] = 1
print(n-i)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
import bisect
idx=bisect.bisect_left(A,K)
ans=0
A=A[:idx]
N=idx
from collections import defaultdict
def search(i):
    dp=defaultdict(int)
    dp[0]=1
    ai=A[i]
    for j in range(N):
        dpc=dp.copy()
        if i==j:continue
        for k in dpc.keys():
            if k+A[j]>=K or dpc[k]==0:
                continue
            if k+A[j]>=K-ai:
                return True
            dp[k+A[j]]=1
    return False
MinTrue=N
MaxFalse=-1
check=(1,2)
while MinTrue-MaxFalse>1:
    idx=N*check[0]//check[1]
    if search(idx):
        MinTrue=min(MinTrue,idx)
        check=(check[0]*2-1,check[1]*2)
    else:
        MaxFalse=max(MaxFalse,idx)
        check=(check[0]*2+1,check[1]*2)
print(MinTrue)

Submission status: Time Limit Exceeded

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    dp = [[False] * (K) for _ in range(N)]

    def need(i: int) -> bool:
        for n in range(N):
            for k in range(K):
                dp[n][k] = False
        dp[0][0] = True

        card_num, n = 0, 0
        for a in A:
            n += 1
            if n-1 == i:
                continue
            for k in range(K):
                dp[card_num + 1][k] = \
                    dp[card_num][k] or (a <= k and dp[card_num][k - a])
            card_num += 1

        for k in range(max(K - A[i], 0), K):
            if dp[N - 1][k]:
                return True
        return False

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l+1


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    def need(i: int)->bool:
        dp = [[False] * (K) for _ in range(N)]
        dp[0][0] = True

        card_num = 0
        for n, a in enumerate(A):
            if n == i:
                continue
            for k in range(K):
                dp[card_num + 1][k] = \
                    dp[card_num][k] or (a <= k and dp[card_num][k - a])
            card_num += 1

        # return any(dp[N - 1][max(K - A[i], 0):])
        for k in range(max(K - A[i], 0), K):
            if dp[N - 1][k]:
                return True
        return False

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l+1


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    def need(i: int)->bool:
        dp = [[False] * (K) for _ in range(N)]
        dp[0][0] = True

        card_num = 0
        for n, a in enumerate(A):
            if n == i:
                continue
            for k in range(K):
                dp[card_num + 1][k] = \
                    dp[card_num][k] or (a <= k and dp[card_num][k - a])
            card_num += 1

        return any(dp[N - 1][max(K - A[i], 0):])

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l+1


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    def need(i: int)->bool:
        dp = [[False] * (K) for _ in range(N)]
        dp[0][0] = True

        for n, a in enumerate(A[:i] + A[i+1:]):
            for k in range(K):
                dp[n + 1][k] = dp[n][k] or (a <= k and dp[n][k - a])

        return any(dp[N - 1][max(K - A[i], 0):])

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l+1


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Time Limit Exceeded

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

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

MIN=-1
MAX=A.index(MAX_NO_NEED)-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: Time Limit Exceeded

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

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

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

MIN=-1
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: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
def DP(N,K,A,i):
    Ac=A.copy()
    a_check=Ac.pop(i)
    if a_check>=K:
        return True
    dp=[0]*(K-a_check+1)
    dp[0]=1
    for a in Ac:
        dpc=dp.copy()
        for k in range(K-a_check+1):
            if dpc[k]==0:continue
            else:
                if k+a<K-a_check:
                    dp[k+a]=1
                elif K-a_check<=k+a<K:
                    return True
    return False

def bisect(N,K,A,check,maxFalse,minTrue):
    idx=N*check[0]//check[1]
    if DP(N,K,A,idx)==True:
        if maxFalse==idx-1:
            return maxFalse
        return bisect(N,K,A,(check[0]*2-1,check[1]*2),maxFalse,min(minTrue,idx))
    else:
        if minTrue==idx+1:
            return idx
        return bisect(N,K,A,(check[0]*2+1,check[1]*2),max(maxFalse,idx),minTrue)

print(bisect(N,K,A,(1,2),-1,N)+1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
cnt=0
for i in range(N):
    a=A[i]
    if a>=K:
        cnt+=1
        continue
    Ac=A.copy()
    Ac.pop(i)
    dp=[0]*(K-a+1)
    dp[0]=1
    for b in Ac:
        dpc=dp.copy()
        for k in range(K-a+1):
            if k+b>=K:break
            if k+b<K-a:
                dp[k+b]+=dpc[k]
            elif k+b>=K-a:
                dp[K-a]+=dpc[k]
        if dp[K-a]>0:
            cnt+=1
            break
print(N-cnt)

Submission status: Time Limit Exceeded

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    if a[m] >= k:
        r = m
        continue
    dp = [set() for _ in range(n + 1)]
    dp[0].add(0)
    check = 0
    for i in range(n):
        if i == m:
            dp[i + 1] = dp[i]
            continue
        for x in dp[i]:
            dp[i + 1].add(x)
            temp = x + a[i]
            if k - a[m] <= temp < k:
                check = 1
                break
            elif temp < k - a[m]:
                dp[i + 1].add(temp)
        if check == 1:
            break
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Time Limit Exceeded

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    if a[m] >= k:
        r = m
        continue
    dp = set()
    dp.add(0)
    check = 0
    for i in range(n):
        next = set()
        if i == m:
            continue
        for x in dp:
            temp = x + a[i]
            if k - a[m] <= temp < k:
                check = 1
                break
            elif temp < k - a[m]:
                next.add(temp)
        if check == 1:
            break
        else:
            dp = dp | next
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Time Limit Exceeded

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    if a[m] >= k:
        r = m
        continue
    dp = [[0 for _ in range(k)] for _ in range(n)]
    dp[0][0] = 1
    t = 1
    check = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k - a[i]):
            if dp[t - 1][j] == 1:
                dp[t][j] = 1
                temp = j + a[i]
                if k - a[m] <= temp < k:
                    check = 1
                    break
                elif temp < k - a[m]:
                    dp[t][temp] = 1
        if check == 1:
            break
        t += 1
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
dpl=[[0 for y in range(K)] for x in range(N+1)]
dpr=[[0 for y in range(K)] for x in range(N+1)]
dpl[0][0]=1
dpr[N][0]=1
for x in range(N):
    for y in range(K):
        if dpl[x][y]==1:
            dpl[x+1][y]=1
            if 0<=y+a[x]<K:
                dpl[x+1][y+a[x]]=1
        if dpr[N-x][y]==1:
            dpr[N-1-x][y]=1
            if 0<=y+a[N-1-x]<K:
                dpr[N-1-x][y+a[N-1-x]]=1
ans=0
for x in range(N):
    Sx=[0 for i in range(K+1)]
    for i in range(K):
        Sx[i+1]=Sx[i]+dpl[x][i]
    #print(dpl[x],Sx,dpr[x+1],"range({0},{1})=[{0},{2}]".format(K-a[x],K,K-1))
    flag=0
    for y in range(K):
        if dpr[x+1][y]==1:
            if Sx[K-y]-Sx[max(K-y-a[x],0)]>0:
                flag=1
                break
            #print(Sx[K-y],Sx[K-y-a[x]])
    if flag==0:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
# 大きい方から試したいので逆順でループ回す
for i in range((1 << len(aN2))-1, -1, -1):
    # 全部合わせても足りないようじゃ論外
    if sum(aN2) < K:
        break
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
    # 最後まで足りなかったら、これ以降も足りないので終了
    else:
        break
print(need.count(False))

Submission status: Time Limit Exceeded

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
for i in range(1 << len(aN2)):
    # 全部合わせても足りないようじゃ論外
    if sum(aN2) < K:
        break
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
print(need.count(False))

Submission status: Time Limit Exceeded

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

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_right

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

aN.sort()
# 単体で条件を満たすものは必要確定なので除く
aN2 = aN[:bisect_right(aN, K)]
aN2.reverse()

need = [False] * len(aN2)
for i in range(1 << len(aN2)):
    sm = 0
    for j in range(len(aN2)):
        if 1 & i>>j == 1:
            sm += aN2[j]
        # 複数で条件を満たせば、それに含まれるものは必要
        if sm >= K:
            for k in range(j+1):
                if 1 & i>>k == 1:
                    need[k] = True
            break
print(need.count(False))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from itertools import accumulate
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # K以上の数はすべて必要なのでA未満の数だけを考える
    A = sorted([a for a in A if a < K], reverse=True)
    N = len(A)

    # dp1[i][k] := 1 ~ iまでのカードを使って数kが作れるか
    dp1 = [[0] * (K + 1) for i in range(N + 1)]
    dp1[0][0] = 1
    # dp2[i][k] := N ~ iまでのカードを使って数kが作れるか
    dp2 = [[0] * (K + 1) for i in range(N + 1)]
    dp2[0][0] = 1

    # dpテーブルを計算
    for i in range(1, N + 1):
        for k in range(K + 1):
            dp1[i][k] = max(dp1[i][k], dp1[i - 1][k])
            if A[i - 1] <= k:
                dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - A[i - 1]])

            dp2[i][k] = max(dp2[i][k], dp2[i - 1][k])
            if A[N - i] <= k:
                dp2[i][k] = max(dp2[i][k], dp2[i - 1][k - A[N - i]])

    # 累積和を取っておく
    for i in range(N + 1):
        dp2[i] = list(accumulate(dp2[i]))

    # ansを計算
    need = 0
    for i in range(1, N + 1):
        for k in range(K + 1):
            # 1 ~ i番目まででkが作れない
            if not dp1[i - 1][k]:
                continue

            # 1 ~ i番目までだけで必要な条件が作れる
            if K - A[i - 1] <= k < K:
                need += 1
                break

            # 範囲外参照
            if K - A[i - 1] - k - 1 < 0:
                continue

            if dp2[N - i][K - k] - dp2[N - i][K - A[i - 1] - k - 1] > 0:
                need += 1
                break

    print(N - need)

main()

Submission status: Time Limit Exceeded

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

# K以上の数はすべて必要なのでA未満の数だけを考える
A = sorted([a for a in A if a < K], reverse=True)
N = len(A)

# dp1[i][k] := 1 ~ iまでのカードを使って数kが作れるか
dp1 = [[0] * (K + 1) for i in range(N + 1)]
dp1[0][0] = 1
# dp2[i][k] := N ~ iまでのカードを使って数kが作れるか
dp2 = [[0] * (K + 1) for i in range(N + 1)]
dp2[0][0] = 1

# dpテーブルを計算
for i in range(1, N + 1):
    for k in range(K + 1):
        dp1[i][k] = max(dp1[i][k], dp1[i - 1][k])
        if A[i - 1] <= k:
            dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - A[i - 1]])

        dp2[i][k] = max(dp2[i][k], dp2[i - 1][k])
        if A[N - i] <= k:
            dp2[i][k] = max(dp2[i][k], dp2[i - 1][k - A[N - i]])

# 累積和を取っておく
for i in range(N + 1):
    dp2[i] = list(accumulate(dp2[i]))

# ansを計算
need = 0
for i in range(1, N + 1):
    for k in range(K + 1):
        # 1 ~ i番目まででkが作れない
        if not dp1[i - 1][k]:
            continue

        # 1 ~ i番目までだけで必要な条件が作れる
        if K - A[i - 1] <= k < K:
            need += 1
            break

        # 範囲外参照
        if K - A[i - 1] - k - 1 < 0:
            continue

        if dp2[N - i][K - k] - dp2[N - i][K - A[i - 1] - k - 1] > 0:
            need += 1
            break

print(N - need)

Submission status: Time Limit Exceeded

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

# K以上の数は常に必要
A = sorted([a for a in A if a < K])

# すべての数が必要
if not A:
    print(0)
    exit()

# 絶対に不要な数0、絶対に必要な数を架空のカードとして追加
A = [0] + A + [float('inf')]

N = len(A)
# にぶたん: 数Xが不要である
ok, ng = -1, N  # indexで管理することに注意
while abs(ok - ng) > 1:
    Xi = (ok + ng) // 2
    X = A[Xi]    # X抜きのリストを作る
    A2 = A[:]
    A2.remove(X)

    creatable = {0}
    flg = False  # 二重ループ抜け用
    for a in A2:
        # 架空のカードははじく
        if a == 0 or a == float('inf'):
            continue

        tmp = set()
        for n in creatable:
            # Xは必要
            if K - X <= n + a < K:
                ng = Xi
                flg = True
                break

            else:
                tmp.add(n)
                tmp.add(n + a)

        if flg:
            break
        creatable = tmp

    else:
        # Xは不要
        ok = Xi

print(ok)

Submission status: Time Limit Exceeded

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


ans=0
for i in range(n):
    if(A[i] >=k):
        ans+=1
        continue
    bitwa=1
    for j in range(n):
        if(A[i] < k and j !=i):
            bitwa = bitwa | bitwa<<A[j]

    bitwa = bitwa >> (k-A[i])
    for j in range(A[i]):
        if(bitwa & 1<<j):
            ans+=1
            break

print(n-ans)

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
A=list(map(int,input().split()))
bitwa=1
for i in range(n):
    if(A[i] < k):
        bitwa = bitwa | bitwa<<A[i]

ans=0
for i in range(n):
    if(A[i] >=k):
        ans+=1
        continue
    bitwa=1
    for j in range(n):
        if(A[i] < k and j !=i):
            bitwa = bitwa | bitwa<<A[j]

  
    for j in range(k-A[i],k):
        if(bitwa & 1<<j):
            ans+=1
            break

print(n-ans)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in 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
if ans != N:
    ans = N-ans-1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in enumerate(a):
    if Smax + a_ >= K:
        ans = N-i-1
    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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in enumerate(a):
    if Smax + a_ >= K:
        ans = N-i-1
    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 = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()

def DP(L, a, b):
    D = [False for i in range(K+1)]
    D[0] = True
    for i in range(len(L)):
        if L[i] < K:
            for j in reversed(range(K-L[i]+1)):
                D[j+L[i]] = D[j]
    if True in D[a:b+1]:
        return True
    else:
        return False

low, high = 0, N+1
while high - low > 1:
    L = copy.deepcopy(A)
    mid = (high + low)//2
    l = L.pop(mid-1)
    if l >= K:
        high = mid
    else:
        if DP(L, K-l, K-1):
            high = mid
        else:
            low = mid

print(low)