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:
import sys
input = sys.stdin.readline
import threading

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

    dp1 = [0 for _ in range(N*K)]
    dp1[0] = 1
    for n in range(N-1):
        for k in range(K):
            if k < A[n]:
                dp1[(n+1)*K+k] = dp1[n*K+k]
            else:
                dp1[(n+1)*K+k] = dp1[n*K+k] | dp1[n*K+k-A[n]]

    dp2 = [0 for _ in range(N*K)]
    dp2[(N-1)*K] = 1
    for n in reversed(range(1, N)):
        for k in range(K):
            if k < A[n]:
                dp2[(n-1)*K+k] = dp2[n*K+k]
            else:
                dp2[(n-1)*K+k] = dp2[n*K+k] | dp2[n*K+k-A[n]]

    ans = 0
    for n, a in enumerate(A):
        if K-a <= 0: continue
        need = False
        k2 = K-1
        for k1 in range(K):
            if not dp1[n*K+k1]: continue
            while not dp2[n*K+k2] or k1+k2 >= K:
                k2 -= 1
            if k1+k2 < K-a:
                continue
            else:
                need = True
                break
        if not need: ans += 1
    print(ans)

if __name__ == "__main__":
    threading.stack_size(256 * 100000)
    thread = threading.Thread(target=main)
    thread.start()
    thread.join()

Submission status: Time Limit Exceeded

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

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

    dp1 = [0 for _ in range(N*K)]
    dp1[0] = 1
    for n in range(N-1):
        for k in range(K):
            if k < A[n]:
                dp1[(n+1)*K+k] = dp1[n*K+k]
            else:
                dp1[(n+1)*K+k] = dp1[n*K+k] | dp1[n*K+k-A[n]]

    dp2 = [0 for _ in range(N*K)]
    dp2[(N-1)*K] = 1
    for n in reversed(range(1, N)):
        for k in range(K):
            if k < A[n]:
                dp2[(n-1)*K+k] = dp2[n*K+k]
            else:
                dp2[(n-1)*K+k] = dp2[n*K+k] | dp2[n*K+k-A[n]]

    ans = 0
    for n, a in enumerate(A):
        if K-a <= 0: continue
        need = False
        k2 = K-1
        for k1 in range(K):
            if not dp1[n*K+k1]: continue
            while not dp2[n*K+k2] or k1+k2 >= K:
                k2 -= 1
            if k1+k2 < K-a:
                continue
            else:
                need = True
                break
        if not need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

    dp1 = [[0]*K for _ in range(N)]
    dp1[0][0] = 1
    for n in range(N-1):
        for k in range(K):
            if k < A[n]:
                dp1[n+1][k] = dp1[n][k]
            else:
                dp1[n+1][k] = dp1[n][k] | dp1[n][k-A[n]]

    dp2 = [[0]*K for _ in range(N)]
    dp2[N-1][0] = 1
    for n in reversed(range(1, N)):
        for k in range(K):
            if k < A[n]:
                dp2[n-1][k] = dp2[n][k]
            else:
                dp2[n-1][k] = dp2[n][k] | dp2[n][k-A[n]]

    ans = 0
    for n, a in enumerate(A):
        b = K - a
        if b <= 0: continue
        need = False
        k2 = K-1
        for k1 in range(K):
            if not dp1[n][k1]: continue
            while not dp2[n][k2] or k1+k2 >= K:
                k2 -= 1
            if k1+k2 < b:
                continue
            else:
                need = True
                break
        if not need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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

    dp1 = [set() for _ in range(N)]
    dp1[0].add(0)
    for n in range(N-1):
        for pm in dp1[n]:
            dp1[n+1].add(pm)
            if pm + A[n] < K:
                dp1[n+1].add(pm+A[n])

    dp2 = [set() for _ in range(N)]
    dp2[N-1].add(0)
    for n in reversed(range(1, N)):
        for pm in dp2[n]:
            dp2[n-1].add(pm)
            if pm+A[n] < K:
                dp2[n-1].add(pm+A[n])

    ans = 0
    for n, a in enumerate(A):
        b = K - a
        if b <= 0: continue
        need = False
        B1 = sorted(dp1[n])
        B2 = sorted(dp2[n], reverse=True)
        i2 = 0
        for b1 in B1:
            while B2[i2] + b1 >= K:
                i2 += 1
                if i2 == len(B2): break
            if i2 == len(B2): break
            if b1+B2[i2] < b:
                continue
            else:
                need = True
                break
        if not need: ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

dp1 = [[0 for _ in range(K)] for _ in range(N)]
dp1[0][0] = 1
for n in range(N-1):
    for k in range(K):
        if k < A[n]:
            dp1[n+1][k] = dp1[n][k]
        else:
            dp1[n+1][k] = dp1[n][k] | dp1[n][k-A[n]]

dp2 = [[0 for _ in range(K)] for _ in range(N)]
dp2[N-1][0] = 1
for n in reversed(range(1, N)):
    for k in range(K):
        if k < A[n]:
            dp2[n-1][k] = dp2[n][k]
        else:
            dp2[n-1][k] = dp2[n][k] | dp2[n][k-A[n]]

ans = 0
for n, a in enumerate(A):
    b = K - a
    if b <= 0: continue
    need = False
    k2 = K-1
    for k1 in range(K):
        if not dp1[n][k1]: continue
        while not dp2[n][k2] or k1+k2 >= K:
            k2 -= 1
        if k1+k2 < b:
            continue
        else:
            need = True
            break
    if not need: ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def examD():
    N, K = LI()
    A = LI(); A.sort()
    cur = int(0)
    """ 部分点
        for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if K-A[i]>=0:
            #Kがちっちゃい時注意
            if sum(dp[-1][K - A[i]:K]) == 0:
                cur += 1
        else:
            if sum(dp[-1][:K]) == 0:
                cur += 1
    print(cur)
    """
    cur = int(0)
    ilower = 0; iupper = N-1; ic = (ilower+iupper)//2
    while(True):
        a = A[0:ic] + A[ic+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if iupper - ilower >= 2:
            if sum(dp[-1][max(0, K - A[ic]):K]) == 0:
                ilower = ic
                ic = (ic + iupper) // 2
            else:
                iupper = ic
                ic = (ic + ilower) // 2
        else:
            if sum(dp[-1][max(0, K - A[ic]):K])==0:
                ic = iupper
                a = A[0:ic] + A[ic + 1:]
                dp = [[0] * (K + 1) for _ in range(N)]
                dp[0][0] = 1
                for j in range(N - 1):
                    for k in range(K + 1):
                        dp[j + 1][k] = max(dp[j][k], dp[j + 1][k])
                        if k - a[j] >= 0:
                            dp[j + 1][k] = max(dp[j + 1][k], dp[j][k - a[j]])
                if sum(dp[-1][max(0, K - A[ic]):K]) == 0:
                    cur = iupper
                else:
                    cur = ilower
            else:
                ic = ilower
                a = A[0:ic] + A[ic + 1:]
                dp = [[0] * (K + 1) for _ in range(N)]
                dp[0][0] = 1
                for j in range(N - 1):
                    for k in range(K + 1):
                        dp[j + 1][k] = max(dp[j][k], dp[j + 1][k])
                        if k - a[j] >= 0:
                            dp[j + 1][k] = max(dp[j + 1][k], dp[j][k - a[j]])
                if sum(dp[-1][max(0, K - A[ic]):K]) == 0:
                    cur = ilower
                else:
                    cur = -1
            break
#    print(cur)
    if cur==-1:
        ans = 0
    else:
        ans = bisect.bisect(A,A[cur])
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Time Limit Exceeded

Solution code:
def examD():
    N, K = LI()
    A = LI()
    dp = [[0]*(N+1) for _ in range(K+1)]
    cur = int(0)
    for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if K-A[i]>=0:
            #Kがちっちゃい時注意
            if sum(dp[-1][K - A[i]:K]) == 0:
                cur += 1
        else:
            if sum(dp[-1][:K]) == 0:
                cur += 1
    print(cur)



import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def check(m):
        DP = [False]*(k+1)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            for j in reversed(range(k+1-a[i])):
                DP[a[i]+j] = DP[a[i]+j] or DP[j]
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()

Submission status: Time Limit Exceeded

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    DP1 = [[False]*(k+1)]
    DP1[0][0] = True
    DP2 = [[False]*(k+1)]
    DP2[0][0] = True
    b = a[::-1]

    for i in range(n):
        DP1.append(DP1[i][:])
        DP2.append(DP2[i][:])
        for j in range(k+1):
            if DP1[i][j] and a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
            if DP2[i][j] and b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

    for i in range(n+1):
        q = [0]
        for j in range(k+1):
            q.append(q[-1]+int(DP2[i][j]))
        DP2[i] = q

    ans = 0
    for i in range(n):
        use = False
        for j in range(k+1):
            if not DP1[i][j]:
                continue
            left = max(0, k-a[i]-j)
            right = k-j
            if DP2[n-i-1][right] - DP2[n-i-1][left]:
                use = True
                break
        if not use:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    a = [i for i in a if i <k]
    n = len(a)

    DP1 = [[False]*(k+1)]
    DP1[0][0] = True
    DP2 = [[False]*(k+1)]
    DP2[0][0] = True
    b = a[::-1]

    for i in range(n):
        DP1.append(DP1[i][:])
        DP2.append(DP2[i][:])
        for j in range(k+1):
            if DP1[i][j] and a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
            if DP2[i][j] and b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

    for i in range(n+1):
        q = [0]
        for j in range(k+1):
            q.append(q[-1]+int(DP2[i][j]))
        DP2[i] = q

    ans = 0
    for i in range(n):
        use = False
        for j in range(k+1):
            if not DP1[i][j]:
                continue
            left = max(0, k-a[i]-j)
            right = k-j
            if DP2[n-i-1][right] - DP2[n-i-1][left]:
                use = True
                break
        if not use:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    DP1.append(DP1[i][:])
    DP2.append(DP2[i][:])
    for j in range(k+1):
        if DP1[i][j] and a[i]+j <= k:
            DP1[i+1][a[i]+j] = True
        if DP2[i][j] and b[i]+j <= k:
            DP2[i+1][b[i]+j] = True

for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    DP2[i] = q

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if DP2[n-i-1][right] - DP2[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = [i for i in a if i <k]
n = len(a)

DP1 = np.full((n+1, k+1), False)
DP1[0][0] = True
DP2 = np.full((n+1, k+1), False)
DP2[0][0] = True

for i in range(n):
    DP1[i+1] = DP1[i]
    DP1[i+1][a[i]:] = np.logical_or(DP1[i+1][a[i]:], DP1[i][:k-a[i]+1])
    DP2[i+1] = DP2[i]
    DP2[i+1][a[n-1-i]:] = np.logical_or(DP2[i+1][a[n-1-i]:], DP2[i][:k-a[n-1-i]+1])

hoge = []
for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    hoge.append(q)

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if hoge[n-i-1][right] - hoge[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1) for i in range(n+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1) for i in range(n+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    for j in range(k+1):
        if DP1[i][j]:
            DP1[i+1][j] = True
            if a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
        if DP2[i][j]:
            DP2[i+1][j] = True
            if b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

for i in range(n+1):
    q = [0]
    for j in range(k+1):
        q.append(q[-1]+int(DP2[i][j]))
    DP2[i] = q

ans = 0
for i in range(n):
    use = False
    for j in range(k+1):
        if not DP1[i][j]:
            continue
        left = max(0, k-a[i]-j)
        right = k-j
        if DP2[n-i-1][right] - DP2[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1) for i in range(n+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1) for i in range(n+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    for j in range(k+1):
        if DP1[i][j]:
            DP1[i+1][j] = True
            if a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
        if DP2[i][j]:
            DP2[i+1][j] = True
            if b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

from itertools import accumulate
for i in range(n+1):
    DP1[i] = [j for j in range(k+1) if DP1[i][j]]
    DP2[i] = [0] + list(accumulate(DP2[i]))

ans = 0
for i in range(n):
    use = False
    for j in DP1[i]:
        left = max(0, k-a[i]-j)
        right = k-j
        if DP2[n-i-1][right] - DP2[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1) for i in range(n+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1) for i in range(n+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    for j in range(k+1):
        if DP1[i][j]:
            DP1[i+1][j] = True
            if a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
        if DP2[i][j]:
            DP2[i+1][j] = True
            if b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

for i in range(n+1):
    DP1[i] = [j for j in range(k+1) if DP1[i][j]]
    DP2[i] = [j for j in range(k+1) if DP2[i][j]]

ans = 0
for i in range(n):
    use = False
    for j in DP1[i]:
        left = max(0, k-a[i]-j)
        right = k-j
        l = bisect_left(DP2[n-i-1], left)
        r = bisect_left(DP2[n-i-1], right)
        if r-l:
            use = True
            break
    if not use:
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bi

N,K=map(int,input().split())
a=[0];a.extend(list(map(int,input().split())));a.append(0)
# K以上の整数が書かれたカードは，不必要ではない。
sL=[{0} for i in range(N+1)] # カード1~iから作れる和(<=K-1)
sR=[{0} for i in range(N+2)];sR[0]=None # カードi~Nから作れる和(<=K-1)

for i in range(1,N+1):
    sL[i].update(sL[i-1]|{x+a[i] for x in sL[i-1] if x+a[i]<=K-1})
for i in range(N,0,-1):
    sR[i].update(sR[i+1]|{x+a[i] for x in sR[i+1] if x+a[i]<=K-1})

ans=0
for i in range(1,N+1):
    if a[i]>=K:
        continue
    l=sorted([x+y for x in sL[i-1] for y in sR[i+1]])
    # print(a[i],l,sep=' ')
    if bi.bisect_left(l,K-a[i])==bi.bisect_right(l,K-1):
        # print(a[i]) #DB
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bi

N,K=map(int,input().split())
a=[0];a.extend(list(map(int,input().split())));a.append(0)
# K以上の整数が書かれたカードは，不必要ではない。
# print(a) #DB
sL=[{0} for i in range(N+1)] # カード1~iから作れる和(<=K-1)
sR=[{0} for i in range(N+2)];sR[0]=None # カードi~Nから作れる和(<=K-1)

for i in range(1,N+1):
    sL[i].update(sL[i-1]|{x+a[i] for x in sL[i-1] if x+a[i]<=K-1})
for i in range(N,0,-1):
    sR[i].update(sR[i+1]|{x+a[i] for x in sR[i+1] if x+a[i]<=K-1})
# print(sL) #DB
# print(sR) #DB

ans=0
# 1<=i<=Nを固定する。
# sL[i-1]の各要素xにつき，x+y+1<=K<=x+y+a[i]⇔K-(x+1)<=y<=K-(x+a[i])なる要素がsR[i+1](リスト化し，昇順にソート）に含まれていれば，a[i]は不必要ではない。
# これは，bi_bisect.left(list,K-(x+a[i]))<bi_bisect.right(list,K-(x+1))か否かで判定できる。
for i in range(1,N+1):
    if a[i]>=K:
        continue
    lR=sorted(list(sR[i+1]))
    f=True
    for x in sL[i-1]:
        # print(f'ai={a[i]},x={x},K-(x+ai)={K-(x+a[i])},K-(x+1)={K-(x+1)},lR={lR},bi_l={bi.bisect_left(lR,K-(x+a[i]))},bi_r={bi.bisect_right(lR,K-(x+1))}')
        if bi.bisect_left(lR,K-(x+a[i]))<bi.bisect_right(lR,K-(x+1)):
            f=False
            break
    if f:
        # print(a[i]) #DB
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect as bi

N,K=map(int,input().split())
a=[0];a.extend(list(map(int,input().split())));a.append(0)
# K以上の整数が書かれたカードは，不必要ではない。
# print(a) #DB
sL=[{0} for i in range(N+1)] # カード1~iから作れる和(<=K-1)
sR=[{0} for i in range(N+2)];sR[0]=None # カードi~Nから作れる和(<=K-1)

for i in range(1,N+1):
    sL[i].update(sL[i-1]|{x+a[i] for x in sL[i-1] if x+a[i]<=K-1})
for i in range(N,0,-1):
    sR[i].update(sR[i+1]|{x+a[i] for x in sR[i+1] if x+a[i]<=K-1})
# print(sL) #DB
# print(sR) #DB

ans=0
# 1<=i<=Nを固定する。
# sL[i-1]の各要素xにつき，x+y+1<=K<=x+y+a[i]⇔K-(x+1)<=y<=K-(x+a[i])なる要素がsR[i+1](リスト化し，昇順にソート）に含まれていれば，a[i]は不必要ではない。
# これは，bi_bisect.left(list,K-(x+a[i]))<bi_bisect.right(list,K-(x+1))か否かで判定できる。
for i in range(1,N+1):
    lR=sorted(list(sR[i+1]))
    f=True
    for x in sL[i-1]:
        # print(f'ai={a[i]},x={x},K-(x+ai)={K-(x+a[i])},K-(x+1)={K-(x+1)},lR={lR},bi_l={bi.bisect_left(lR,K-(x+a[i]))},bi_r={bi.bisect_right(lR,K-(x+1))}')
        if bi.bisect_left(lR,K-(x+a[i]))<bi.bisect_right(lR,K-(x+1)):
            f=False
            break
    if f:
        # print(a[i]) #DB
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=[0];a.extend(list(map(int,input().split())));a.append(0)
# K以上の整数が書かれたカードは，不必要ではない。
# print(a) #DB
L=[{0} for i in range(N+1)] # カード1~iから作れる和(<=K-1)
R=[{0} for i in range(N+2)];R[0]=None # カードi~Nから作れる和(<=K-1)

for i in range(1,N+1):
    L[i].update(L[i-1]|{x+a[i] for x in L[i-1] if x+a[i]<=K-1})
for i in range(N,0,-1):
    R[i].update(R[i+1]|{x+a[i] for x in R[i+1] if x+a[i]<=K-1})
# print(L) #DB
# print(R) #DB
S=[set() for i in range(N+1)];S[0]=None
for i in range(1,N+1):
    S[i]={x+y for x in L[i-1] for y in R[i+1] if x+y<=K-1}
# print(S) #DB

ans=0
for i in range(1,N+1):
    # print(i,{x for x in range(K-a[i],K)} & S[i]) #DB
    if not {x for x in range(K-a[i],K)} & S[i]:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in range(N):
    s={0}
    for j in range(N):
        if j!=i:
            t=set()
            for x in range(K-a[j]):
                if x in s:
                    t.add(x+a[j])
            s.update(t)
    f=True
    for k in range(K-a[i],K):
        if k in s:
            f=False
            break
    if f:
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,discrete=True,left=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return h if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    def check(x): # xが必要かどうかを判定する
        dp=[0]*k # k未満が実現できるかだけを判定
        dp[0]=1
        for i in range(n):
            if(i==x): continue
            newdp=dp[:] # i番目を使わない場合
            a=A[i]
            for j in range(k):
                if(j+a<k):
                    newdp[j+a]=max(dp[j+a],dp[j])
            dp=newdp
        return any(dp[i] for i in range(max(0,k-A[x]),k))
    print(bisection(0,n-1,check,left=False))
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def bisection(l,r,f,discrete=True,left=True):
    eps=1 if discrete else 10**-12
    if((not left)^f(r)): return r if left else r+1
    elif(left^f(l)): return l-1 if left else l
    while(r-l>eps):
        h=(l+r)//2 if discrete else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return h if not discrete else l if left else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    def check(x): # xが必要かどうかを判定する
        dp=[0]*k # k未満が実現できるかだけを判定
        dp[0]=1
        for i in range(n):
            if(i==x): continue
            newdp=dp[:] # i番目を使わない場合
            a=A[i]
            for j in range(k):
                if(j+a<k):
                    newdp[j+a]=max(dp[j+a],dp[j])
            dp=newdp
        return any(dp[i] for i in range(max(0,k-A[x]),k))
    ans=n
    for i in range(n):
        ans-=check(i)
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, K = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    n = -1
    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, ai in enumerate(a):
        for j in range(K+1):
            if j>=ai:
                dp1[i+1][j] = max(dp1[i][j], dp1[i][j-ai])
            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]
    for i in range(N+1):
        for j in range(K):
            dp2[i][j+1] = dp2[i][j]+dp2[i][j+1]
    ans = 0
    for i, ai in enumerate(a):
        need = False
        for j in range(K):
            if dp1[i][j]:
                if K-j-ai>0:
                    l = K-j-ai-1
                    if dp2[i+1][K-j-1]-dp2[i+1][l]:
                        need = True
                else:
                    if dp2[i+1][K-j]:
                        need = True
        if not need:
            ans+=1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
n = -1
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]
for i in range(N+1):
    for j in range(K):
        dp2[i][j+1] = dp2[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 dp2[i+1][K-j-1]-dp2[i+1][l]:
                    need = True
            else:
                if dp2[i+1][K-j]:
                    need = True
    if not need:
        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

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 = [0] * K
    dp[0] = 1
    for i in range(1, N+1):
        for j in range(K-1, -1, -1):
            if i-1 != omit and j-A[i-1] >= 0:
                dp[j] |= dp[j-A[i-1]]
    # 今回の値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: 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(list)
dp[0].append(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]].append(A[i])

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

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)