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:
# -*- coding: utf-8 -*-

import sys
import numpy as np

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

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

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

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros(K, dtype=np.bool)
    prev = np.zeros(K, dtype=np.bool)
    dp[0] = 1
    for i in range(N):
        # まとめて遷移
        if i != omit and A[i] < K:
            prev[A[i]:] |= dp[:K-A[i]]
        dp = prev.copy()
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))

Submission status: Wrong Answer

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

import sys
import numpy as np

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

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

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

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros(K, dtype=np.bool)
    dp[0] = 1
    for i in range(N):
        if i != omit and A[i] < K:
            # まとめて遷移
            dp[A[i]:] |= dp[:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))

Submission status: Wrong Answer

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

import sys

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

N, K = MAP()
A = [0] + LIST() + [0]

# 部分和DP
dp = list2d(N+2, K, 0)
dp[0][0] = 1
for i in range(1, N+1):
    for j in range(K):
        dp[i][j] |= dp[i-1][j]
        if j-A[i] >= 0:
            dp[i][j] |= dp[i-1][j-A[i]]

# Nについて後ろから同じDP
redp = list2d(N+2, K, 0)
redp[N+1][0] = 1
for i in range(N, 0, -1):
    for j in range(K):
        redp[i][j] |= redp[i+1][j]
        if j-A[i] >= 0:
            redp[i][j] |= redp[i+1][j-A[i]]

ans = 0
for i in range(1, N+1):
    # 今回の値A[i]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[i]), K):
        # 自分を除いた結果と比べるには、前から来て1つ前までと、後ろから来て1つ後までを合わせればいい
        if dp[i-1][j] or redp[i+1][j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
end = bisect.bisect_right(a, k)
a = a[0:end]
n = len(a)

def subset_sum(mid):
    dp = [False]*k
    dp[0] = True    
    for i in range(n):
        if i == mid:
            continue
        for j in range(k)[::-1]:
            if j - a[i] < 0:
                break
            else:
                dp[j] |= dp[j - a[i]]
    return sum(dp[k-a[mid]:])
  
ok = -1
ng = n
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if subset_sum(mid):
        ng = mid
    else:
        ok = mid
print(0)

Submission status: Wrong Answer

Solution code:
import bisect


n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
end = bisect.bisect_right(a, k)
a = a[0:end]
n = len(a)

def subset_sum(mid):
    pos = k - a[mid]
    dp = [False]*k
    dp[0] = True    
    for i in range(n):
        if i == mid:
            continue
        for j in range(k)[::-1]:
            if j - a[i] < 0:
                break
            else:
                dp[j] |= dp[j - a[i]]
        if pos <= j and dp[j]:
            return True
    return False
  
ok = -1
ng = n
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if subset_sum(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Wrong Answer

Solution code:
import bisect


n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
end = bisect.bisect_right(a, k)
a = a[0:end]
n = len(a)

def subset_sum(mid):
    pos = k - a[mid]
    dp = [False]*k
    dp[0] = True    
    for i in range(n):
        if i == mid:
            continue
        for j in range(k)[::-1]:
            if j - a[i] < 0:
                break
            else:
                dp[j] |= dp[j - a[i]]
        if pos - a[mid] <= j and dp[j]:
            return True
    return False
  
ok = -1
ng = n
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if subset_sum(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Wrong Answer

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

A.sort()
# print(A)
A_set = list(set(A))

le = -1
ri = len(A_set)
mid = (le + ri) // 2

while ri - le > 1:
    need = 0
    #print(le,ri,mid)

    DP = [0 for i in range(k)]
    DP[0] = 1
    jogai = 0
    for i in range(n):
        #print(DP)
        if jogai == 0 and A[i] == A_set[mid]:
            jogai = 1
        else:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            # print(j)
    
            #print(DP)
        for p in range(max(0, k-A_set[mid]), k):
            if DP[p] == 1:
                need = 1
                break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2


if le == -1:
    print(0)
else:
    jougen = A_set[le]
    ans = 0
    for i in range(n):
        if A[i] <= jougen:
            ans += 1
    print(ans)

Submission status: Wrong Answer

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

A.sort()
# print(A)
A_set = list(set(A))

le = -1
ri = len(A_set)
mid = (le + ri) // 2

while ri - le > 1:
    need = 0
    #print(le,ri,mid)

    DP = [0 for i in range(k)]
    DP[0] = 1
    jogai = 0
    for i in range(n):
        #print(DP)
        if jogai == 0 and A[i] == A_set[mid]:
            jogai = 1
        else:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            # print(j)
    
            #print(DP)
        for p in range(max(0, k-A_set[mid]), k):
            if DP[p] == 1:
                need = 1
                break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2


jougen = A_set[le]
ans = 0
for i in range(n):
    if A[i] <= jougen:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

A.sort()
# print(A)

le = -1
ri = len(A)
mid = (le + ri) // 2
while ri - le > 1:
    need = 0
    # print(le,ri,mid)
    DP = [0 for i in range(k)]
    DP[0] = 1
    for i in range(n):
        #print(DP)
        if i != mid:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            # print(j)
    
            #print(DP)
            for p in range(max(0, k-A[mid]), k):
                if DP[p] == 1:
                    need = 1
                    break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2

print(le + 1)

Submission status: Wrong Answer

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

A.sort()
# print(A)

le = 0
ri = len(A)
mid = (le + ri) // 2
while ri - le > 1:
    # print(le,ri,mid)
    DP = [0] * k
    DP[0] = 1
    for i in range(n):
        #print(DP)
        if i != mid:
            for p in range(k-1, -1, -1):
                if p-A[i] >= 0:
                    DP[p] = int(DP[p-A[i]] or DP[p])
        # print(j)
    need = 0
    # print(DP[-1])
    for p in range(max(0, k-A[mid]), k):
        if DP[p] == 1:
            need = 1
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2

print(le + 1)

Submission status: Wrong Answer

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

A.sort()
# print(A)

le = 0
ri = len(A)
mid = (le + ri) // 2
while ri - le > 1:
    # print(le,ri,mid)
    DP = [[0] * k for i in range(n)]
    DP[0][0] = 1
    j = 0
    for i in range(n):
        #print(DP)
        if i != mid:
            for p in range(0, k):
                if p-A[i] >= 0:
                    DP[j+1][p] = int(DP[j][p-A[i]] or DP[j][p])
                else:
                    DP[j+1][p] = DP[j][p]
            j += 1
        # print(j)
    need = 0
    # print(DP[-1])
    for p in range(max(0, k-A[mid]), k):
        if DP[-1][p] == 1:
            need = 1
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2

print(le + 1)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import *
mod = 10**9+7

N, K = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
t = bisect_left(a, K)
l, r = 0, t
while l+1 < r:
    m = (l+r)//2
    dp = [[0] * K for i in range(t)]
    dp[0][0] = 1
    for i, x in enumerate(a[:m]+a[m+1:t]):
        for j in range(K):
            if dp[i][j] and j+x < K:
                dp[i+1][j+x] = 1
    dp = dp[-1]
    for i in range(K-a[m], K):
        if dp[i]:
            r = m
            break
    else:
        l = m
print(r)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import *
mod = 10**9+7

N, K = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()
t = bisect_left(a, K)
l, r = 0, t
while l+1 < r:
    m = (l+r)//2
    dp = set()
    dp.add(0)
    for x in a[:m]+a[m+1:t]:
        dpp = dp.copy()
        for k in dpp:
            if k+x < K:
                dp.add(k+x)
    dp.remove(0)
    for i in range(K-a[m], K):
        if i in dp:
            r = m
            break
    else:
        l = m
print(r)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x: continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                if dp[j - ai]:
                    dp[j] = True
                    if kx <= j:
                        return True
        return False
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x: continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                ji = j - ai
                if dp[ji]:
                    if kx <= j:
                        return True
                    dp[j] = True
        return False
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x:
                continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                ji = j - ai
                if dp[ji]:
                    if kx <= j:
                        return True
                    dp[j] = True
        return False
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x:
                continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                ji = j - ai
                if dp[j]:
                    if kx <= ji:
                        return True
                    dp[ji] = True
        return False
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x:
                continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                ji = j + ai
                if dp[j]:
                    if kx <= ji:
                        return True
                    dp[ji] = True
        return False
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = 0
    ng = n
    def f(x):
        dp = [[False] * (k + 1) for i in range(n)]
        for i in range(n):
            dp[i][0] = True
        for i in range(n):
            for j in range(k+1):
                if i == x:
                    dp[i][j] |= dp[i - 1][j]
                else:
                    if j >= a[i]:
                        dp[i][j] |= dp[i][j - a[i]]
                    dp[i][j] |= dp[i-1][j]
        for i in range(a[x], k + 1):
            if dp[-1][i]:
                return True
        return False
    if sum(a) <= k:
        print(n)
        return
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok-1)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n,k=MI()
a=LI()
a.sort()
m=n
for i in range(n):
    if a[i]>k:
        m=i
        break

ans=0
dp=[0 for _ in range(k+1)]
#a_req=[0]*(k+1)
a_req=[[0]*(k+1) for _ in range(k+1)]


for i in range(m):
    for j in range(k+1):
        if dp[j]!=0 and j+a[i]<=k:
            dp[j+a[i]]=1
            a_req[j+a[i]][a[i]]=min(a_req[j+a[i]][a[i]],1+a_req[j][a[i]])
    if dp[a[i]]==0:
        a_req[a[i]][a[i]]=1
        dp[a[i]]=1
    
print(dp,a_req)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    while abs(ok - ng) > 1:
        j = (ok + ng) // 2
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [[False]*K for _ in range(N-1)]
        DP[0][A[0]] = True
        for i in range(1, N-1):
            DP[i][:] = DP[i-1]
            for k in range(K):
                # DP[i][k] = DP[i-1][k] or DP[i][k]
                if k < K-A[i]:
                    DP[i][k+A[i]] = DP[i-1][k]
        if any(DP[-1][max(K-a[j], 0):]):
            ok = j
        else:
            ng = j
    print(ok)

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

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    while abs(ok - ng) > 1:
        j = (ok + ng) // 2
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [[False]*K for _ in range(N-1)]
        DP[0][A[0]] = True
        for i in range(1, N-1):
            for k in range(K):
                DP[i][k] = DP[i-1][k]
                if k < K-A[i]:
                    DP[i][k+A[i]] = DP[i-1][k]
        if any(DP[-1][max(K-a[j], 0):]):
            ok = j
        else:
            ng = j
    print(ok)

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

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    while abs(ok - ng) > 1:
        j = (ok + ng) // 2
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [False]*K
        DP[A[0]] = True
        for i in range(1, N-1):
            for k in range(K, -1, -1):
                if k < K-A[i]:
                    DP[k+A[i]] = DP[k]
        if any(DP[max(K-a[j], 0):]):
            ok = j
        else:
            ng = j
    print(ok)

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