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:
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(N)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(N-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[N-1][K-a[num]:])

    left = 0
    right = N-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    def dp(num):
        dp = [[0]*(K) for _ in range(N)]
        dp[0][0] = 1
        b = a[:num]+a[num+1:] #N-1個
        for i in range(N-1):
            for j in range(K):
                if b[i]<=j:
                    dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
                else:
                    dp[i+1][j]=dp[i][j]
        return any(dp[N-1][K-a[num]:])

    left = 0
    right = N-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    dp_left = [[False] * K for _ in range(N + 1)]
    dp_right = [[False] * K for _ in range(N + 1)]
    dp_left[0][0] = True
    dp_right[0][0] = True
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = True
                if j + a < K:
                    dp_left[i + 1][j + a] = True
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = True
                if j + a < K:
                    dp_right[i + 1][j + a] = True

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    dp_left = [[False] * K for _ in range(N + 1)]
    dp_right = [[False] * K for _ in range(N + 1)]
    dp_left[0][0] = True
    dp_right[0][0] = True
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = True
                if j + a < K:
                    dp_left[i + 1][j + a] = True
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = True
                if j + a < K:
                    dp_right[i + 1][j + a] = True

    ans = 0
    for i, a in enumerate(A):
        if a >= K:
            continue
        ok = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-i-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                ok = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-i-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[i][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if not ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    dp_left = [[False] * K for _ in range(N + 1)]
    dp_right = [[False] * K for _ in range(N + 1)]
    dp_left[0][0] = True
    dp_right[0][0] = True
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = True
                if j + a < K:
                    dp_left[i + 1][j + a] = True
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = True
                if j + a < K:
                    dp_right[i + 1][j + a] = True

    ans = 0
    for i, a in enumerate(A):
        if a >= K:
            continue
        L = []
        R = []
        for j in range(K):
            if dp_left[i][j]:
                L.append(j)
            if dp_right[N-i-1][j]:
                R.append(j)
        nl = len(L)
        nr = len(R)
        l = 0
        r = nr-1
        ok = 0
        while True:
            if K-a <=L[l] + R[r] < K:
                ok = 1
                break
            elif L[l] + R[r] >= K:
                r -= 1
                if r < 0:
                    break
            else:
                l += 1
                if l >= nl:
                    break
        if not ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = dp[i-1]|(dp[i-1]<<ls[i-1])
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
def solve(i):
  dp = np.zeros(k, dtype=bool)
  dp[0] = True
  for j in range(n):
    if j == i:
      continue
    a = A[j]
    dp[a:] |= dp.copy()[:-a]
  return np.any(dp[-A[i]:])

ans = 0
for i in range(n):
  if not solve(i):
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
 
    ans = N
    for i in range(N):
        if A[i] >= K:
            #print(str(A[i]) +"は必要")
            ans-=1
            continue
 
        B = A[:]
        B.pop(i) # Aの中で今選ばれているもの以外のlist
        #print("↓B")
        #print(B)
 
        # DP[i][k] i枚目のカードまででkが作れるか
        DP = [[0] * (K+1) for x in range(N)]
        DP[0][0] = 0
 
        for j in range(N-1):
            for k in range(K+1):
                if DP[j][k] == 1 and k + B[j] <= K:
                    DP[j+1][k+B[j]] = 1
 
                if B[j] == k:
                    DP[j+1][k] = 1
 
                DP[j+1][k] |= DP[j][k]
 
        #print(DP[N-1])
        #DP[N-1] をみて、K - A[i] =< n < K なるnが1ならOK
        for j in range(K-A[i],K):
            if DP[N-1][j] == 1:
                ans-=1
                #print(str(A[i]) +"は必要")
                break
 
    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()))

    ans = N
    for i in range(N):
        if A[i] >= K:
            #print(str(A[i]) +"は必要")
            ans-=1
            continue

        B = A[:]
        B.pop(i) # Aの中で今選ばれているもの以外のlist
        #print("↓B")
        #print(B)

        # DP[i][k] i枚目のカードまででkが作れるか
        DP = [[0] * (K+1) for x in range(N)]
        DP[0][0] = 0

        for j in range(N-1):
            for k in range(K+1):
                if DP[j][k] == 1 and k + B[j] <= K:
                    DP[j+1][k+B[j]] = 1

                if B[j] == k:
                    DP[j+1][k] = 1

                DP[j+1][k] |= DP[j][k]

        #print(DP[N-1])
        #DP[N-1] をみて、K - A[i] =< n < K なるnが1ならOK
        for j in range(K-A[i],K):
            if DP[N-1][j] == 1:
                ans-=1
                #print(str(A[i]) +"は必要")
                break

    print(ans)




if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    ans = 0
    for i in range(n):
        B = A[:]
        B.pop(i) # Aの中で今選ばれているもの以外のlist
        C = subset(B) #Bの部分集合それぞれの和のlist
        D = [x for x in C if x >= (k-A[i])] # Cのうち和が(k-Ai)以上のもの
        if len([x for x in D if x >= k]) == len(D): # Dがすべて20以上であればans+1
            ans+=1

    print(ans)


def subset(B):
    """
    input B=list
    output 部分集合のそれぞれの和のlist
    """
    subsets=[]
    for i in range(len(B) + 1):
        for j in combinations(B, i):
                subsets.append(j)

    return [sum(x) for x in subsets]


if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()

def check(d):#そいつが必要か
    global a,n,k
    dp=[0]*(k)#k-1まで
    if a[d]>=k:
        return True
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(filter(lambda a: a < K, map(int, input().split())))
    N = len(A)
    DP = [[0] * (2 * K) for _ in range(N+1)]
    DP[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K+a):
            DP[i+1][j] = (DP[i][j-a] if j >= a else 0) + DP[i][j]
    DP2 = [[0] * (2 * K) for _ in range(N+1)]
    for i, a in enumerate(A):
        for j in range(K+a):
            DP2[i][j] = DP[N][j] - (DP2[i][j-a] if j >= a else 0)
    print(N - sum(any(DP2[i][j] > 0 for j in range(K-a, K)) for i, a in enumerate(A)))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()

def check(d):#そいつが必要か
    global a,n,k
    dp=[0]*(k)#k-1まで
    if a[d]>=k:
        return True
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                flag = False
                for j in range(k-ta,k):
                    if dp[j]:
                        flag = True
                        break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n
while l!=r:
    i=(l+r)//2
    ta = a[i]
    if ta>=k:flag=True
    else:
        na = a[:i]+a[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(n-1):
            for m in range(k,0,-1):
                if m-na[j]>=0:
                    dp[m]=dp[m] or dp[m-na[j]]
        flag = False
        for j in range(k-ta,k):
            if dp[j]:
                flag = True
                break
    if flag:
        r=i
    else:
        l=i+1
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=0
r=n
while l!=r:
    i=(l+r)//2
    ta = a[i]
    na = a[:i]+a[i+1:]
    dp = [False for _ in range(k+1)]
    dp[0]=True
    for j in range(n-1):
        for m in range(k,0,-1):
            if m-na[j]>=0:
                dp[m]=dp[m] or dp[m-na[j]]
    flag = False
    if ta>=k:flag=True
    else:
        for j in range(k-ta,k):
            if dp[j]:
                flag = True
                break
    if flag:
        r=i
    else:
        l=i+1
print(l)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
nn = len(fa)
if sum(a)<k:
    print(n)
elif nn==0:
    print(0)
else:
    fa.reverse()
    res = nn
    for i in range(nn):
        flag = 0
        ta = fa[i]
        na = fa[:i]+fa[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(nn-1):
            for l in range(k,0,-1):
                if l-na[j]>=0:
                    dp[l]=dp[l] or dp[l-na[j]]
        for j in range(k-ta,k):
            if dp[j]:
                flag = 1
                break
        if flag == 0:
            res = i
            break
    print(nn-res)

Submission status: Time Limit Exceeded

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

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp0 = [0]*K
    dp0[0] = 1
    dp1 = [0]*K
    for i in range(N-1):
        for j in range(K):
            if i%2 == 0:
                if j < L[i]:
                    dp1[j] = dp0[j]
                    continue
                dp1[j] = dp0[j] | dp0[j-L[i]]
            else:
                if j < L[i]:
                    dp0[j] = dp1[j]
                    continue
                dp0[j] = dp1[j] | dp1[j-L[i]]
        
    res = False
    if N%2 == 0:
        for j in range(K-A[n], K):
            if dp1[j]:
                res = True
                break
    else:
        for j in range(K-A[n], K):
            if dp0[j]:
                res = True
                break
            
    return res

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

Submission status: Time Limit Exceeded

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

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(2)]
    dp[0][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[(i+1)%2][j] = dp[i%2][j]
                continue
            dp[(i+1)%2][j] = dp[i%2][j] | dp[i%2][j-L[i]]
        
    res = False
    for j in range(K-A[n], K):
        if dp[(N+1)%2][j]:
            res = True
            break
            
    return res

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

Submission status: Time Limit Exceeded

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

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(N)]
    for i in range(N):
        dp[i][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] | dp[i][j-L[i]]
                
    res = False
    for j in range(K-A[n], K):
        if dp[-1][j]:
            res = True
            break
            
    return res

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

Submission status: Time Limit Exceeded

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

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

# K-a <= x <= K-1

dp_L = [[False]*K for _ in range(N)]
dp_L[0][0] = True
for i, a in enumerate(A[:-1]):
    dp_L_next = dp_L[i+1]
    for j, d in enumerate(dp_L[i]):
        dp_L_next[j] = d
    if a>=K: continue
    for j, d in enumerate(dp_L[i][:-a]):
        dp_L_next[j+a] |= d

dp_R = [[False]*K for _ in range(N)]
dp_R[0][0] = True
for i, a in enumerate(A[:0:-1]):
    dp_R_next = dp_R[i+1]
    for j, d in enumerate(dp_R[i]):
        dp_R_next[j] = d
    if a>=K: continue
    for j, d in enumerate(dp_R[i][:-a]):
        dp_R_next[j+a] |= d

# for i, d in enumerate(dp_L):
#     print(i,d)
# 
# for i, d in enumerate(dp_R):
#     print(i, d)

ans = 0
for i, a in enumerate(A):
    dl = dp_L[i]
    dr = dp_R[-(i+1)]
    
    noneed = True
    ml = -K
    for j in range(K):
        fl = dl[j]
        fr = dr[K-1-j]
        if fl: ml = j
        if fr and j-ml<a:
            noneed = False
            break
    if noneed: ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
modmask = 2**K - 1

# K-a <= x <= K-1

dp_L = [1] * N
p = 1
for i, a in enumerate(A[:-1]):
    if a<K: p = (p|(p<<a)) & modmask
    dp_L[i+1] = p

dp_R = [1] * N
p = 1
for i, a in enumerate(reversed(A[1:])):
    if a<K : p = (p|(p<<a)) & modmask
    dp_R[i+1] = p
    
#for i, d in enumerate(dp_L):
#    print('{:2d} {:20b}'.format(i, d))

#for i, d in enumerate(dp_R):
#    print('{:2d} {:20b}'.format(i, d))

ans = 0
for i, a in enumerate(A):
    dl = dp_L[i]
    dr = dp_R[-(i+1)]
    #print(i, '{:20b} {:20b}'.format(dl, dr))
    Fl = []
    
    noneed = True
    ml = -K
    for j in range(K):
        #fl = dl&(1<<j)
        fl = dl&1
        dl>>=1
        fr = dr&(1<<(K-1-j))
        if fl: ml = j
        if fr and j-ml<a:
            #print(j, ml, K-1-j)
            noneed = False
            break
    #print('noneed:', noneed,'\n')
    if noneed: ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
modmask = 2**K - 1

# K-a <= x <= K-1

dp_L = [1] * N
for i, a in enumerate(A[:-1]):
    dp_L[i+1] = dp_L[i]
    if a>=K: continue
    dp_L[i+1] |= (dp_L[i]<<a)
    dp_L[i+1] &= modmask

dp_R = [1] * N
for i, a in enumerate(reversed(A[1:])):
    dp_R[i+1] = dp_R[i]
    if a>=K: continue
    dp_R[i+1] |= (dp_R[i]<<a)
    dp_R[i+1] &= modmask
    
#for i, d in enumerate(dp_L):
#    print('{:2d} {:20b}'.format(i, d))

#for i, d in enumerate(dp_R):
#    print('{:2d} {:20b}'.format(i, d))

ans = 0
for i, a in enumerate(A):
    dl = dp_L[i]
    dr = dp_R[-(i+1)]
    #print(i, '{:20b} {:20b}'.format(dl, dr))
    noneed = True
    ml = -K
    for j in range(K):
        fl = dl&(1<<j)
        fr = dr&(1<<(K-1-j))
        if fl: ml = j
        if fr and j-ml<a:
            #print(j, ml, K-1-j)
            noneed = False
            break
    #print('noneed:', noneed,'\n')
    if noneed: ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
modmask = 2**K - 1

# K-a <= x <= K-1

dp_L = [1] * N
for i, a in enumerate(A[:-1]):
    dp_L[i+1] = dp_L[i]
    if a>=K: continue
    dp_L[i+1] |= (dp_L[i]<<a)
    dp_L[i+1] &= modmask

dp_R = [1] * N
for i, a in enumerate(reversed(A[1:])):
    dp_R[i+1] = dp_R[i]
    if a>=K: continue
    dp_R[i+1] |= (dp_R[i]<<a)
    dp_R[i+1] &= modmask
    
#for i, d in enumerate(dp_L):
#    print('{:2d} {:20b}'.format(i, d))

#for i, d in enumerate(dp_R):
#    print('{:2d} {:20b}'.format(i, d))

ans = 0
for i, a in enumerate(A):
    dl = dp_L[i]
    dr = dp_R[-(i+1)]
    #print(i, '{:20b} {:20b}'.format(dl, dr))
    noneed = True
    ml = -K
    for j in range(K):
        fl = dl&(1<<j)
        fr = dr&(1<<(K-1-j))
        if fl: ml = j
        if fr and j-ml<a:
            #print(j, ml, K-1-j)
            noneed = False
            break
    #print('noneed:', noneed,'\n')
    if noneed: ans+=1

print(ans)

Submission status: Time Limit Exceeded

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

# K-a <= x <= K-1

dp_L = [1] * N
for i, a in enumerate(A[:-1]):
    dp_L[i+1] = dp_L[i]
    if a>=K: continue
    dp_L[i+1] |= (dp_L[i]<<a)
    dp_L[i+1] %= mod

dp_R = [1] * N
for i, a in enumerate(reversed(A[1:])):
    dp_R[i+1] = dp_R[i]
    if a>=K: continue
    dp_R[i+1] |= (dp_R[i]<<a)
    dp_R[i+1] %= mod
    
#for i, d in enumerate(dp_L):
#    print('{:2d} {:20b}'.format(i, d))

#for i, d in enumerate(dp_R):
#    print('{:2d} {:20b}'.format(i, d))

ans = 0
for i, a in enumerate(A):
    dl = dp_L[i]
    dr = dp_R[-(i+1)]
    #print(i, '{:20b} {:20b}'.format(dl, dr))
    noneed = True
    ml = -K
    for j in range(K):
        fl = dl&(1<<j)
        fr = dr&(1<<(K-1-j))
        if fl: ml = j
        if fr and j-ml<a:
            #print(j, ml, K-1-j)
            noneed = False
            break
    #print('noneed:', noneed,'\n')
    if noneed: 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,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    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 (l+r)/2 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()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    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,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    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 (l+r)/2 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(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])

        for j in range(max(0,k-A[i]),k):
            if((dp>>j)&1):
                return True
        return False

    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,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    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 (l+r)/2 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()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<=k が作れるか
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        for j in range(max(0,k-A[i]),k+1):
            if((dp>>j)&1):
                return True
        return False




    print(bisection(0,n-1,check,left=False))
resolve()

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):
        if K-a <= 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 >= K-a:
                need = True
                break
        if not need: ans += 1
    print(ans)

if __name__ == "__main__":
    main()