Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    
    def trans(v):
    	l = [0] * (k + 1)
    	for i in range(k + 1):
        	l[i] = (v & 1)
        	v >>= 1
    	return l
  
    a.sort()
    lef = [1] * n
    rig = [1] * n
    mask = (1 << (k + 1)) - 1
    for i in range(n - 1):
        lef[i + 1] = lef[i] | (lef[i] << a[i]) & mask
        rig[-i - 2] = rig[-i - 1] | (rig[-i - 1] << a[-i - 1]) & mask
    ok = -1
    ng = n
    while ng - ok > 1:
        mid = (ng + ok) // 2
        lc = trans(lef[mid])
        rc = trans(rig[mid])
        # print(a[mid], lc, rc)
        rcs = [0] * (k + 2)
        for i in range(k + 1):
            rcs[i + 1] = rcs[i] + rc[i]
        for i in range(k + 1):
            if lc[i] and rcs[k - i] - rcs[max(k - a[mid] - i, 0)] > 0:
                ng = mid
                break
        else:
            ok = mid
    print(ok + 1)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


def solve():
    n, k = nm()
    a = nl()
    a.sort()

    lef = [1]*n
    rig = [1]*n
    mask = (1 << (k+1)) - 1
    for i in range(n-1):
      lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
      rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask

    ok = -1
    ng = n
    while ng - ok > 1:
      mid = (ng + ok) // 2
      lc = lef[mid]
      rc = rig[mid]
      cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 1)
      for i in range(k):
        if lc & 1 and rc & cov:
          ng = mid
          break
        lc >>= 1
        cov >>= 1
      else:
        ok = mid
    print(ok + 1)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
def trans(v):
  l = [0]*(k+1)
  for i in range(k+1):
    l[i] = (v&1)
    v >>= 1
  return l

a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  lc = trans(lef[mid])
  rc = trans(rig[mid])
  # print(a[mid], lc, rc)
  rcs = [0]*(k+2)
  for i in range(k+1):
    rcs[i+1] = rcs[i] + rc[i]
  for i in range(k+1):
    if lc[i] and rcs[k-i] - rcs[max(k - a[mid] - i, 0)] > 0:
      ng = mid
      break
  else:
    ok = mid
print(ok + 1)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
a = list(map(int,input().split()))
def trans(v):
  l = [0]*(k+1)
  for i in range(k+1):
    l[i] = (v&1)
    v >>= 1
  return l

a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << max(k - a[mid], 0)) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

Submission status: Time Limit Exceeded

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))
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)

Submission status: Time Limit Exceeded

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))
for i in range(N):
    n=1
    for j in range(N):
        if i!=j:
            n=n|n<<a[j]
            n%=(1<<K)
    #print(bin(n))
    if n<((1<<K)>>a[i]):
        ans+=1
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

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()
if f(0):
  print(0)
  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: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    setSums = [{0}]
    setSum = {0}
    for B in Bs:
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSums.append(setSum.copy())
    setSumRevs = [{0}]
    setSum = {0}
    for B in reversed(Bs):
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSumRevs.append(setSum.copy())
    setSumRevs.reverse()

    def isOK(x):
        B = Bs[x]
        numRevs = [0] * K
        for s in setSumRevs[x+1]:
            numRevs[s] = 1
        accNumRevs = list(accumulate([0]+numRevs))
        for s in setSums[x]:
            if accNumRevs[K-s] - accNumRevs[max(0, K-s-B)] > 0:
                return True
        return False

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    def isOK(x):
        isFounds = [False] * K
        isFounds[0] = True
        for i, B in enumerate(Bs):
            if i == x: continue
            for s in reversed(range(K-B)):
                if isFounds[s]:
                    isFounds[s+B] = True
        return any(isFounds[K-Bs[x]:])

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()

Submission status: Time Limit Exceeded

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)

#print(bin(dpm[-1]))
r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
#    print(bin(dpm[N-i-1]))
    tmp = dpm[N-i-1]
    for j in range(1, a):
        tmp |= tmp>>1
#    print(bin(tmp), bin(dp2), len(bin(tmp)))
    if not dp2&tmp:
#        print("aa")
        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: Time Limit Exceeded

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

r = 0
dp2 = 1
for i, a in enumerate(A[::-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))-1
print(r)

Submission status: Time Limit Exceeded

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

r = 0
dp2 = 1
for i, a in enumerate(A[::-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
print(r)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

r = 0
for i, a in enumerate(A[::-1]):
    f = True
    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
        if f and dp2[j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                f = False
        if j-a>=0:
            dp2[j] = dp2[j] + dp2[j-a]
    if f:
        r += 1
#    for j in range(K-1, 0, -1):
#        print("aa", i, N-i-1)
print(r)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

#print(dp)
#print(dpm)
r = 0
for i, a in enumerate(A[::-1]):
    f = False
    for j in range(K-1, 0, -1):
        if j - a >= 0:
            dp2[i+1][j] = dp2[i][j] + dp2[i][j-a]
#    print(i, N-i-1, a)
    for j in range(K-1, -1, -1):
        # 後ろiこの合計がjのもの
#        print("bb", i, j, K-j-a, K-j)
        if dp2[i][j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                break
    else:
        r += 1
#        print("aa", i, N-i-1)
print(r)

#    print(N-i, i+1)
#    if mx[N-i] + a + mx2[i+1] < K: 
#        r += 1

Submission status: Time Limit Exceeded

Solution code:

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

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

ans = [False] * N
able = [False] * (2*K+1)
able[0] = True
lis = [ [False] * N for i in range(2*K+1) ]

for i,na in enumerate(a):

    if na >= K:
        ans[i] = True
        continue

    nable = able.copy()

    for j in range(K):

        if able[j]:

            for nown in range(N):

                if not lis[j+na][nown] and lis[j][nown]:
                    lis[j + na][nown] = True

            lis[j+na][i] = True
            nable[j+na] = True

    able = nable

for i,na in enumerate(a):

    if na < K:

        for j in range(K,K+na,1):

            if lis[j][i]:
                ans[i] = True

#print (able)
r = N
for i in ans:
    if i:
        r -= 1

print (r)

Submission status: Time Limit Exceeded

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*13) - 1
for i in range(N-1):
    X[i+1] = (X[i] | X[i] << 13 * A[i]) & m if A[i] else X[i]
for i in range(1, N)[::-1]:
    Y[i-1] = (Y[i] | Y[i] << 13 * A[i]) & m if A[i] else Y[i]

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

Submission status: Time Limit Exceeded

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*13) - 1
for i in range(N-1):
    X[i+1] = X[i] * ((1<<13*A[i]) + 1 if A[i] else 1) & m
for i in range(1, N)[::-1]:
    Y[i-1] = Y[i] * ((1<<13*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) >> 13 * (K - A[i])) & ((1 << 13 * A[i]) - 1):
        ans -= 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  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
    f = 0
    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
            f = 1
            break
      if f:
        break
    else:
      ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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
  f = 0
  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
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
print(n-ok)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
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):
      dp[i] |= dp[i-w]
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  a.sort(reverse=True)
  hi = -1
  lo = n
  while lo-hi>1:
    mid = (lo+hi)//2
    if a[mid] >= k:
      hi = mid
    else:
      lo = mid
  ng = hi
  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):
        dp[i] |= dp[i-w]
    if any(dp[k-a[mid]:k]):
      ng = mid
    else:
      ok = mid
  print(n-ok)
  return
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
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):
      dp[i] |= dp[i-w]
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 1
  for j in range(n):
    if j == mid:
      f = 0
      continue
    w = a[j]
    new = dp.copy()
    for i in range(k-w+1):
      new[i+w] |= dp[i]
    dp = new
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)

Submission status: Time Limit Exceeded

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, i):
                isNess[j] = True
            break

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp, f = [[False] * K for i in range(N+1)], [[0] * K for i in range(N+1)]
dp[0][0] = f[N][0] = 1
for i, (al, ar) in enumerate(zip(a, a[::-1]), 1):
    for j in range(K):
        if dp[i-1][j]:
            dp[i][j] = 1
            if al+j < K:
                dp[i][al+j] = 1
    for j in range(K):
        if f[-i][j]:
            f[-i-1][j] = 1
            if ar+j < K:
                f[-i-1][ar+j] = 1
for i in range(N):
    for j in range(1, K):
        f[i][j] += f[i][j-1]
cnt = 0
for i, x in enumerate(a):
    if x >= K:
        cnt += 1
        continue
    dpi = dp[i]
    for j in range(K):
        if dpi[j]:
            if K-x-j-1 < 0 or f[i+1][K-j-1]-f[i+1][K-x-j-1] > 0:
                cnt += 1
                break
print(N-cnt)

Submission status: Time Limit Exceeded

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

N, K = map(int, input().split())
a = list(map(int, input().split()))
S, f = [set() for i in range(N+1)], [[0] * K for i in range(N+1)]
S[0].add(0)
f[N][0] = 1
for i, (al, ar) in enumerate(zip(a, a[::-1]), 1):
    for j in S[i-1]:
        S[i].add(j)
        x = al + j
        if x < K:
            S[i].add(x)
    for j in range(K):
        if f[-i][j]:
            f[-i-1][j] = 1
            if ar+j < K:
                f[-i-1][ar+j] = 1
for i in range(N):
    for j in range(1, K):
        f[i][j] += f[i][j-1]
cnt = 0
for i, x in enumerate(a):
    if x >= K:
        cnt += 1
        continue
    for j in S[i]:
        if K-x-j-1 < 0 or f[i+1][K-j-1]-f[i+1][K-x-j-1] > 0:
            cnt += 1
            break
print(N - cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *

N, K = map(int, input().split())
a = list(map(int, input().split()))
S, f = [set() for i in range(N+1)], [[0] * K for i in range(N+1)]
S[0].add(0)
f[N][0] = 1
for i, (al, ar) in enumerate(zip(a, a[::-1]), 1):
    for j in S[i-1]:
        S[i].add(j)
        x = al + j
        if x < K:
            S[i].add(x)
    for j in range(K):
        if f[-i][j]:
            f[-i-1][j] = 1
            if ar+j < K:
                f[-i-1][ar+j] = 1
for i in range(N):
    for j in range(1, K):
        f[i][j] += f[i][j-1]
cnt = 0
for i, x in enumerate(a):
    if x >= K:
        cnt += 1
        continue
    for j in S[i]:
        if K-x-j-1 < 0 or f[i+1][K-j-1]-f[i+1][K-x-j-1] > 0:
            cnt += 1
            break
print(N - cnt)

Submission status: Time Limit Exceeded

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

d = {0: 1}
for i in range(1, K):
    d[i] = 0
for x in a:
    for i in range(K - 1, 0, -1):
        if i >= x:
            d[i] += d[i - x]

alt_sum = [[None for _ in range(K)] for _ in range(K)]
# alt_sum[n][step] = d[n] - d[n - step] + d[n - 2*step] -d[n - 3*step] + ...
for n in range(K):
    for step in range(1, K):
        if n >= step:
            alt_sum[n][step] = d[n] - alt_sum[n - step][step]
        else:
            alt_sum[n][step] = d[n]

need = 0
for x in a:
    if x >= K:
        need += 1
    else:
        for s in range(K - x, K):
            if d[s] > 0:
                if alt_sum[s][x] > 0:
                    need += 1
                    break
no_need = N - need
print(no_need)

Submission status: Time Limit Exceeded

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

d = {0: 1}
for i in range(1, K):
    d[i] = 0
for x in a:
    for i in range(K - 1, 0, -1):
        if i >= x:
            d[i] += d[i - x]

need = 0
for x in a:
    if x >= K:
        need += 1
    else:
        for s in range(K - x, K):
            if d[s] > 0:
                alt_sum = 0
                i = s
                sign = 1
                while i >= 0:
                    alt_sum += sign * d[i]
                    i -= x
                    sign *= -1
                if alt_sum > 0:
                    need += 1
                    break
no_need = N - need
print(no_need)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, k = map(int, input().split())
  alist = list(sorted(map(int, input().split())))
  l, r = 0, n
  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:
          tmp_dp[_k] = dp[_k] or dp[_k-a]
      dp = tmp_dp
    is_need = False
    for _k in range(max(0, k-alist[mid]), k):
      if dp[_k]:
        is_need = True
        break
    if is_need:
      r = mid
    else:
      l = mid + 1

  print(r)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

  print(r)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

n, k = map(int, input().split())
alist = list(sorted(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]
  is_need = False
  for _k in range(max(0, k-alist[mid]), k):
    if dp[_k][-1]:
      is_need = True
      break
  if is_need:
    r = mid
  else:
    l = mid + 1

print(r)

Submission status: Time Limit Exceeded

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    
    for i in range(n):
        if i == mid:
            continue
        for j in range(k)[::-1]:
            if j - a[i] < 0:
                break
            else:
                dp[j] |= dp[j - 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: Time Limit Exceeded

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

def subset_sum(mid):
    if a[mid] > k:
        return False

    li = a[0:mid] + a[mid+1:]
    n = len(li)
    dp = [False]*(k + 1)
    dp[0] = True    
    for i in range(n):
        for j in range(k+1)[::-1]:
            if j - li[i] < 0:
                break
            else:
                dp[j] = dp[j] or 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: Time Limit Exceeded

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

dp = [[0]*(k + 1) for i in range(n + 1)]
dp[0][0] = 1

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] + dp[i][j - a[i]]
dp = dp[n]

ans = 0
for i in range(n):
    tmp = dp[0:]
    if a[i] > k:
        continue
    for j in range(a[i], k + 1):
        tmp[j] = dp[j] - tmp[j - a[i]]
    if max(tmp[k-a[i]:k]) <= 0:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


def calc(x):
    if A[x] >= K:
        return True
    dp = [False] * K
    dp[0] = True
    ma = 0
    for i in range(N):
        if i == x:
            continue
        for k in range(ma, -1, -1):
            if k + A[i] >= K:
                continue
            dp[k + A[i]] |= dp[k]
        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


l, r = 0, N - 1
if not calc(N - 1):
    print(N)
    exit()
if calc(0):
    print(0)
    exit()
while r - l > 1:
    mi = (l + r) // 2
    if calc(mi):
        r = mi
    else:
        l = mi

print(r)

Submission status: Time Limit Exceeded

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

As.sort(reverse=True)

minAOK = As[0]+1
sumSubsets = set([0])
for A in As:
    if A >= K:
        minAOK = A
        continue
    for sumSubset in sumSubsets.copy():
        if K - A <= sumSubset:
            minAOK = A
        if sumSubset + A < K:
            sumSubsets.add(sumSubset + A)

ans = len([A for A in As if A < minAOK])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=0
for k in range(K):
  mask|=1<<k
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if len(bin(dp[x]<<a[x]))-2>=K+1:
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=0
for k in range(K):
  mask|=1<<k
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if (dp[x]<<a[x])&(~mask):
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
mask=(1<<(K))-1
a.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(N):
  dp[i+1]=(dp[i]|(dp[i]<<a[i]))&mask

def solve(x):
  if (dp[x]<<a[x])>=1<<K:
    return True
  else:
    return False
  
for i in range(-1,N)[::-1]:
  if solve(i):
    break
    
print(N-i-1)