Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()

    dp_L = [set() for _ in range(N+1)]
    dp_R = [set() for _ in range(N+1)]
    dp_L[0].add(0)
    dp_R[N].add(0)
    for i in range(N):
        a = A[i]
        for n in dp_L[i]:
            dp_L[i+1].add(n)
            if n+a<K:
                dp_L[i+1].add(n+a)

    for i in range(N)[::-1]:
        a = A[i]
        for n in dp_R[i+1]:
            dp_R[i].add(n)
            if n+a<K:
                dp_R[i].add(n+a)

    for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)
    noneed = -1; need = N
    while(need-noneed>1):
        i = (need+noneed)//2
        a = A[i]
        is_need = False
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                is_need = True
                break

            l += 1

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    cnt = 0
    for i in range(N):
        if K<=i:
            cnt += N - i
            A = A[:i]
            N = i
            break

    dp_L = [set() for _ in range(N+1)]
    dp_R = [set() for _ in range(N+1)]
    dp_L[0].add(0)
    dp_R[N].add(0)
    for i in range(N):
        a = A[i]
        for n in dp_L[i]:
            dp_L[i+1].add(n)
            if n+a<K:
                dp_L[i+1].add(n+a)

    for i in range(N)[::-1]:
        a = A[i]
        for n in dp_R[i+1]:
            dp_R[i].add(n)
            if n+a<K:
                dp_R[i].add(n+a)

    for i in range(N+1):
        dp_L[i] = list(dp_L[i])
        dp_R[i] = list(dp_R[i])

    #print(dp_L)
    #print(dp_R)

    for i in range(N):
        a = A[i]
        flag = True
        L = dp_L[i]
        R = dp_R[i+1]
        l = 0; r = len(R)-1
        while(l<len(L)):
            while(0<r and K<=L[l]+R[r]):
                r -= 1
            #print(L[l]+R[r],l,r)
            if K<=L[l]+R[r]:
                break

            if K<=L[l]+R[r]+a:
                flag = False
                break

            l += 1

        if flag:
            cnt += 1
        else:
            break

    ans = cnt
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    maximum modulo k
    dp[i] = True if there exists i
    """
    _, K = read_ints()
    A = [a for a in read_ints() if a < K]
    N = len(A)
    dp = [
        [False for _ in range(K)] for _ in range(N+1)
    ]
    for i, a in enumerate(A):
        for k in range(K):
            if k-a >= 0:
                dp[i+1][k] = dp[i+1][k] or dp[i][k-a]
        dp[i+1][a] = True
    max_k = -1
    for i, d in enumerate(dp[N]):
        if d:
            max_k = i
    if max_k == -1:
        return 0
    count = 0
    for a in A:
        if max_k-2*a >= 0:
            count += 1
    return count



if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    maximum modulo k
    dp[i] = True if there exists i
    """
    _, K = read_ints()
    A = [a for a in read_ints() if a < K]
    N = len(A)
    dp = [
        [False for _ in range(K)] for _ in range(N+1)
    ]
    for i, a in enumerate(A):
        for k in range(K):
            dp[i+1][k] = dp[i+1][k] or dp[i][(k-a)%K]
        dp[i+1][a] = True
    max_k = -1
    for i, d in enumerate(dp[N]):
        if d:
            max_k = i
    count = 0
    for a in A:
        if max_k-2*a > 0:
            count += 1
    return count



if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    maximum modulo k
    dp[i] = True if there exists i
    """
    _, K = read_ints()
    A = [a for a in read_ints() if a < K]
    N = len(A)
    dp = [
        [False for _ in range(K)] for _ in range(N+1)
    ]
    for i, a in enumerate(A):
        for k in range(K):
            dp[i+1][k] = dp[i+1][k] or dp[i][(k-a)%K]
        dp[i+1][a] = True
    max_k = -1
    for i, d in enumerate(dp[N]):
        if d:
            max_k = i
    count = 0
    for a in A:
        if max_k-2*a >= 0:
            count += 1
    return count



if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    # for i in range(N):
    #      if a[i]>=K:
    #          break
    #      ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
    #      if isunnec(i):
    #          nn+=1
        # for j in range(i+1,N):
        #     if a[j]>=K:
        #         break
        #     ss[i]=mkns(a[j],ss[i],pm)
        # # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        # if ss[i]&mask(K-a[i])==0:
        #     nn+=1
    nn=biser(list(range(N)),isunnec)+1
    # print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    r=n
    while r>1:
        if func(lst[nh]):
            r=n-nh
            nh=nh+(n-nh)//2
        else:
            r=nh
            n=nh
            nh=nh//2
    if not func(lst[nh]):
        return -1
    else:
        return lst[nh]

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        ss[i+1]=mkns(a[i],ss[i],pm)
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=mkns(a[j],ss[i],pm)
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        c=a[i]
        ss[i+1]=mkns(c,ss[i],mask(0))
        a[i]=0
        for j in range(N):
            if c>=K:
                break
            ss[i]=mkns(a[j],ss[i],mask(K-c))
        a[i]=c
        if ss[i]==0:
            nn+=1
    # print([bin(x) for x in ss])
    print(nn)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    for i in range(N):
        c=a[i]
        if c>=K:
            break
        ss[i+1]=mkns(c,ss[i],mask(0))
        a[i]=0
        for j in range(N):
            if c>=K:
                break
            ss[i]=mkns(a[j],ss[i],mask(K-c))
        a[i]=c
        if ss[i]==0:
            nn+=1
    # print([bin(x) for x in ss])
    print(nn)

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

    
def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    c1i=list(range(N))
    def unneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,unneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)


def main2():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    mask=lambda c: (1<<(K))-(1<<c)
    
    def isunnec(i):
        c=cards[i]
        if c>=K:
            return False
        cards[i]=0
        ret=0
        for x in cards:
            if x!=0:
                ret=(((ret+1)<<x)|ret )&mask(0)
        cards[i]=c
        # print(i,bin(ret&mask(K-c)))
        if ret&mask(K-c)>0:
            return False
        else:
            return True
    nn=biser(list(range(N)),isunnec)
    print(nn+1)
    # for x in range(N):
    #     isunnec(x)
if __name__=='__main__':
    #main()
    main2()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(4100000)

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def findminsum(lst,K,N):
    inf=10**6
    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]


    dp=[[inf]*N for s in range(K+1)]
    for s in range(K+1):
        for j in range(N):
            if j==0 and s<=lst[j]:
                dp[s][j]=lst[0]
            elif s>lst[j] and j>0:
                dp[s][j]=min(dp[s-lst[j]][j-1]+lst[j], dp[s][j-1])
            elif s<=lst[j] and j>0:
                dp[s][j]=min(lst[j],dp[s][j-1])
    # print(lst)
    # print(dp[0][:])
    # print(dp[1][:])
    # print(dp[K][:])
    return dp[K][N-1]

    
def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    # cards=list(filter(lambda x:x<K,cards))
    # N=len(cards)
    cards.sort()
    c1i=list(range(N))
    def unneccesity(h):
        if cards[h]>=K:
            return False
        else:
            c=cards[h]
            cards[h]=0
            ret=findminsum(cards,K-c,N)>=K
            cards[h]=c
            return ret
    #nn=0
    nn=biser(ci,unneccesity)
    # for i in range(N):
    #     if cards[i]<K:
    #         c=cards[i]
    #         cards[i]=0
    #         if findminsum(cards,K-c,N)>=K:
    #             nn+=1
    #         cards[i]=c
    #     else:
    #         break
    print(nn+1)


def main2():
    N,K=map(int,sys.stdin.readline().strip().split())
    cards=list(map(int,sys.stdin.readline().strip().split()))
    mask=lambda c: (1<<(K))-(1<<c)
    
    def isunnec(i):
        c=cards[i]
        if c>K:
            return False
        cards[i]=0
        ret=0
        for x in cards:
            if x!=0:
                ret=(((ret+1)<<x)|ret )&mask(0)
        cards[i]=c
        # print(i,bin(ret&mask(K-c)))
        if ret&mask(K-c)>0:
            return False
        else:
            return True
    nn=biser(list(range(N)),isunnec)
    print(nn+1)
    # for x in range(N):
    #     isunnec(x)
if __name__=='__main__':
    #main()
    main2()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros((n + 1, k), bool)
dp[0][0] = True
for i, e in enumerate(a, 1):
    dp[i] = dp[i-1]
    dp[i, e:] |= dp[i-1, :-e]

dp2 = np.zeros((n + 1, k), bool)
dp2[0][0] = True
for i, e in enumerate(a[::-1], 1):
    dp2[i] = dp2[i-1]
    dp2[i, e:] |= dp2[i-1, :-e]

exit()
ans = 0
for i, e in enumerate(a, 1):
    li = [j for j in range(k) if dp[i-1][j]]
    li2 = [j for j in range(k) if dp2[n-i][j]]

    j = len(li2) - 1
    mx = 0
    for e2 in li:
        while j > 0 and e2 + li2[j] >= k:
            j -= 1

        if e2 + li2[j] < k:
            mx = max(mx, e2 + li2[j])

    if mx + e < k:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

list.sort(a)

tmp=[]
for i in range(n):
    if sum(tmp) >= k:
        print(len(tmp)-2)
        exit(0)
    else:
        tmp.append(a[i])
print(n)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(N):
  if A[-1]>=K:
    del A[-1]
    N-=1
L,R,M=0,N,0
DP=[0]*(K*2)
while R-L>1:
  M=(L+R+1)//2
  if M==N:
    break
  for i in range(K*2):
    DP[i]=False
  DP[0]=True
  for i in range(M):
    for j in range(K-1,-1,-1):
      DP[j+A[i]]|=DP[j]
  for i in range(K-A[M],K):
    if DP[i]:
      R=min(M,R-1)
      break
    if i==K-1:
      L=M
if L!=R:
  for i in range(K*2):
    DP[i]=False
  DP[0]=True
  for i in range(N-1):
    for j in range(K-1,-1,-1):
      DP[j+A[i]]|=DP[j]
  for i in range(K-A[N-1],K):
    if DP[i]:
      R=N-1
      break
    if i==K-1:
      L=N
print(L)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(N):
  if A[-1]>=K:
    del A[-1]
    N-=1
L,R,M=0,N,0
DP=[0]*(K*2)
while R>L:
  M=(L+R+1)//2
  if M==N:
    break
  for i in range(K*2):
    DP[i]=False
  DP[0]=True
  for i in range(M):
    for j in range(K-1,-1,-1):
      DP[j+A[i]]|=DP[j]
  for i in range(K-A[M],K):
    if DP[i]:
      R=min(M,R-1)
      break
    if i==K-1:
      L=M
if L!=R:
  for i in range(K*2):
    DP[i]=False
  DP[0]=True
  for i in range(N-1):
    for j in range(K-1,-1,-1):
      DP[j+A[i]]|=DP[j]
  for i in range(K-A[N-1],K):
    if DP[i]:
      R=N-1
      break
    if i==K-1:
      L=N
print(L)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=sorted(list(map(int,input().split())))
for i in range(N):
  if A[-1]>=K:
    del A[-1]
    N-=1
L,R,M=0,N,0
DP=[0]*(K*2)
while R>L:
  M=(L+R)//2
  for i in range(K*2):
    DP[i]=False
  DP[0]=True
  for i in range(M):
    for j in range(K-1,-1,-1):
      DP[j+A[i]]|=DP[j]
  for i in range(K-A[M],K):
    if DP[i]:
      R=M
      break
    if i==K-1:
      L=max(L+1,M)
print(L)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    #if a[i]>=k:break
    dp[a[i]:]+=dp[:-a[i]]
  return any(dp[max(0,k-a[t]):k])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    if a[i]>=k:break
    dp[a[i]:]+=dp[:-a[i]]
  return any(dp[max(0,k-a[t]):k])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    if a[i]>=k:break
    dp[a[i]:]+=dp[:-a[i]]
  return any(dp[max(0,k-a[t]):k])
l,r=0,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import numpy as np
dpl=np.full((n+1,k),False) #左からi枚目まででk未満の数について
dpr=np.full((n+1,k),False) #右からi枚目まででk未満の数について
dpl[:,0]=True
dpr[:,0]=True
for i in range(n):
  dpl[i+1]=dpl[i]
  dpr[i+1]=dpr[i]
  if a[i-1]>=k:continue
  dpl[i+1][a[i]:]+=dpl[i][:-a[i]]
  dpr[i+1][a[-i-1]:]+=dpr[i][:-a[-i-1]]
ans=0
from bisect import bisect_left,bisect_right
for i in range(1,n+1):# i枚目を取り除くことを考える。i=1,2,3...
  if a[i-1]>=k:continue
  flg=False
  ai=a[i-1]
  dpli=dpl[i-1]
  dpri=dpr[n-i]
  dl=np.where(dpli==True)[0] # i枚目より左
  dr=np.where(dpri==True)[0] # i枚目より右　それぞれから一つずつ選び、足してk-a[i-1]以上、k-1以下にできる。
  cs_dpri=[0]
  tmp=0
  for j in dpri:
    tmp+=j
    cs_dpri.append(tmp)
  for dli in dl:
    l,r=k-ai-dli,k-dli-1 # drにl以上r以下の値があればaiは必要
    lsum=cs_dpri[l]
    rsum=cs_dpri[r+1]
    if rsum>lsum:
      flg=True
      break
  if not flg:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
import numpy as np
dpl=np.zeros((n+1,k),int) #左からi枚目まででk未満の数について
dpr=np.zeros((n+1,k),int) #右からi枚目まででk未満の数について
dpl[:,0]=1
dpr[:,0]=1
for i in range(n):
  dpl[i+1]=dpl[i]
  dpr[i+1]=dpr[i]
  if a[i-1]>=k:continue
  dpl[i+1][a[i]:]+=dpl[i][:-a[i]]
  dpr[i+1][a[-i-1]:]+=dpr[i][:-a[-i-1]]
ans=0
from bisect import bisect_left,bisect_right
for i in range(1,n+1):# i枚目を取り除くことを考える。i=1,2,3...
  if a[i-1]>=k:continue
  flg=False
  ai=a[i-1]
  dpli=dpl[i-1]
  dpri=dpr[n-i]
  dl=np.where(dpli>0)[0] # i枚目より左
  dr=np.where(dpri>0)[0] # i枚目より右　それぞれから一つずつ選び、足してk-a[i-1]以上、k-1以下にできる。
  for dli in dl:
    l,r=k-ai-dli,k-dli-1 # drにl以上r以下の値があればaiは必要
    lidx=bisect_left(dr,l)
    ridx=bisect_right(dr,r)
    if lidx!=ridx:
      flg=True
      break
  if not flg:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
cnt = 0
sum1 = sum(L)
i = 0
while i <= n-1:
    sum1 -= L[i]
    if sum1 >=k:
        cnt +=1
    i +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    dpf = [set() for _ in range(N+1)]
    dpr = [set() for _ in range(N+1)]
    dpf[0].add(0)
    dpr[0].add(0)
    for i in range(N):
        for v in dpf[i]:
            dpf[i+1].add(v)
            if v+A[i] < K:
                dpf[i+1].add(v+A[i])
        for v in dpr[i]:
            dpr[i+1].add(v)
            if v+A[N-1-i] < K:
                dpr[i+1].add(v+A[N-1-i])
    ans = 0
    for i in range(N):
        neccesary = False
        for v in set(list(dpf[i]) + list(dpr[N-1-i])):
            if v + A[i] >= K:
                neccesary = True
                break
        if not neccesary:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


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

A.sort()

ans = N
total = 0

for i in range(N):
    # 後ろ(大きい方) からみていく
    a = A[N-1-i]
    # 合計に加えても K を超えないなら, 最小の部分集合に必要
    if total + a < K:
        total += a
    # そうでない場合, 不要
    else:
        ans = min(ans, i)

print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = [0]+sorted(filter(lambda x: x < k, map(int,input().split())))
n = len(a)
print(a)
def search(m):
    print(a[m])
    dp = [1] + [0]*k
    for i in range(n):
        if i == m:
            continue
        for j in range(k,a[i]-1,-1):
            dp[j] |= dp[j-a[i]]
    for i in range(k-a[m],k):
        if dp[i]:
            return True
    return False
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= k:
    print(0)
    exit()
def search(m):
    if a[m] >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] = a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] == float("INF"):
        print(n)
        exit()
    elif dp[-1][-1] >= k:
        return False
    else:
        return True
le = 0
ri = n-1


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= k:
    print(0)
    exit()
def search(m):
    if a[m] >= k:
        return True
    x = k-a[m]
    dp = [[float("INF")]*(x+1) for i in range(n)]
    dp[0][0] = 0
    now = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(x+1):
            if dp[now][j] !=float("INF"):
                dp[now+1][j] = min(dp[now][j],dp[now+1][j])
                if a[i]+j < x:
                    dp[now+1][a[i]+j] = a[i]+j
                else:    
                    dp[now+1][-1] = min(a[i]+j,dp[now+1][-1])
        now += 1
    if dp[-1][-1] == float("INF"):
        print(n)
        exit()
    elif dp[-1][-1] >= k:
        return False
    else:
        return True
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split())) + [0]
A.sort(reverse=True)

if sum(A) < K:
  print(N)
  quit()

idx = 0
left = 0
right = 1
s = A[0]
while right <= N:
  while right <= N and s + A[right] < K:
    s += A[right]
    right += 1
  if right < N:
    idx = right
  s -= A[left]
  left += 1
  if left == right:
    right += 1
    s = A[left]

print(N - idx - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    for i in range(N):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    break
                if (dp0[i]>>j)&1:
                    pass
            else:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    for i in range(N):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                pass
            else:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()