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

import sys
from collections import defaultdict
from bisect import bisect_left

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

# 部分和DPを変形させて、その値になるのに使われた値の集合を持っておく
dp = defaultdict(set)
dp[0].add(0)
for i in range(N):
    for j in range(K-1, -1, -1):
        if len(dp[j]):
            dp[j+A[i]] |= dp[j]
            dp[j+A[i]].add(A[i])

# 和がK未満の集合はこの後のチェックで使わないので削る
dp = sorted(dp.items())
keys, sets = zip(*dp)
idx = bisect_left(keys, K)
keys = keys[idx:]
sets = sets[idx:]

ans = 0
for i in range(N):
    for k, s in zip(keys, sets):
        # A[i]減らしたらK未満になる状況で、一度でもA[i]が使われていれば必要
        if k-A[i] < K and A[i] in s:
            break
    else:
        # 該当するどの集合でも、一度も使われていなければ不要
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict

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

# 部分和DPを変形させて、その値になるのに使われた値の集合を持っておく
dp = defaultdict(set)
dp[0].add(0)
for i in range(N):
    for j in range(K-1, -1, -1):
        if len(dp[j]):
            dp[j+A[i]] |= dp[j]
            dp[j+A[i]].add(A[i])

ans = 0
for i in range(N):
    for k, s in dp.items():
        # A[i]減らしたらK未満になる状況で、一度でもA[i]が使われていれば必要
        if k >= K and k-A[i] < K and A[i] in s:
            break
    else:
        # 該当するどの集合でも、一度も使われていなければ不要
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

def check(omit):
    dp = list2d(N+1, 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 i-1 != omit and j-A[i-1] >= 0:
                dp[i][j] |= dp[i-1][j-A[i-1]]
    
    for j in range(max(0, K-A[omit]), K):
        if dp[N][j]:
            return True
    return False

ans = 0
for i in range(N):
    if not check(i):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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):
    if a[mid] >= k:
        return True
    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(ng)

Submission status: Time Limit Exceeded

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)

#rightの部分和の集合を予め求めておく
right_subset_sum = [None] * (n+1)
right_subset_sum[-1] = set([0])
for i in range(n)[::-1]:
    a_i = a[i]
    tmp_set = set([])
    if a_i <= k:
        tmp_set.add(a_i)
    for j in right_subset_sum[i+1]:
        if j + a_i <= k:
            tmp_set.add(j + a_i)
    right_subset_sum[i] = right_subset_sum[i+1] | tmp_set

ans = 0
left_subset_sum = set([0])

for i in range(n):
    a_i= a[i]
    li = sorted(list(right_subset_sum[i+1]))
    for num in left_subset_sum:
        left = k - a_i - num
        right = k - num
        if bisect.bisect_left(li, right) - bisect.bisect_left(li, left) > 0:
            break
    else:
        ans += 1
    #leftの集合にa_iを含めた部分和を追加する
    tmp_set = set([])
    if a_i <= k:
        tmp_set.add(a_i)
    for j in left_subset_sum:
        if j + a_i <= k:
            tmp_set.add(j + a_i)
    left_subset_sum = left_subset_sum | tmp_set
print(ans)

Submission status: Time Limit Exceeded

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:
    # 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)
    need = 0
    #print(DP)
    for p in range(max(0, k-A[mid]), k):
        if DP[p] == 1:
            need = 1
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2

print(le + 1)

Submission status: Time Limit Exceeded

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

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
        for i in range(n):
            if i == x:
                continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                dp[j] |= dp[j - a[i]]
        for j in range(max(0, k - a[x]), k):
            if dp[j]:
                return 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: Time Limit Exceeded

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
        for i in range(n):
            if i == x:
                continue
            for j in range(k - 1, a[i] - 1, -1):
                dp[j] |= dp[j - a[i]]
        for j in range(max(0, k - a[x]), k):
            if dp[j]:
                return 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: Time Limit Exceeded

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
        # print(A)
        DP = [False]*K
        DP[a[not j]] = True
        for i in range(1, N):
            if i == j:
                continue
            for k in range(K-a[i]-1, -1, -1):
                DP[k+a[i]] = DP[k] or DP[k+a[i]]
        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()

Submission status: Time Limit Exceeded

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
        # print(A)
        DP = [[False]*K for _ in range(N)]
        DP[0][a[0 if j != 0 else 1]] = True
        for i in range(1, N):
            for k in range(K):
                DP[i][k] = DP[i-1][k] or DP[i][k]
                if i != j and 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: Time Limit Exceeded

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

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):
                if DP[i-1][k] == True:
                    DP[i][k] = True
                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: Time Limit Exceeded

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)]
        if A[0] < K:
            DP[0][A[0]] = True
        for i in range(1, N-1):
            for k in range(K):
                if DP[i-1][k] == True:
                    DP[i][k] = True
                if k + A[i] < K:
                    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: Time Limit Exceeded

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

def ok(x):
    dp = [[0] * k for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(k):
            dp[i + 1][j] += dp[i][j]
            if i != x and j + a[i] < k:
                dp[i + 1][j + a[i]] += dp[i][j]

    return any(dp[n][i] > 0 for i in range(max(0, k - a[x]), k))


lo = -1
hi = n
while abs(hi - lo) > 1:
    mi = (hi + lo) // 2
    if ok(mi):
        hi = mi
    else:
        lo = mi

print(hi)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = [0] * K
    dp[0] = 1
    for i in range(N) :
        if i == n : continue
        for j in range(K-a[i]-1, -1, -1) :
            if not dp[j] :
                continue
            if K - a[n] <= j + a[i] :
                return True
            dp[j+a[i]] = 1
    return False

l, r = -1, N
while r - l > 1 :
    m = (l+r)//2
    if judge(m) :
        r = m
    else  :
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = [0] * K
    dp[0] = 1
    for i in range(N) :
        if i == n : continue
        dp_ = dp[::]
        for j in range(K) :
            if not dp[j] :
                continue
            if j + a[i] >= K :
                break
            if K - a[n] <= j + a[i] :
                return True
            dp_[j+a[i]] = 1
        dp = dp_
    return False

l, r = -1, N
while r - l > 1 :
    m = (l+r)//2
    if judge(m) :
        r = m
    else  :
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = set([0])
    for i in range(N) :
        if i == n : continue
        dp_ = set()
        for j in dp :
            j = j + a[i]
            if K-a[n] <= j < K :
                return True
            if j >= K : break
            dp_.add(j)
        dp = dp | dp_
    return False

l, r = -1, N
while r - l > 1 :
    m = (l+r)//2
    if judge(m) :
        r = m
    else  :
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = set([0])
    for i in range(N) :
        if i == n : continue
        dp_ = set()
        for j in dp :
            j = j + a[i]
            if K-a[n] <= j < K :
                return True
            if j < K :
                dp_.add(j)
        dp = dp | dp_
    return False

l, r = -1, N
while r - l > 1 :
    m = (l+r)//2
    if judge(m) :
        r = m
    else  :
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = set([0])
    for i in range(N) :
        if i == n : continue
        dp_ = set()
        for j in dp :
            if K-a[n] <= j+a[i] < K :
                return True
            dp_.add(j+a[i])
        dp = dp | dp_
    return False

l, r = -1, N
while r - l > 1 :
    m = (l+r)//2
    if judge(m) :
        r = m
    else :
        l = m
print(r)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
b = a[::]
for i in range(N-1, 0, -1) :
    b[i-1] += b[i]

ret = [0] * N

def rec(n, s) :
    if s >= K :
        return True
        
    if n == N or s + b[n] < K :
        return False
    flg = rec(n+1, s+a[n])
    if flg :
        ret[n] = 1
    rec(n+1, s)
    return flg
    
rec(0, 0)
print(N - sum(ret))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)

N, K = map(int, input().split())
a = [int(i) for i in input().split()]

a.sort(reverse=True)

ret = [0] * N

def rec(n, s) :
    if s >= K :
        return True
        
    if n == N :
        return False
    flg = rec(n+1, s+a[n])
    if flg :
        ret[n] = 1
    rec(n+1, s)
    return flg
    
rec(0, 0)
print(N - sum(ret))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
MAX_INT = int(10e10)

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards += [MAX_INT]
#print(cards)
memo = [None]*5010
dp = [[0]*K for i in range(N+2)]
left = -1
right = N
while right - left > 1:
  middle = (left+right)//2
  if cards[middle] >= K:
    right = middle
  elif memo[cards[middle]] == True:
    right = middle
  elif memo[cards[middle]] == False:
    left = middle
  else:
    #print(left,right,middle,cards[middle])
    for i in range(N+1):
      for j in range(K):
        if i == middle:
          dp[i+1][j] = dp[i][j]
        else:
          if cards[i] <= j:
            dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
          else:
            dp[i+1][j] = dp[i][j]
    #print(dp)
    if dp[N][K-1] + cards[middle] >= K:
      right = middle
      memo[cards[middle]] = True
      #print(True)
    else:
      left = middle
      memo[cards[middle]] = False
      #print(False)
print(right)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
MAX_INT = int(10e10)

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards += [MAX_INT]
#print(cards)
dp = [[0]*K for i in range(N+2)]
left = -1
right = N
while right - left > 1:
  middle = (left+right)//2
  #print(left,right,middle,cards[middle])
  if cards[middle] >= K:
    right = middle
  else:
    for i in range(N+1):
      for j in range(K):
        if i == middle:
          dp[i+1][j] = dp[i][j]
        else:
          if cards[i] <= j:
            dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
          else:
            dp[i+1][j] = dp[i][j]
    #print(dp)
    if dp[N][K-1] + cards[middle] >= K:
      right = middle
      #print(True)
    else:
      left = middle
      #print(False)
print(right)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
MAX_INT = int(10e10)

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards += [MAX_INT]
#print(cards)
dp = [[0]*K for i in range(N+2)]
left = -1
right = N
while right - left > 1:
  middle = (left+right)//2
  #print(left,right,middle,cards[middle])
  for i in range(N+1):
    for j in range(K):
      if i == middle:
        dp[i+1][j] = dp[i][j]
      else:
        if cards[i] <= j:
          dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
        else:
          dp[i+1][j] = dp[i][j]
  #print(dp)
  if dp[N][K-1] + cards[middle] >= K:
    right = middle
    #print(True)
  else:
    left = middle
    #print(False)
print(right)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
MAX_INT = int(10e10)

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards += [MAX_INT]
#print(cards)
left = -1
right = N
while right - left > 1:
  middle = (left+right)//2
  #print(left,right,middle,cards[middle])
  dp = [[0]*K for i in range(N+2)]
  for i in range(N+1):
    for j in range(K):
      if i == middle:
        dp[i+1][j] = dp[i][j]
      else:
        if cards[i] <= j:
          dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
        else:
          dp[i+1][j] = dp[i][j]
  if dp[N][K-1] + cards[middle] >= K:
    right = middle
    #print(True)
  else:
    left = middle
    #print(False)
print(right)

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

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: 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 = [0]*k
    dp[0] = 1
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(k-ai)[::-1]:
            if dp[j]:
                if k_ <= j+ai:
                    r = m
                    break
                dp[j+ai] = 1
        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
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):
        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