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:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0
#print(bin((1<<K)>>1))
C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)
#print(C)
    #print(bin(n))
if N<=10:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    a+=[10**9]
    H=N
    L=0
    
    while abs(H-L)>4:
        Mid=(H+L)//2
        #print(H,Mid,L)
        n=1
        for i in range(N):
            if i==Mid:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[Mid]:    
            H=Mid
        else:
            L=Mid
    #print(H,L)        
    for j in range(max(0,L-5),N):
        n=1
        for i in range(N):
            if i==j:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[j]: 
            print(j)
            exit()

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0
#print(bin((1<<K)>>1))
C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)
#print(C)
    #print(bin(n))
if N<=10:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    a+=[10**9]
    H=N
    L=0
    
    while abs(H-L)>4:
        Mid=(H+L)//2
        #print(H,Mid,L)
        n=1
        for i in range(N):
            if i==Mid:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n < (1<<K)>>a[Mid]:    
            H=Mid
        else:
            L=Mid
    #print(H,L)        
    for j in range(max(0,L-5),N):
        n=1
        for i in range(N):
            if i==j:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n < (1<<K)>>a[j]: 
            print(j)
            exit()
    print(N)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
n=1
A=[0]
for i in range(N):
    if a[i]>=K:
        A.append(A[-1])
    else:
        A.append((n|(n<<a[i]))%(1<<K))
        n=A[-1]
A.append(A[-1])
n=1
B=[0]
for i in range(N):
    if a[-1-i]>=K:
        B.append(B[-1])
    else:
        B.append((n|n<<a[-1-i])%(1<<K))
        n=B[-1]
B.append(B[-1])
B=B[::-1]
#print(A)
#print(B)
#print(bin(((1<<K)>>(a[1]-1))-1))

ans=0
for i in range(1,len(B)-1):
    if a[i-1]>=K:
        continue
    elif A[i-1]|B[i+1] < (((1<<K)>>(a[i-1]))):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
n=1
A=[0]
for i in range(N):
    if a[i]>=K:
        A.append(A[-1])
    else:
        A.append((n|(n<<a[i]))%(1<<K))
        n=A[-1]
n=1
B=[0]
for i in range(N):
    if a[-1-i]>=K:
        B.append(B[-1])
    else:
        B.append((n|n<<a[-1-i])%(1<<K))
        n=B[-1]
B=B[::-1]
#print(A)
#print(B)
#print(bin(((1<<K)>>(a[1]-1))-1))

ans=0
for i in range(1,len(B)):
    if a[i-1]>=K:
        continue
    elif A[i-1]|B[i] <= (((1<<K)>>(a[i-1]-1))-1):
        #print(A[i-1]|B[i],bin((((1<<K)>>(a[i-1]-1))-1)))
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
n=1
A=[0]
for i in range(N):
    if a[i]>=K:
        A.append(A[-1])
    else:
        A.append((n|(n<<a[i]))%(1<<K))
        n=A[-1]
n=1
B=[0]
for i in range(N):
    if a[-1-i]>=K:
        B.append(B[-1])
    else:
        B.append((n|n<<a[-1-i])%(1<<K))
        n=B[-1]
B=B[::-1]
#print(A)
#print(B)
#print(bin(((1<<K)>>(a[1]-1))-1))

ans=0
for i in range(1,len(B)):
    if a[i-1]>=K:
        continue
    elif A[i-1]|B[i] < (((1<<K)>>(a[i-1]-1))-1):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
n=1
A=[0]
for i in range(N):
    A.append((n|(n<<a[i]))%(1<<K))
    n=A[-1]
n=1
B=[0]
for i in range(N):
    B.append((n|n<<a[-1-i])%(1<<K))
    n=B[-1]
B=B[::-1]
#print(A)
#print(B)
#print(bin(((1<<K)>>(a[1]-1))-1))

ans=0
for i in range(1,len(B)):
    if A[i-1]|B[i] < (((1<<K)>>(a[i-1]-1))-1):
        ans+=1
print(ans)

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 = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    tmp = dpm[N-i-1]
    for j in range(1, a+1):
        tmp |= tmp<<j
    tmp &= (1<<K)-1
    if not dp2&tmp:
        r += 1
#    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
#        if dp2&(1<<j) and dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
            # K-j > x >= K-j-a
#            break
#    else:
#        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    tmp = dpm[N-i-1]
    for j in range(1, a+1):
        tmp |= tmp<<j
    tmp &= (1<<K)-1
    if not dp2&dpm[N-i-1]:
        r += 1
#    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
#        if dp2&(1<<j) and dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
            # K-j > x >= K-j-a
#            break
#    else:
#        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
dp = [1] + [0]*(2*K-1)
r = 0
for a in A:
    for i in range(2*K-1, -1, -1):
        if i - a >= 0:
            dp[i] = dp[i] + dp[i-a]

A = set(A)
for i in range(K):
    tmp = set()
    for a in A:
        if i+a >= K:
            if dp[i] and dp[i+a]:
                tmp.add(a)
    for b in tmp:
        A.remove(b)
print(len(A))

Submission status: Wrong Answer

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

def check(a, l, r):
    if (l*r&filt).bit_length() + a > K:
        return True
    else:
        return False

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
A = [a for a in A if a < K]
A.sort()
filt = (1<<K) - 1
M = len(A)
dpl = [0]*(M+2)
dpr = [0]*(M+2)
dpl[0] = 1
dpr[M+1] = 1

for i in range(1, M+1):
    dpl[i] = ((dpl[i-1]*(1<<A[i-1]))&filt) |dpl[i-1]

for i in range(M, 0, -1):
    dpr[i] = ((dpr[i+1]*(1<<A[i-1]))&filt) |dpr[i+1]
    
ok = M+1
ng = 0
while abs(ok - ng) > 1:
    med = (ok+ng)//2
    if check(A[med-1], dpl[med-1], dpr[med+1]):
        ok = med
    else:
        ng = med
print(ng)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
A = [0 if a >= K else a for a in A]
X = [1] * N
Y = [1] * N
m = (1<<K*8) - 1
for i in range(N-1):
    X[i+1] = X[i] * ((1<<8*A[i]) + 1 if A[i] else 1) & m
for i in range(1, N)[::-1]:
    Y[i-1] = Y[i] * ((1<<8*A[i]) + 1 if A[i] else 1) & m

ans = N
for i in range(N):
    if A[i] == 0 or ((X[i] * Y[i] & m) >> 8 * (K - A[i])) & ((1 << 8 * A[i]) - 1):
        ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A = [x if x <= K else K + 1 for x in A]

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - A[x])
    return (dp > 0)

left = -1 # 必要
right = N # 不要
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = left + 1
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
else:
    # Find the Smallest Necessary Number 
    # SmallNec = N-1
    A_cumsum = np.concatenate(([0], np.cumsum(A)))
    # SubSet A[0:I]
    I = np.where(A_cumsum<K)[0][-1] + 1
    Sum_ = A_cumsum[I]
    while Sum_ >= K:
        for J in xrange(I-1, -1, -1):
            if A[J] >= Sum_ - K:
                # A[J] is Necessary
                I = J
                pass
            else:
                # A[J] Maybe Unnecessary
                break
        Sum_ = A_cumsum[I]
    print I

Submission status: Wrong Answer

Solution code:
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
else:
    A_cumsum = np.concatenate(([0], np.cumsum(A)))
    I = np.where(A_cumsum<K)[0][-1] + 1
    Sum_ = A_cumsum[I]
    while Sum_ > K:
        for J in xrange(I-1, -1, -1):
            if A[J] <= Sum_ - K:
                break
        I = J + 1
        Sum_ = A_cumsum[I]
    print I

Submission status: Wrong Answer

Solution code:

import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
else:
    A_cumsum = np.concatenate(([0], np.cumsum(A)))
    I = np.where(A_cumsum<K)[0][-1] + 1
    Sum_ = A_cumsum[I]
    while Sum_ > K:
        for J in xrange(I-1, -1, -1):
            if A[J] <= Sum_ - K:
                break
            I = J + 1
            Sum_ = A_cumsum[I]
    print I

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
    sys.exit()
   
A_cumsum = np.concatenate(([0], np.cumsum(A)))
I = np.where(A_cumsum<K)[0][-1] + 1

Sum_ = A_cumsum[I]
while Sum_ > K:
    for J in xrange(I-1, -1, -1):
        if A[J] <= Sum_ - K:
            break
    I = J + 1
    Sum_ = A_cumsum[I]

print I

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
    sys.exit()
   
A_cumsum = np.concatenate(([0], np.cumsum(A)))
I = np.where(A_cumsum<K)[0][-1] + 1

Sum_ = np.sum(A[:I])
while Sum_ > K:
    for J in xrange(I-1, -1, -1):
        if A[J] <= Sum_ - K:
            break
    I = J + 1
    Sum_ = np.sum(A[:I])

print I

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          break
    else:
      ok = mid
print(n-ok)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M)[:: -1]:
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, right):
                isNess[j] = True
            break

ans += sum(isNess)
print(N - ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    if (accA[right] - accA[left]) + A[right] >= K:
        isNess[right] = True
        for j in range(left, right):
            isNess[j] = True

ans += sum(isNess)
print(N - ans)

Submission status: Wrong Answer

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

def no_need(i):
    assert 0 <= i <= N
    if i==0: return True
    i -= 1
    s = set([0])
    for j in range(N-1,-1,-1):
        if i==j: continue
        t = set()
        for a in s:
            if K-A[i] <= a+A[j] < K:
                return False
            t.add(a)
            t.add(a+A[j])
        s = t
    return True

ok = 0
ng = N+1
while ng-ok > 1:
    m = (ok+ng)//2
    if no_need(m):
        ok = m
    else:
        ng = m
print(ok)

Submission status: Wrong Answer

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

# 必須なカードを求める
A.sort(reverse=True)
right = 0
cum = 0

ans = {a : False for a in A}

for left in range(N):
    while right < N and cum < K:
        cum += A[right]
        right += 1

    if cum >= K:
        for i in range(left, right):
            ans[A[i]] = True

    cum -= A[left]

cnt = 0
for a in A:
    if ans[a]:
        cnt += 1

print(N - cnt)

Submission status: Wrong Answer

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

# 必須なカードを求める
A.sort(reverse=True)
right = 0
cum = 0

ans = [False] * N

for left in range(N):
    while right < N and cum < K:
        cum += A[right]
        right += 1

    if cum >= K:
        ans[left: right] = [True] * (right - left)

    cum -= A[left]

print(N - ans.count(True))

Submission status: Wrong Answer

Solution code:
def main():
  n, k = map(int, input().split())
  alist = list(map(int, input().split()))
  aset = list(sorted(set(alist)))
  l, r = 0, len(aset)
  while l < r:
    mid = (l + r) // 2
    dp = [False for _ in range(k)]
    dp[0] = True
    for i, a in enumerate(aset):
      if a >= k:
        break
      if i == mid:
        continue
      tmp_dp = dp[:]
      for _k in range(1, k):
        if _k >= a and not tmp_dp[_k]:
          tmp_dp[_k] = dp[_k-a]
      dp = tmp_dp
    is_need = False
    for _k in range(max(0, k-aset[mid]), k):
      if dp[_k]:
        is_need = True
        break
    if is_need:
      r = mid
    else:
      l = mid + 1
  ans = 0
  if r == len(aset):
    print(n)
  else:
    ar = aset[r]
    for a in alist:
      if a < ar:
        ans += 1
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n, k = map(int, input().split())
  alist = list(map(int, input().split()))
  aset = list(sorted(set(alist)))
  l, r = 0, len(aset)
  while l < r:
    mid = (l + r) // 2
    dp = [False for _ in range(k)]
    dp[0] = True
    for i, a in enumerate(alist):
      if a >= k:
        break
      if i == mid:
        continue
      tmp_dp = dp[:]
      for _k in range(1, k):
        if _k >= a and not tmp_dp[_k]:
          tmp_dp[_k] = dp[_k-a]
      dp = tmp_dp
    is_need = False
    for _k in range(max(0, k-aset[mid]), k):
      if dp[_k]:
        is_need = True
        break
    if is_need:
      r = mid
    else:
      l = mid + 1
  ans = 0
  if r == len(aset):
    print(n)
  else:
    ar = aset[r]
    for a in alist:
      if a < ar:
        ans += 1
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
  n, k = map(int, input().split())
  alist = list(map(int, input().split()))
  l, r = 0, n
  while l < r:
    mid = (l + r) // 2
    dp = [[False for _ in range(n)] for _ in range(k)]
    for i in range(n):
      dp[0][i] = True
    skipped = False
    for i, a in enumerate(alist):
      if i == mid:
        skipped = True
        continue
      for _k in range(1, k):
        previ = i-1 if skipped else i
        if _k < a:
          dp[_k][previ+1] = dp[_k][previ]
        else:
          dp[_k][previ+1] = dp[_k][previ] or dp[_k-a][previ]
    if any(dp[_k][-1] for _k in range(max(0, k-alist[mid]), k)):
      r = mid
    else:
      l = mid + 1
  print(r)

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

def subset_sum(mid):
    if a[mid] >= k:
        return True
    dp = [False]*k
    dp[0] = True
    kk = 0
    for i in range(n):
        if i == mid:
            continue
        for j in range(kk)[::-1]:
            if j + a[i] >= k:
                continue
            dp[j + a[i]] |= dp[j]
        kk = min(k - 1, kk + a[i])
    return sum(dp[k-a[mid]:])
  
ok = -1
ng = n
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if subset_sum(mid):
        ng = mid
    else:
        ok = mid
print(ng)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = tuple([0] + sorted(a) + [k])
li_n = n-1

def subset_sum(mid):
    if a[mid] >= k:
        return False
    li = a[0:mid] + a[mid+1:]
    dp = [False]*(k + 1)
    dp[0] = True    
    for i in range(li_n):
        for j in range(k+1)[::-1]:
            if j - li[i] < 0:
                break
            else:
                dp[j] |= dp[j - li[i]]

    if not any(dp[k-a[mid]:k]):
        return True
    else:
        return False
  
ok = 0
ng = n+2
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    if subset_sum(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 = [0] + sorted(a) + [k]


def subset_sum(a):
    n = len(a)
    dp = [False]*(k + 1)
    dp[0] = True
    for i in range(n):
        for j in range(k+1)[::-1]:
            if j - a[i] < 0:
                break
            else:
                dp[j] = dp[j] or dp[j - a[i]]
    return dp
  
ok = 0
ng = n + 2
while abs(ng - ok) > 1:
    mid = (ok + ng) // 2
    li = a[0:mid] + a[mid+1:]
    dp = subset_sum(li)
    if not any(dp[k-a[mid]:k]):
        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 = [0] + sorted(a) + [k]


def subset_sum(a):
    n = len(a)
    dp = [[False]*(k + 1) for i in range(n + 1)]
    dp[0][0] = True
    for i in range(n):
        for j in range(k+1):
            if j - a[i] < 0:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] or dp[i][j - a[i]]
    return dp[n]
  
ok = 0
ng = n + 2
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    li = a[0:mid] + a[mid+1:]
    dp = subset_sum(li)
    if not any(dp[k-a[mid]:k]):
        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()))
dp=[0]*k
su=[[] for i in range(k)]
dp[0]=1
for i in range(n):
    for j in range(k-1,-1,-1):
        if dp[j]>0 and a[i]+j<k:
            dp[a[i]+j]+=1
            su[a[i]+j]+=[i]
            su[a[i]+j]+=su[j]
ans=n
for i in range(n):
    if a[i]<k:
        f=0
        for j in range(k-1,k-a[i]-1,-1):
            if f==0 and dp[j]>0 and su[j].count(i)!=dp[j]:
                ans-=1
                f=1
    else:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*k
su=[[] for i in range(k)]
dp[0]=1
for i in range(n):
    for j in range(k-1,-1,-1):
        if dp[j]>0 and a[i]+j<k:
            dp[a[i]+j]+=1
            su[a[i]+j]+=[i]
            su[a[i]+j]+=su[j]
ans=n
for i in range(n):
    if a[i]<k:
        f=0
        for j in range(k-1,k-a[i]-1,-1):
            if f==0 and dp[j]>0 and su[j].count(i)!=1:
                ans-=1
                f=1
    else:
        ans-=1
print(ans)

Submission status: Wrong Answer

Solution code:
#O(ElogV)
import heapq
import sys
input = sys.stdin.readline

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

if sum(a) < k:
    print(n)
    exit()

res = -1
for i in range(n-1):
    if a[i] >= k:
        res = i
        break
    if a[i]+a[i+1] >= k and a[i+1] < k:
        res = i
        break
if res == -1:
    if a[-1] >= k:
        print(n-1)
    else:
        print(n)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
#O(ElogV)
import heapq
import sys
input = sys.stdin.readline

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

if sum(a) < k:
    print(n)

res = -1
for i in range(n-1):
    if a[i] >= k:
        res = i
        break
    if a[i]+a[i+1] >= k and a[i+1] < k:
        res = i
        break
if res == -1:
    if a[-1] >= k:
        print(n-1)
    else:
        print(n)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
#O(ElogV)
import heapq
import sys
input = sys.stdin.readline

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

if sum(a) < k:
    print(n)

res = -1
for i in range(n-1):
    if a[i] >= k:
        res = i
        break
    if a[i]+a[i+1] >= k and a[i+1] < k:
        res = i
        break
if n == -1:
    if a[-1] >= k:
        print(n-1)
    else:
        print(n)
else:
    print(res)

Submission status: Wrong Answer

Solution code:
import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if not check(1):
    print(0)
    sys.exit()

if check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
migi = [[0]*k for i in range(n)]
hidari = [[0]*k for i in range(n)]
matome = set()
matome.add(0)
hidari[0][0] = 1
for i in range(1,n):
  for j in list(matome):
    hidari[i][j] = 1
    if j + a[i-1] < k:
      matome.add(j + a[i-1])
      hidari[i][j + a[i-1]] = 1
matome = set()
matome.add(0)
migi[n-1][0] = 1
for i in range(n-2,-1,-1):
  for j in list(matome):
    migi[i][j] = 1
    if j + a[i+1] < k:
      matome.add(j + a[i+1])
      migi[i][j + a[i+1]] = 1

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
dp = [set() for i in range(n)]
dp2 = [float("inf")]*n
matome = set()
matome.add(0)
for i in range(n):
  for j in list(matome):
    if j + a[i] >= k:
      dp2[i] = min(dp2[i],j+a[i])
    else:
      dp[i].add(j+a[i])
      matome.add(j+a[i])
  for j in range(i-1):
    for l in list(dp[j]):
      if l + a[i] >= k:
        dp2[j] = min(dp2[j],l+a[i])
      else:
        dp[j].add(l+a[i])
        matome.add(l+a[i])   
ans = 0
for i in range(n):
  if dp2[i] - a[i] >= k:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K+1)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<=K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
import sys
def inpl(): return [int(i) for i in input().split()]
def search(a,j):
    if D[j]:
        if D[j] == 1:
            return True
        else:
            return False
    H = defaultdict(lambda: 0)
    H[0] = True
    for i in a:
        for ni,nv in H.copy().items():
            if ni + i < K-j:
                H[ni+i] = True
                continue
            elif ni + i <= K-1:
                D[j] = 1
                return True
    D[j] = -1
    return False

N, K = inpl()
A = inpl()
A.sort()
A = A[:bisect.bisect_left(A,K)]
M = len(A)
D = defaultdict(lambda: 0)
if sum(A) < K:
    print(M)
    sys.exit()
if sum(A) == K:
    print(0)
    sys.exit()
lo = -1
hi = M
while hi - lo > 1:
    me = (hi+lo)//2
    B = A[:me] + A[me+1:]
    if search(B, me):
        hi = me
    else:
        lo = me
print(hi)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

def needcheck(nums, n, ind, maxnum):
    low = max(0, n-nums[ind])
    storage = [0 for j in range(n + maxnum + 1)]
    for i, num in enumerate(nums):
        if i == ind:
            pass
        else:
            for j, loc in enumerate(storage[:n]):
                if loc == 1:
                    storage[j + num] = 1
            storage[num] = 1
    if 1 in storage[low:n]:
        return False
    else:
        return True

N, K = getNM()
nums = getList()
maxnum = max(nums)
ans = 0

for ind in range(N):
    if needcheck(nums, K, ind, maxnum):
        ans += 1
    else:
        pass

print(ans)

Submission status: Wrong Answer

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		#dp[0] = True
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):

			#dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(K - 1, 0, -1):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				#if dp[k] == True:
					#dp2[k] = True
				
				#elif k > b[j]:
				if dp[k] == True and K - a[i] <= k:
					return True
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True and K - a[i] <= k:
						return True
						#dp[j][k] = True
						#dp[k] = True

				#if dp[j][k] == True and K - a[i] <= k < K:
				#if dp[k] == True and K - a[i] <= k:
					#return True

			#print(dp)
			#dp = dp2

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid + 1, upper)


	print(bi_search(0, N - 1))

Submission status: Wrong Answer

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		#dp[0] = True
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):

			#dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(K - 1, 0, -1):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				#if dp[k] == True:
					#dp2[k] = True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True and K - a[i] <= k:
						return True
						#dp[j][k] = True
						#dp[k] = True

				#if dp[j][k] == True and K - a[i] <= k < K:
				#if dp[k] == True and K - a[i] <= k:
					#return True

			#print(dp)
			#dp = dp2

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid + 1, upper)


	print(bi_search(0, N - 1))