Problem:


Score : 600 points

Problem Statement

AtCoDeer the deer has N cards with positive integers written on them. The number on the i-th card (1≤i≤N) is a_i.
Because he loves big numbers, he calls a subset of the cards good when the sum of the numbers written on the cards in the subset, is K or greater.

Then, for each card i, he judges whether it is unnecessary or not, as follows:

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

Otherwise, card i is NOT unnecessary.

Find the number of the unnecessary cards. Here, he judges each card independently, and he does not throw away cards that turn out to be unnecessary.

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

1≤a_i≤10^9 (1≤i≤N)

Partial Score

300 points will be awarded for passing the test set satisfying N,K≤400.

Input

The input is given from Standard Input in the following format:

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

There are two good sets: {2,3} and {1,2,3}.

Card 1 is only contained in {1,2,3}, and this set without card 1, {2,3}, is also good. Thus, card 1 is unnecessary.

For card 2, a good set {2,3} without card 2, {3}, is not good. Thus, card 2 is NOT unnecessary.

Neither is card 3 for a similar reason, hence the answer is 1.

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

In this case, there is no good set. Therefore, all the cards are unnecessary.

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
a=[None]
a.extend(list(map(int,input().split())))
# K以上の整数が書かれたカードは，不必要ではない。
# print(a) #DB
# dp[i][j]=i枚目のカードを使用して合計がjになったことがあるか(1<=i<=N,0<=j<=2K-2)
dp=[[False for j in range(2*K-1)] for i in range(N+1)];dp[0]=None

for i2 in range(1,N+1):
    t=a[i2]
    dp[i2][t]=True
    for i1 in range(1,i2):
        for j in range(2*K-2,0,-1):
            if dp[i1][j] and j+t<=2*K-2:
                dp[i1][j+t]=dp[i2][j+t]=True

# print(dp) #DB
ans=0
for i in range(1,N+1):
    t=a[i]
    if t>=K:
        continue
    else:
        f=True
        for j in range(K,K+t):
            if dp[i][j]:
                f=False
                break
        if f:
            # print(t,f)
            ans+=1
print(ans)

Submission status: Runtime Error

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

dp = [[10 ** 11 for _ in range(2*K-1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0] = 10 ** 10
for i in range(N):
    for j in range(K):
        if dp[i][j] < 10 ** 10 + 1:
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            if j + a[i] <= 2*(K-1):
                dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]], dp[i][j], a[i])

dp_last = dp[-1][K:]
ans = 0
i = 0
prev = 0
for i in range(N):
    if a[i] == prev:
        i += 1
        ans += 1
        continue
    else:
        prev = a[i]
    ok = 0
    for j in range(a[i]):
        if dp_last[j] <= a[i]:
            ok = 1
            break
    if ok:
        break
    else:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    num = [0] * K
    c = 0
    ok = float('inf')
    for i, ai in enumerate(a):
        if ai >= K:
            a = a[:i]
        else:
            num[ai] += 1
            c += ai
        if c >= K:
            ok = i - num[ai] + 1
    if not a:
        print(0)
        exit()
    n = len(a)
    if ok > n:
        ok = n
    ng = -1
    mid = (ok + ng) // 2
    while ok - ng > 1:
        flg = 0
        dp = [[0 for _ in range(K)] for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(n):
            for j in range(K):
                if dp[i][j] == 1:
                    if i != mid:
                        if j + a[i] <= K-1:
                            dp[i+1][j+a[i]] = 1
                    dp[i+1][j] = 1
        for i in range(-1, -a[mid]-1, -1):
            if dp[-1][i] == 1:
                flg = 1
                break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok + ng) // 2
    if ng == -1:
        print(0)
        exit()
    print(sum(num[:a[ng]+1]))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
for i in range(N):
    if a[i]<=K:
        n = i
    else:
        break
if n == 0:
    print(0)
    exit()
N = n+1
a = a[:N]
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[0][0] = 1
dp2[-1][0] = 1#i~Nまで使う
for i in range(N):
    for j in range(K+1):
        if j>=a[i]:
            dp1[i+1][j] = max(dp1[i][j], dp1[i][j-a[i]])
        else:
            dp1[i+1][j] = dp1[i][j]
for i in range(N)[::-1]:
    for j in range(K+1):
        if j>=a[i]:
            dp2[i][j] = max(dp2[i+1][j], dp2[i+1][j-a[i]])
        else:
            dp2[i][j] = dp2[i+1][j]
S1 = [[0]*(K+1) for _ in range(N+1)]
S2 = [[0]*(K+1) for _ in range(N+1)]
for i in range(N+1):
    S1[i][0], S2[i][0] = dp1[i][0], dp2[i][0]
for i in range(N+1):
    for j in range(K):
        S1[i][j+1] = S1[i][j]+dp1[i][j+1]
        S2[i][j+1] = S2[i][j]+dp2[i][j+1]
ans = 0
for i in range(N):
    need = False
    for j in range(K):
        if dp1[i][j]:
            if K-j-a[i]>0:
                l = K-j-a[i]-1
                if S2[i+1][K-j-1]-S2[i+1][l]:
                    need = True
            else:
                if S2[i+1][K-j]:
                    need = True
    if not need:
        ans+=1
print(ans)

Submission status: Runtime Error

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

raise Exception

# 和が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: Runtime Error

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) for _ in range(n)]
        dp[0][0] = True
        for i in range(n):
            dpi = dp[i]
            dpi1 = dp[i - 1]
            ai = a[i]
            for j in range(k):
                if i == x:
                    dpi[j] |= dpi1[j]
                else:
                    if j >= a[i]:
                        dpi[j] |= dpi1[j - ai]
                    dpi[j] |= dpi1[j]
            for j in range(k - a[x], k):
                if dpi[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: Runtime Error

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) for i in range(n)]
        dp[0][0] = True
        for i in range(n):
            dpi = dp[i]
            dpi1 = dp[i - 1]
            for j in range(k):
                if i == x:
                    dpi[j] |= dpi1[j]
                else:
                    if j >= a[i]:
                        dpi[j] |= dpi1[j - a[i]]
                    dpi[j] |= dpi1[j]
        for i in range(k - a[x], k):
            if dpi[i]:
                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: Runtime Error

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 - 1
    ng = -1
    def f(x):
        dp = [[False] * (k) for i in range(n)]
        dp[0][0] = True
        for i in range(n):
            dpi = dp[i]
            dpi1 = dp[i - 1]
            for j in range(k):
                if i == x:
                    dpi[j] |= dpi1[j]
                else:
                    if j >= a[i]:
                        dpi[j] |= dpi1[j - a[i]]
                    dpi[j] |= dpi1[j]
        for i in range(k - a[x], k):
            if dpi[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(ng + 1)
    return

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

Submission status: Runtime Error

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 - 1
    ng = 0
    def f(x):
        dp = [[False] * (k) for i in range(n)]
        dp[0][0] = True
        for i in range(n):
            dpi = dp[i]
            dpi1 = dp[i - 1]
            for j in range(k):
                if i == x:
                    dpi[j] |= dpi1[j]
                else:
                    if j >= a[i]:
                        dpi[j] |= dpi1[j - a[i]]
                    dpi[j] |= dpi1[j]
        for i in range(k - a[x], k):
            if dpi[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(ng + 1)
    return

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

Submission status: Runtime Error

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 - 1
    ng = 0
    def f(x):
        dp = [[False] * (k) for i in range(n)]
        dp[0][0] = True
        for i in range(n):
            for j in range(k):
                if i == x:
                    dp[i][j] |= dp[i - 1][j]
                else:
                    if j >= a[i]:
                        dp[i][j] |= dp[i - 1][j - a[i]]
                    dp[i][j] |= dp[i - 1][j]
        for i in range(k - a[x], k):
            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(ng + 1)
    return

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

Submission status: Runtime Error

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 - 1
    ng = 0
    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 - 1][j - a[i]]
                    dp[i][j] |= dp[i - 1][j]
        for i in range(k - a[x], k):
            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(ng + 1)
    return

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

Submission status: Runtime Error

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 = 0
    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 - 1][j - a[i]]
                    dp[i][j] |= dp[i - 1][j]
        for i in range(k - a[x], k):
            if dp[-1][i]:
                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: Runtime Error

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


def solve(N: int, K: int, a: "List[int]"):
    a.sort()
    count = 0
    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: Runtime Error

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


def solve(N: int, K: int, a: "List[int]"):
    a.sort()
    # print(a)
    count = 0
    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 + 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: Runtime Error

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


def solve(N: int, K: int, a: "List[int]"):
    a.sort()
    count = 0
    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)]
        for i in range(N-1):
            if A[i] < K:
                DP[i][A[i]] = True
            if i == 0:
                continue
            for k in range(K):
                DP[i][k] = DP[i-1][k] or DP[i][k]
                if 0 <= k - A[i] < K:
                    DP[i][k] = DP[i][k] or DP[i-1][k-A[i]]
        # print(*DP, sep="\n")
        # print("")
        if any(DP[N-2][K-a[j]:]):
            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: Runtime Error

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


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

    count = 0
    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)]
        for i in range(N-1):
            if A[i] < K:
                DP[i][A[i]] = True
            if i == 0:
                continue
            for k in range(K):
                DP[i][k] = DP[i-1][k] or DP[i][k]
                if 0 <= k - A[i] < K:
                    DP[i][k] = DP[i][k] or DP[i-1][k-A[i]]
        # print(*DP, sep="\n")
        # print("")
        if any(DP[N-2][K-a[j]:]):
            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: Runtime Error

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


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

    count = 0
    for j in range(N):
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [[False]*K for _ in range(N-1)]
        for i in range(N-1):
            if A[i] < K:
                DP[i][A[i]] = True
            if i == 0:
                continue
            for k in range(K):
                DP[i][k] = DP[i-1][k] or DP[i][k]
                if 0 <= k - A[i] < K:
                    DP[i][k] = DP[i][k] or DP[i-1][k-A[i]]
        # print(*DP, sep="\n")
        # print("")
        if any(DP[N-2][K-a[j]:]):
            count += 1
    print(N-count)

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

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

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 memo[cards[middle]] == True or cards[middle] >= K:
    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: Runtime Error

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

a.sort()

ret = [0] * N
def rec(i, s, m) :
    if s >= K :
        if s - m < K :
            return True
        return False
        
    if i == N :
        return False

    c1 = rec(i + 1, s + a[i], min(m, a[i]))
    c2 = rec(i + 1, s, m)
    if c1 :
        ret[i] = 1
        
    return (c1 or c2)
        
    
rec(0, 0, float('inf'))

print(N - sum(ret))

Submission status: Runtime Error

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

a.sort()

ret = [0] * N
def rec(i, s, m) :
    print(i, s, m)
    if s >= K :
        if s - m < K :
            return True
        return False
        
    if i == N :
        return False

    c1 = rec(i + 1, s + a[i], min(m, a[i]))
    c2 = rec(i + 1, s, m)
    if c1 :
        ret[i] = 1
        
    return (c1 or c2)
        
    
rec(0, 0, float('inf'))

print(N - sum(ret))