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:
# -*- 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:
                    if (dp1[i]<<j):
                        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
    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
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
    ans=0
    for i in range(N):
        if K>a[i]:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(K):
                if (dp0[i]>>j)&1:
                    if (dp1[i]<<j)&mask2:
                        break
            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
        if a[N-i-1]<=K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
    ans=0
    for i in range(N):
        if K>a[i]:
            mask2=(1<<a[i])-1
            for j in range(K):
                if (dp0[i]>>j)&1:
                    n=K-a[i]-j
                    if n>0:
                        res=((dp1[i])>>n)&mask2
                    else:
                        res=((dp1[i])<<-n)&mask2
                    if res>0:
                        break
            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
        if a[N-i-1]<=K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
    ans=0
    for i in range(N):
        if K>a[i]:
            for j in range(K):
                if (dp0[i]>>j)&1:
                    if (dp1[i]>>max(K-a[i]-j,0))&((1<<a[i])-1)>0:
                        break
            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
        if a[N-i-1]<=K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
    ans=0
    for i in range(N):
        if K>a[i]:
            dp=dp0[i]|dp1[i]
            for j in range(1,K):
                if (dp1[i]>>j)&1:
                    dp|=(dp0[i]<<j)&mask
            if dp>>(K-a[i])==0:
                ans+=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
alist.sort(reverse=True)

if sum(alist)<K:
  print(len(alist))
  sys.exit(0)
  
need_list=[False]*N
for i in range(N):
  for j in range(i+1,N):
    mlist=[alist[i]]
    msum=alist[i]
    ilist=[i]
    
    for k in range(j,N):
      if msum>=K:
        break
      mlist.append(alist[k])
      msum+=alist[k]
      ilist.append(k)
        
    if msum>=K:
      #print(mlist,msum,ilist)
      for ii in ilist:
        need_list[ii]=True
        
#print(need_list)
print(need_list.count(False))

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*N
for i in range(N):
  if A[i]>=K:
    B[i]=1
    continue
  for j in range(i+1,N):
    if A[j]<K:
      if A[i]+A[j]>=K:
        B[i]=1;B[j]=1

print(B.count(0))

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp_l = np.zeros((n + 1, k + 1), np.int16)
dp_l[0][0] = 1

for i, e in enumerate(a):
    dp_l[i+1] += dp_l[i]
    dp_l[i+1][e:] += dp_l[i][:-e]
    dp_l[i+1][k] += dp_l[i][-e:].sum()

dp_r = np.zeros((n + 1, k + 1), np.int16)
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1][e:] += dp_r[i][:-e]
    dp_r[i+1][k] += dp_r[i][-e:].sum()

dp_r = np.cumsum(dp_r[:, ::-1], axis=1)[::-1]

base = dp_l[n][k]
cnt = np.sum(dp_l[:-1] * dp_r[1:], axis=1)
cnt *= 2
ans = np.count_nonzero(cnt == base)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp_l = np.zeros((n + 1, k + 1), int)
dp_l[0][0] = 1

for i, e in enumerate(a):
    dp_l[i+1] += dp_l[i]
    dp_l[i+1][e:] += dp_l[i][:-e]
    dp_l[i+1][k] += dp_l[i][-e:].sum()

dp_r = np.zeros((n + 1, k + 1), int)
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1][e:] += dp_r[i][:-e]
    dp_r[i+1][k] += dp_r[i][-e:].sum()

dp_r = np.cumsum(dp_r[:, ::-1], axis=1)[::-1]

base = dp_l[n][k]
cnt = np.sum(dp_l[:-1] * dp_r[1:], axis=1)
cnt *= 2
ans = np.count_nonzero(cnt == base)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp_l = np.zeros((n + 1, k + 1), np.int32)
dp_l[0][0] = 1

for i, e in enumerate(a):
    dp_l[i+1] += dp_l[i]
    dp_l[i+1][e:] += dp_l[i][:-e]
    dp_l[i+1][k] += dp_l[i][-e:].sum()

dp_r = np.zeros((n + 1, k + 1), np.int32)
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1][e:] += dp_r[i][:-e]
    dp_r[i+1][k] += dp_r[i][-e:].sum()

dp_r = np.cumsum(dp_r[:, ::-1], axis=1)[::-1]

base = dp_l[n][k]
cnt = np.sum(dp_l[:-1] * dp_r[1:], axis=1)
cnt *= 2
ans = np.count_nonzero(cnt == base)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp_l = np.zeros((n + 1, k + 1), np.int64)
dp_l[0][0] = 1

for i, e in enumerate(a):
    dp_l[i+1] += dp_l[i]
    dp_l[i+1][e:] += dp_l[i][:-e]
    dp_l[i+1][k] += dp_l[i][-e:].sum()

dp_r = np.zeros((n + 1, k + 1), np.int64)
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1][e:] += dp_r[i][:-e]
    dp_r[i+1][k] += dp_r[i][-e:].sum()

dp_r = np.cumsum(dp_r[:, ::-1], axis=1)[::-1]

base = dp_l[n][k]
cnt = np.sum(dp_l[:-1] * dp_r[1:], axis=1)
cnt *= 2
ans = np.count_nonzero(cnt == base)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp_l = np.zeros((n + 1, k + 1), np.uint64)
dp_l[0][0] = 1

for i, e in enumerate(a):
    dp_l[i+1] += dp_l[i]
    dp_l[i+1][e:] += dp_l[i][:-e]
    dp_l[i+1][k] += dp_l[i][-e:].sum()

dp_r = np.zeros((n + 1, k + 1), np.uint64)
dp_r[0][0] = 1

for i, e in enumerate(a[::-1]):
    dp_r[i+1] += dp_r[i]
    dp_r[i+1][e:] += dp_r[i][:-e]
    dp_r[i+1][k] += dp_r[i][-e:].sum()

dp_r_acc = np.cumsum(dp_r[:, ::-1], axis=1)[::-1]

base = dp_l[n][k]
cnt = np.sum(dp_l[:-1] * dp_r_acc[1:], axis=1)
cnt *= 2
ans = np.count_nonzero(cnt == base)

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
a = sorted(list(map(int,input().split())))
ans = 0
lo = 0
hi = N
while hi-lo > 1:
    mid = (hi+lo)//2
    dp = [[0]*(K+1) for _ in range(N)]
    dp[0][0] = 1
    f = 0
    for i in range(N):
        if i == mid:
            f = 1
        else:
            for j in range(K+1):
                if j >= a[i]:
                    dp[i+1-f][j] = dp[i-f][j] or dp[i-f][j-a[i]]
                else:
                    dp[i+1-f][j] = dp[i-f][j]
    f = 1
    for i in range(max(0,K-a[mid]),K):
        if dp[N-1][i] == 1:
            f = 0
            break
    if f == 0:
        hi = mid
    else:
        lo = mid
print(hi)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
a = list(map(int,input().split()))
if N > 400 or K > 400:
    print(-1)
    exit(0)
# a[k]以外で部分集合を作り、K-a[k]以上K未満のものがあれば、そこにa[k]が必要なので、いる
ans = 0
for k in range(N):
    dp = [[0]*(K+1) for _ in range(N)]
    dp[0][0] = 1
    f = 0
    for i in range(N):
        if i == k:
            f = 1
        else:
            for j in range(K+1):
                if j >= a[i]:
                    dp[i+1-f][j] = dp[i-f][j] or dp[i-f][j-a[i]]
                else:
                    dp[i+1-f][j] = dp[i-f][j]
    f = 1
    for i in range(max(0,K-a[k]),K):
        if dp[N-1][i] == 1:
            f = 0
            break
    ans += f
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


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

dp1 = [[0] * (K + 1) for _ in range(N + 1)]
dp1[0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(K + 1):
        here = dp1[i][j]
        dp1[i + 1][min(K, j + a)] |= here
        dp1[i + 1][j] |= here

dp2 = [[0] * (K + 1) for _ in range(N + 1)]
dp2[0][0] = 1
for i in range(N):
    a = A[N - 1 - i]
    for j in range(K + 1):
        here = dp2[i][j]
        dp2[i + 1][min(K, j + a)] |= here
        dp2[i + 1][j] |= here


def solve(i):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            return True
    return False


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N - 1
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)

Submission status: Wrong Answer

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = set()
    dp.add(0)
    ans = set(x for x in range(max(0, K - A[n] + 1), K))
    rst = False
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K - a - 1, -1, -1):
            if j in dp:
                if j + a in ans:
                    rst = True
                    break
                else:
                    dp.add(min(K, j + a))
    else:
        rst = any(k in dp for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
p=0
def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func
import itertools
for m in a:
    p=0
    temp=a.copy()
    temp.remove(m)
    # print(temp)
    for i in range(1,n):
        ans=list(itertools.combinations(temp,i))
        # print(ans)
        if p==1:
            break
        for l in range(len(ans)):
            # print(sum(ans[l]))
            if (k-m<=sum(ans[l])<k)and(p==0):
                p+=1
                cnt+=1
                break
                
        
                # print('カウント'+'cnt')
# print(cnt)
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
p=0
import itertools
for m in a:
    p=0
    temp=a.copy()
    temp.remove(m)
    # print(temp)
    for i in range(1,n):
        ans=list(itertools.combinations(temp,i))
        # print(ans)
        if p==1:
            break
        for l in range(len(ans)):
            # print(sum(ans[l]))
            if (k-m<=sum(ans[l])<k)and(p==0):
                p+=1
                cnt+=1
                break
                
        
                # print('カウント'+'cnt')
# print(cnt)
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
p=0
import itertools
for m in a:
    p=0
    temp=a.copy()
    temp.remove(m)
    # print(temp)
    for i in range(1,n):
        ans=list(itertools.combinations(temp,i))
        # print(ans)
        for l in range(len(ans)):
            # print(sum(ans[l]))
            if (k-m<=sum(ans[l])<k)and(p==0):
                p+=1
                cnt+=1
            break
        break
                # print('カウント'+'cnt')
# print(cnt)
print(n-cnt)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
p=0
import itertools
for m in a:
    p=0
    temp=a.copy()
    temp.remove(m)
    # print(temp)
    for i in range(1,n):
        ans=list(itertools.combinations(temp,i))
        # print(ans)
        for l in range(len(ans)):
            # print(sum(ans[l]))
            if (k-m<=sum(ans[l])<k)and(p==0):
                p+=1
                cnt+=1
                # print('カウント'+'cnt')
# print(cnt)
print(n-cnt)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left as bl
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = np.zeros(k, dtype=np.int32)
    dp[0] = 1
    m = bl(a, k)
    for i in range(m):
        aa = a[i]
        dp[aa:] = (dp[aa:]+dp[:k-aa]) % mod

    def b_search(ok, ng):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def value(i):
        if i == m:
            return False
        aa = a[i]
        dp2 = np.zeros(k, dtype=np.int32)
        dp2[:aa] = dp[:aa]
        for j in range(aa, k):
            dp2[j] = (dp[j]-dp2[j-aa]) % mod
        for j in range(k-aa, k):
            if dp2[j] != 0:
                return False
        return True
    print(b_search(0, m)+1)


main()

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

Submission status: Wrong Answer

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

#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(1,K):
            dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

    else:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(1,K):
            if i>=K-A[num]:
                dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

#必要な数のうち最小のもの
if N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)

Submission status: Wrong Answer

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

#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(1,K):
            dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

    else:
        dp=[[False for i in range(0,K)] for i in range(0,N)]
        for i in range(1,K):
            if i>=K-A[num]:
                dp[0][i]=True

        for i in range(1,N):
            for j in range(0,K):
                if K>j+test[i-1]:
                    dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
                else:
                    dp[i][j]=dp[i-1][j]

        return dp[N-1][0]

#必要な数のうち最小のもの
start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if condition(t):
        end=t
    else:
        start=t

if condition(start):
    print(start)
elif condition(end):
    print(end)
else:
    print(N)

Submission status: Wrong Answer

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

def condition(num):
    if N>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    dp=[[False for i in range(0,K)] for j in range(0,N)]
    for i in range(0,K):
        if K-1>=i>=max(K-A[num],1):
            dp[0][i]=True
    for i in range(1,N):
        for j in range(0,K):
            if K>j+test[i-1]:
                dp[i][j]=dp[i-1][j] or dp[i-1][j+test[i-1]]
            else:
                dp[i][j]=dp[i-1][j]
    return dp[N-1][0]

if N==1:
    if K>A[0]:
        print(1)
    else:
        print(0)
else:
    start=0
    end=N-1
    ans=0
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        ans=start
    else:
        if condition(end):
            ans=end
        else:
            ans=N
    print(ans)

Submission status: Wrong Answer

Solution code:
import copy

tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]
a = list(map(int, input().split()))
dp = [[0 for j in range(2*k+2)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(2*k+1):
        if j>=a[i]:
            dp[i+1][j]=dp[i][j]+dp[i][j-a[i]]
        else:
            dp[i+1][j]=dp[i][j]

ans = 0

for ii in range(n):
    dp2 = copy.copy(dp[n])
    if a[ii]>=k:
        ans+=1
    else:
        fl = True
        for i in range(k):
            if dp2[i]>0:
                if i>=k-a[ii]:
                    fl = False
                    break
                else:
                    dp2[i+a[ii]]-=dp2[i]
        if fl:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

tmp = list(map(int, input().split()))
n = tmp[0]
k = tmp[1]
a = list(map(int, input().split()))
dp = [[0 for j in range(2*k+2)] for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(2*k+1):
        if j>=a[i]:
            dp[i+1][j]=dp[i][j]+dp[i][j-a[i]]
        else:
            dp[i+1][j]=dp[i][j]

ans = 0

for ii in range(n):
    dp2 = copy.copy(dp[n])
    if a[ii]>=k:
        ans+=1
    else:
        for i in range(k):
            if dp2[i]>0:
                if i>=k-a[ii]:
                    ans+=1
                    break
                else:
                    dp2[i+a[ii]]-=dp2[i]
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort(reverse = True)
    
    
    #i番目までを使ってjが作れるかどうか
    dp=[[0]*K for _ in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(K):
            if dp[i][j]==1:
                dp[i+1][j]=1
                jj=j+a[i]
                if jj<K:
                    dp[i+1][jj]=1
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良い               
    def ch(x):
        if a[x]>=K:
            return True
        else:
            for j in range(a[x]):
                if dp[x][-1-j]==1:
                    return True
        return False
    
                        
    ng=N
    ok=-1
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(N-(ok+1))
    
    
   
    
            
    
    
    

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    b=LI()
    a=[]
    #K以上は不要
    for i in range(N):
        if b[i]<K:
            a.append(b[i])
    a.sort()
    N=len(a)
    
    #下位の連続するn枚が不要なはず
    
    #X番目の数が必要かどうか判定，X+1番目以降の数で，和がK未満，K-a[X]以上のものが作れれば良い
    def ch(X):
        NN=N-(X+1)
        #X+1番目以降のi番目までを使ってjが作れるかどうか
        dp=[[0]*K for _ in range(NN+1)]
        dp[0][0]=1
        for i in range(NN):
            for j in range(K):
                if dp[i][j]==1:
                    dp[i+1][j]=1
                    jj=j+a[X+1+i]
                    if jj<K:
                        dp[i+1][jj]=1
        
                        
        for j in range(a[X]):
            if dp[-1][-1-j]==1:
                return True
        return False
                
        
        
    
    ng=-1
    ok=N
    while ok-ng>1:
        med=(ok+ng)//2
        
        if ch(med):#med番目の数が必要ならば
            ok=med
        else:
            ng=med
        
            
            
    print(ng+1)
            
    
    
    

main()

Submission status: Wrong Answer

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-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: Wrong Answer

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
print(sepa[r]+1)

Submission status: Wrong Answer

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)
  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[-1] & 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)
l = 0
r = m-1
while l<r:
  mid = (l+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if x < n-1:
    if maxsum(a[x+1:],k)+sumx >= k:
      r = mid
    else:
      l = mid+1
  else:
    r -= 1

Submission status: Wrong Answer

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)
  print(ls)
  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[-1] & 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()
l = 0
r = n+1
while l+1<r:
  x = (l+r)//2
  sumx = acc[x]
  if x < n-1:
    if maxsum(a[x+1:],k)+sumx >= k:
      r = x
    else:
      l = x
  else:
    r -= 1
print(r)

Submission status: Wrong Answer

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

a.sort()

def possible(n):
    if a[n]>=K:
        return True
    b = [a[i] for i in range(N) if i!=n]
    dp = [[False]*K for _ in range(N)]
    dp[0][0] = True
    for i in range(N-1):
        for k in range(K):
            if k>=b[i]:
                dp[i+1][k] = dp[i][k-b[i]] or dp[i][k]
            else:
                dp[i+1][k] = dp[i][k]
    res = False
    for k in range(K-a[n],K):
        res = res or dp[N-1][k]
    return res

ng = -1
ok = N
m = (ng+ok)//2
for i in range(30):
    if possible(m):
        ok = m
    else:
        ng = m
    m = (ng+ok)//2

print(ok)

Submission status: Wrong Answer

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

a.sort()

def possible(n):
    if a[n]>=K:
        return True
    b = [a[i] for i in range(N) if i!=n]
    dp = [[False]*K for _ in range(N)]
    dp[0][0] = True
    for i in range(N-1):
        for k in range(K):
            if k>=b[i]:
                dp[i+1][k] = dp[i][k-b[i]] or dp[i][k]
            else:
                dp[i+1][k] = dp[i][k]
    res = False
    for k in range(K-a[n],K):
        res = res or dp[N-1][k]
    return res

ng = -1
ok = N
m = (ng+ok)//2
for i in range(15):
    if possible(m):
        ok = m
    else:
        ng = m
    m = (ng+ok)//2

print(ok)

Submission status: Wrong Answer

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

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = np.zeros(k, dtype=np.int64)
dp[0] = 1
for i in range(n):
  a = A[i]
  dp[a:] += dp.copy()[:-a]

ans = 0
for i in range(n):
  a = A[i]
  for j in range(max(0, k-a), k):
    temp = dp[j::-a*2].sum() - dp[j-a::-a*2].sum()
    if temp:
      break
  else:
    ans += 1
print(ans)