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: Wrong Answer

Solution code:
from itertools import accumulate

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

main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
N = len(A)
dp_init = lambda x:True if x == 0 else False
#Aの左からと右から加えていく場合のdpテーブルを作成
ldp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
rdp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
for i in range(N):
    for j in range(K):
        ldp[i+1][j] = (lambda:ldp[i][j] if j < A[i] else ldp[i][j] | ldp[i][j-A[i]])()
        rdp[i+1][j] = (lambda:rdp[i][j] if j < A[N-1-i] else rdp[i][j] | rdp[i][j-A[N-1-i]])()

def dpAny(n,m): #== any(ldp[n][m] & rdp[N-n-1][m-j] for j in range(i+1))
    for j in range(m+1):
        if ldp[n][j] & rdp[N-n-1][m-j]:
            return True
    return False

def NoNeed(n):
    #ldp[n]とrdp[N-1-n]でA[n]を含まない部分集合の取り得る和が求められる。
    dp = [dpAny(n,i) for i in range(K-A[n],K)]
    return 1 if not any(dp) else 0

ans = 0
for i in range(N):
    ans += NoNeed(i)
print(NoNeed)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
N = len(A)
dp_init = lambda x:True if x == 0 else False
#Aの左からと右から加えていく場合のdpテーブルを作成
ldp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
rdp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
for i in range(N):
    for j in range(K):
        ldp[i+1][j] = (lambda:ldp[i][j] if j < A[i] else ldp[i][j] | ldp[i][j-A[i]])()
        rdp[i+1][j] = (lambda:rdp[i][j] if j < A[N-1-i] else rdp[i][j] | rdp[i][j-A[N-1-i]])()

def dpAny(n,m): #== any(ldp[n][m] & rdp[N-n-1][m-j] for j in range(i+1))
    for j in range(m+1):
        if ldp[n][m] & rdp[N-n-1][m-j]:
            return True
    return False

def NoNeed(n):
    #ldp[n]とrdp[N-1-n]でA[n]を含まない部分集合の取り得る和が求められる。
    dp = [dpAny(n,i) for i in range(K-A[n],K)]
    return 1 if not any(dp) else 0

ans = 0
for i in range(N):
    ans += NoNeed(i)
print(NoNeed)

Submission status: Wrong Answer

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Aiが必要か否か
    if A[n] > K:
        return
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(N)]  # dp[i][j] = B1~Biを用いてKを作れるか
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K):
            if j >= b:
                dp[i][j] = dp[i-1][j] | dp[i-1][j-b]
            else:
                dp[i][j] = dp[i-1][j]
    if sum(dp[N-1][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def check(x):
    if x >= K:
        return True
    dp = [False] * (K + 1)
    dp[0] = True
    for j, a in enumerate(A):
        if j == x:
            continue
        for i in range(K, 0, -1):
            if i >= a:
                dp[i] |= dp[i - a]
    for i in range(K - x, K):
        if dp[i]:
            return True
    return False
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

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

def check(x):
    if x >= K:
        return True
    A2 = [A[i] for i in range(N) if i != x]
    dp = [0] * (K + 1)
    dp[0] = 1
    for a in A2:
        for i in range(K, 0, -1):
            if i >= a:
                dp[i] += dp[i - a]
    for i in range(K - x, K):
        if dp[i] > 0:
            return True
    return False
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dp = [0] * (K + 1)
dp[0] = 1
for a in A:
    for i in range(K, 0, -1):
        if i >= a:
            dp[i] += dp[i - a]
ans = 0
for a in A:
    x = K - a
    if x <= 0:
        ans += 1
        continue
    necessary = False
    for i in range(x, K):
        if i >= a:
            if dp[i] - dp[i - a] >= 1:
                necessary = True
        else:
            if dp[i] >= 1:
                necessary = True
    if necessary:
        ans += 1
print(N - ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

dp = [0] * (K + 1)
dp[0] = 1
for a in A:
    for i in range(K, 0, -1):
        if i >= a:
            dp[i] += dp[i - a]
ans = 0
for a in A:
    x = K - a
    if x < 0:
        ans += 1
        continue
    necessary = False
    for i in range(x, K):
        if i >= a:
            if dp[i] - dp[i - a] >= 1:
                necessary = True
        else:
            if dp[i] >= 1:
                necessary = True
    if necessary:
        ans += 1
print(N - ans)

Submission status: Wrong Answer

Solution code:
def partial_solution(N, K, A):
    # O(K * N**2)解法
    #     「aが不必要」
    #     ＝「aを含む良い集合の数字の和は K+a 以上」
    #     ＝「a以外の数字の組み合わせで K-a ～ K-1 は作れない」
    cnt = 0
    for i in range(N):
        # dp[n][k]: n番目（1-indexed）までの数字の和でkを作れるか否か
        dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N):
            a = A[j]
            if j == i:
                for k in range(K + 1):
                    # i番目（0-indexed）のAは使わない
                    dp[j + 1][k] = dp[j][k]
            else:
                for k in range(K + 1):
                    v = dp[j][k]
                    if k >= a:
                        v = max(v, dp[j][k - a])
                    dp[j + 1][k] = v
        lb, ub = max(0, K - A[i]), K - 1
        if sum(dp[N][lb:(ub + 1)]) == 0:
            cnt += 1
    return cnt


def solution(N, K, A):
    # O(K * (log K) * N)解法
    #     partial_solutionの改良。
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    import bisect
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    dp1 = [[0 for _ in range(K + 1)] for _ in range(N)]
    dp2 = [[0 for _ in range(K + 1)] for _ in range(N)]
    dp1[0][0] = 1
    dp1[0][min(A[0], K)] = 1
    dp2[N - 1][0] = 1
    dp2[N - 1][min(A[N - 1], K)] = 1
    for i in range(1, N):
        j = N - 1 - i
        a1, a2 = A[i], A[j]
        for k in range(K + 1):
            v1, v2 = dp1[i - 1][k], dp2[j + 1][k]
            if k >= a1:
                v1 = max(v1, dp1[i - 1][k - a1])
            if k >= a2:
                v2 = max(v2, dp2[j + 1][k - a2])
            dp1[i][k] = v1
            dp2[j][k] = v2
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    for i in range(N):
        left_list = [0]  # i == 0
        if i > 0:
            left_list = [k for k in range(K + 1) if dp1[i - 1][k] == 1]
        right_list = [0]  # i == N - 1
        if i < N - 1:
            right_list = [k for k in range(K + 1) if dp2[i + 1][k] == 1]
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: left_listの要素, y: right_listの要素
        a = A[i]
        can_make = False
        for x in left_list:
            index1 = bisect.bisect_right(right_list, K - a - x)
            index2 = bisect.bisect_right(right_list, K - 1 - x)
            if index1 != index2:
                can_make = True
                break
        if not can_make:
            cnt += 1
    return cnt


def check():
    import random
    random.seed(0)
    for N in range(1, 202, 50):
        for K in range(1, 202, 50):
            A = random.choices(range(1, 10**9+1), k=N)
            print('Checking: N={}, K={}'.format(N, K))
            assert solution(N, K, A) == partial_solution(N, K, A)
    print('OK')


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


if __name__ == '__main__':
    main()
    # check()

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    """
    rdp = [[0] * K for _ in range(N)]  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
    rdp[0][0] = 1
    for i in range(1, N):
        for j in range(K):
            if rdp[i - 1][j] == 1 or (j >= A[-i] and rdp[i - 1][j - A[-i]] == 1):
                rdp[i][j] = 1

    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] + rdp[i - 1][j]
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            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)
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x) < K]
a.sort()

def renew_dp(dp, List, K): #Listの部分和がiとなりうるならばdp[i]=True
    dp_ = dp.copy()
    for x in List:
        for i in range(x,K):
            if dp_[i]: continue 
            if dp[i-x]: dp_[i] = True
        dp = dp_
    return dp_


def binary_tree(List, base_List, K): #2分探索
    if len(List) == 0: return 0 #不要札無し
    center = len(List)//2 #2分する支点
    dp = collections.defaultdict(lambda:False)
    dp[0] = True
    List_without_center = base_List.copy()
    List_without_center.remove(List[center])
    dp = renew_dp(dp, List_without_center, K) #dp更新
    if any(dp[i] for i in range(K-List[center],K)): #必要(True)か不必要(False)かジャッジ
        result = center if len(List)==1 else binary_tree(List[:center], base_List, K) #2分木の末端まで再帰
    else:
        result = center+1 if len(List)==1 else binary_tree(List[center:], base_List, K) + center
    return result

ans = binary_tree(a, a, K) #ans以下のjについて、a[j]は不必要
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, K = map(int, input().split())
a = [int(x) for x in input().split() if int(x) < K]
a.sort()

def renew_dp(dp, List, K): #Listの部分和がiとなりうるならばdp[i]=True
    dp_ = dp.copy()
    for x in List:
        for i in range(x,K):
            if dp_[i]: continue 
            if dp[i-x]: dp_[i] = True
    return dp_


def binary_tree(List, base_List, K): #2分探索
    if len(List) == 0: return 0 #不要札無し
    center = len(List)//2 #2分する支点
    dp = collections.defaultdict(lambda:False)
    dp[0] = True
    List_without_center = base_List.copy()
    List_without_center.remove(List[center])
    dp = renew_dp(dp, List_without_center, K) #dp更新
    if any(dp[i] for i in range(K-List[center],K)): #必要(True)か不必要(False)かジャッジ
        result = center if len(List)==1 else binary_tree(List[:center], base_List, K) #2分木の末端まで再帰
    else:
        result = center+1 if len(List)==1 else binary_tree(List[center:], base_List, K) + center
    return result

ans = binary_tree(a, a, K) #ans以下のjについて、a[j]は不必要
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
no_need = 0
no_good_set = 0
for i in range(N):
    total = a[i]
    for j in range(0,N):
        if j == i: continue
        total += a[j]
        if total < K: continue
        if total - a[i] >= K:
            no_need += 1
        break
    else:
        no_good_set += 1
if no_good_set == N: no_need = N   
print(no_need)

Submission status: Wrong Answer

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

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

    a[mid] ^= a[n - 1]
    a[n - 1] ^= a[mid]
    a[mid] ^= a[n - 1]

    dp = [[False for j in range(k)] for i in range(n)]
    dp[0][0] = True

    for i in range(n - 1):
        for j in range(k):
            dp[i + 1][j] = dp[i + 1][j] or dp[i][j]
            if j + a[i] < k:
                dp[i + 1][j + a[i]] = dp[i + 1][j + a[i]] or dp[i][j]
    
    flg = False
    for j in range(max(0, k - a[n - 1]), k):
        if dp[n - 1][j]:
            flg = True
            break
    
    if flg:
        ok = mid
    else:
        ng = mid

    a[mid] ^= a[n - 1]
    a[n - 1] ^= a[mid]
    a[mid] ^= a[n - 1]

print(ok)

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = 0
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = (dp > mask>>A[i])

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = 1
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = (dp > mask>>A[i])

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1



    noneed = 0; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = ((dp << (A[i])) > mask)

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()

    dp_L = [[False]*K for _ in range(N+1)]
    dp_R = [[False]*K for _ in range(N+1)]
    dp_L[0][0] = True
    dp_R[N][0] = True
    for i in range(N):
        a = A[i]
        for k in range(K):
            if not dp_L[i][k]:
                continue
            dp_L[i+1][k] = True
            if k+a<K:
                dp_L[i+1][k+a] = True

    for i in range(N)[::-1]:
        a = A[i]
        for k in range(K):
            if not dp_R[i+1][k]:
                continue
            dp_R[i][k] = True
            if k+a<K:
                dp_R[i][k+a] = True

    """
        for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)
    
        noneed = -1; need = N
    while(need-noneed>1):
        i = (need+noneed)//2
        a = A[i]
        is_need = False
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                is_need = True
                break

            l += 1

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    """
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()

    dp_L = [set() for _ in range(N+1)]
    dp_R = [set() for _ in range(N+1)]
    dp_L[0].add(0)
    dp_R[N].add(0)
    for i in range(N):
        a = A[i]
        for n in dp_L[i]:
            dp_L[i+1].add(n)
            if n+a<K:
                dp_L[i+1].add(n+a)

    for i in range(N)[::-1]:
        a = A[i]
        for n in dp_R[i+1]:
            dp_R[i].add(n)
            if n+a<K:
                dp_R[i].add(n+a)

    """
        for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)
    
        noneed = -1; need = N
    while(need-noneed>1):
        i = (need+noneed)//2
        a = A[i]
        is_need = False
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                is_need = True
                break

            l += 1

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    """
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()

    dp_L = [set() for _ in range(N+1)]
    dp_R = [set() for _ in range(N+1)]
    dp_L[0].add(0)
    dp_R[N].add(0)
    for i in range(N):
        a = A[i]
        for n in dp_L[i]:
            dp_L[i+1].add(n)
            if n+a<K:
                dp_L[i+1].add(n+a)

    for i in range(N)[::-1]:
        a = A[i]
        for n in dp_R[i+1]:
            dp_R[i].add(n)
            if n+a<K:
                dp_R[i].add(n+a)

    for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)
    """
        noneed = -1; need = N
    while(need-noneed>1):
        i = (need+noneed)//2
        a = A[i]
        is_need = False
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                is_need = True
                break

            l += 1

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    """
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""