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:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    while abs(ok - ng) > 1:
        j = (ok + ng) // 2
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [[False]*K for _ in range(N-1)]
        DP[0][A[0]] = True
        for i in range(1, N-1):
            DP[i][:] = DP[i-1]
            for k in range(K):
                if k + A[i] < K:
                    DP[i][k+A[i]] = DP[i-1][k]
        if any(DP[-1][max(K-a[j], 0):]):
            ok = j
        else:
            ng = j
    print(ok)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    while abs(ok - ng) > 1:
        j = (ok + ng) // 2
        A = a[:j]+a[j+1:]
        # print(A)
        DP = [False]*K
        DP[A[0]] = True
        for i in range(1, N-1):
            for k in range(K-1, -1, -1):
                if k + A[i] < K:
                    DP[k+A[i]] = DP[k]
        if any(DP[max(K-a[j], 0):]):
            ok = j
        else:
            ng = j
    print(ok)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort()

    if a[0] >= K:
        print(0)
        return

    a = [x for x in a if x < K]
    N = len(a)

    ng = -1
    ok = N
    DP0 = [False]*K
    DP = DP0[:]
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        A = a[:mid]+a[mid+1:]
        DP[:] = DP0
        DP[A[0]] = True
        for i in range(1, N-1):
            for k in range(K-A[i]-1, -1, -1):
                DP[k+A[i]] = DP[k]
        if any(DP[max(K-a[mid], 0):]):
            ok = mid
        else:
            ng = mid
    print(ok)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, K: int, a: "List[int]"):
    a.sort(reverse=True)
    tot = 0
    curr = 0
    for i, aa in enumerate(a):
        tot += aa
        if tot >= K:
            tot = 0
            curr = i+1
    print(N-curr)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
A = []
ans = 0
for a in _A:
    if a >= K:  # 一つで良い集合
        ans += 1
    else:
        A.append(a)

M = len(A)
A.sort(reverse=True)
confilm = [0 for _ in range(N)]

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

left = 0
right = 1
while right < M:
    while sumA[right] - sumA[left] >= K:
        left += 1
    for check in range(right, M):
        if (sumA[right] - sumA[left]) + A[check] >= K:
            confilm[check] = 1
            confilm[left] = 1
    right += 1

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left
input = sys.stdin.readline

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
a = a[:bisect_left(a,K)]
N = len(a)

def judge(n) :
    dp = [0] * K
    dp[0] = 1
    for i in range(N) :
        if i == n : continue
        dp_ = [0] * K
        for j in range(K) :
            if not dp[j] :
                continue
            if j + a[i] >= K :
                break
            if K - a[n] <= j + a[i] :
                return True
            dp_[j+a[i]] = 1
        dp = dp_
    return False

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

Submission status: Wrong Answer

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

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()

# print(a)
def judge(n) :
    dp = set([0])
    for i in range(N) :
        if i == n : continue
        dp_ = set()
        for j in dp :
            if K-a[n] <= j+a[i] < K :
                return True
            dp_.add(j+a[i])
        dp = dp | dp_
        # print(dp_, dp)
    return False

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

def judge(n) :
    dp = set([0])
    for i in range(n) :            
        dp_ = set()
        for j in dp :
            if K-a[n] <= j+a[i] < K :
                return True
            dp_.add(j+a[i])
        dp = dp | dp_
    return False

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

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

def judge(n) :
    dp = set([0])
    for i in range(N) :
        if i == n :
            continue
            
        dp_ = set()
        for j in dp :
            if j+a[i]<K and j+a[i]+a[n]>=K :
                return True
            dp_.add(j+a[i])
        dp = dp | dp_
    return False

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

Submission status: Wrong Answer

Solution code:
MAX_INT = int(10e10)

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards += [MAX_INT]

left = 0
right = N+1
while right - left > 1:
  middle = (left+right)//2
  dp = [[0]*K for i in range(N+2)]
  for i in range(1,N+1):
    for j in range(K):
      if i == middle:
        dp[i+1][j] = dp[i][j]
      else:
        if cards[i] <= j:
          dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
        else:
          dp[i+1][j] = dp[i][j]
  if K-cards[middle] <= dp[-1][-1]:
    right = middle
  else:
    left = middle
print(right)

Submission status: Wrong Answer

Solution code:
MAX_INT = int(10e10)
MIN_INT = -MAX_INT

def judge(x):
  dp = [[0]*K for i in range(N+1)]
  for i in range(N):
    for j in range(K):
      if i == x:
        dp[i+1][j] = dp[i][j]
      else:
        if cards[i] <= j:
          dp[i+1][j] = max(dp[i][j],dp[i][j-cards[i]]+cards[i])
        else:
          dp[i+1][j] = dp[i][j]
  if K-cards[x] <= dp[-1][-1]:
    return True
  else:
    return False

def nibutan():
  left = 0
  right = N
  middle = (left+right)//2
  while right - left != 1:
    if judge(middle) == True:
      right = middle
    else:
      left = middle
    middle = (left+right)//2
  return right

N,K = list(map(int,input().split()))
cards = list(map(int,input().split()))
cards.sort()
cards = cards + [MAX_INT]
print(nibutan())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*(k_+1)
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma,k_-ai)+1)[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_ < k:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k_
    dp[0] = 1
    ma = 0
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma,k_-ai)+1)[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_ < k:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_left(a,k)]
n = len(a)
a = a[::-1]
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = [0]*k
    dp[0] = 1
    ma = 1
    for i in range(n):
        if i == m:continue
        ai = a[i]
        for j in range(min(ma,k-ai))[::-1]:
            j_ = j+ai
            if dp[j]:
                if k_ <= j_:
                    l = m
                    break
                dp[j_] = 1
                if j_ > ma:
                    ma = j_
        else:
            continue
        break
    else:
        r = m
print(n-r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
a = a[:bisect.bisect_right(a,k)]
n = len(a)
l = -1
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = defaultdict(int)
    dp[0] = 1
    for i in range(n):
        if i == m:continue
        ai = a[i]
        d = list(dp.keys())
        for j in d:
            dp[j+ai] = 1
            if k_ <= j+ai < k:
                r = m
                break
        else:
            continue
        break
    else:
        l = m
print(r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


#A
"""
a,b = LS()
if a == b:
    print("H")
else:
    print("D")
"""

#B
"""
w,a,b = LI()
print(max(max(a,b)-min(a,b)-w,0))
"""

#C
"""

x = I()
a = 0
i = 1
while a < x:
    a += i
    i += 1
print(i-1)
"""

#D
n,k = LI()
a = LI()
a.sort()
l = 0
r = n
while r-l > 1:
    m = (l+r)//2
    k_ = k-a[m]
    dp = defaultdict(int)
    dp[0] = 1
    for i in range(n):
        if i == m:continue
        ai = a[i]
        d = list(dp.keys())
        for j in d:
            dp[j+ai] = 1
            if k_ <= j+ai < k:
                r = m
                break
        else:
            continue
        break
    else:
        l = m
print(r)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T

Submission status: Wrong Answer

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

L = [0] * N
L[0] = a[0]
for i in range(1, N):
  L[i] = L[i - 1] + a[i]

ans = 0
for i in range(N):
  x = a[i]
  l = 0
  r = i + 1
  t = L[i]
  f = 1
  while l <= i:
    if t >= K:
      if l != i and t - a[l] >= K:
        t -= a[l]
        l += 1
        continue
      if t - x < K:
        f = 0
        break
      t -= a[l]
      l += 1
    else:
      if r == N:
        break
      t += a[r]
      r += 1
  ans += f

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	i = 0
	sum_few = A[0]
	while sum_few < K and i < N-1:
		i += 1
		sum_few += A[i]
	j = i
	if sum_few >= K:
		next_sum = A[j]
		while next_sum < K and j >= 0:
			j -= 1
			next_sum += A[j]
		j -= 1

	print(j+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	i = 0
	sum_few = A[0]
	while sum_few < K and i < N-1:
		i += 1
		sum_few += A[i]
	j = i
	if sum_few >= K:
		next_sum = A[j]
		while next_sum < K and j >= 0:
			j -= 1
			next_sum += A[j]
		if j > 0:
			j -= 1

	print(j+1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

if __name__ == "__main__":
	N, K = stdin.readline().split(" ")
	N = int(N)
	K = int(K)
	
	a = []
	line = stdin.readline().split(" ")
	for e in line:
		a.append(int(e)) 

	total_sum = sum(a)
	if total_sum < K:
		print (N)
	else:
		a.sort()
		current_sum = 0
		min_length = N+1 # min elements of subarray that sum to K
		start = end = 0

		while end < N:
			flag1 = False
			flag2 = False
			while (current_sum < K and end < N):
				flag1 = True
				current_sum += a[end]
				end += 1
				# print ("add ", a[end-1], current_sum)

			while (current_sum > K and start < N):
				flag2 = True
				if end - start < min_length:
					min_length = end - start
				
				if current_sum - a[start] >= K:
					current_sum -= a[start]
					start += 1
					# print ("remove ", a[start-1], current_sum)
				else:
					break

			if not flag1 and not flag2:
				break
				
		print (N-min_length)

Submission status: Wrong Answer

Solution code:
from sys import stdin

if __name__ == "__main__":
	N, K = stdin.readline().split(" ")
	N = int(N)
	K = int(K)
	
	a = []
	line = stdin.readline().split(" ")
	for e in line:
		a.append(int(e)) 

	total_sum = sum(a)
	if total_sum < K:
		print (N)
	else:
		print (1)

Submission status: Wrong Answer

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

dp1 = [[False for _ in range(k)] for _ in range(n+1)]
dp1[0][0] = True

for i in range(n):
    for j in range(k):
        x = xs[i]
        dp1[i+1][j] = dp1[i][j] or ((j - x >= 0) and dp1[i][j-x])


dp2 = [[False for _ in range(k)] for _ in range(n+1)]
dp2[n][0] = True
for i in range(n-1, -1, -1):
    for j in range(k):
        x = xs[i]
        dp2[i][j] = dp2[i+1][j] or ((j - x >= 0) and dp2[i+1][j-x])


c = 0
for i in range(n):
    x = xs[i]
    dpl = dp1[i+1]
    dpr = dp2[i]
    dpi = [False for _ in range(k)]
    for il, tl in enumerate(dpl):
        for ir, tr in enumerate(dpr):
            if il + ir < k and (tl and tr):
                dpi[il+ir] = True

    if not all(dpi[-x:]):
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
x = [0]
for ai in a:
    x.append(x[-1] + ai)

ii = 0
for i in range(n):
    for j in range(ii, n):
        if x[j + 1] - x[i] >= k:
            ii = j + 1
            break
print(max(0, n - ii))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
dp = [[0 for x in range(k+1)]for i in range(n+1)]
dp[0][0] = 1
dp_back = [[0 for x in range(k+1)]for i in range(n+1)]
dp_back[0][0] = 1
for x in range(1,n+1):
    for y in range(k+1):
        z = y-a[x-1]
        if dp[x-1][y] or (z>=0 and dp[x-1][z]):
            dp[x][y] = 1
        z = y-a[-x]
        if dp_back[x-1][y] or (z>=0 and dp_back[x-1][z]):
            dp_back[x][y] = 1
for i in range(n):
    x = a[i]
    for y, left in enumerate(dp[i]):
        for z, right in enumerate(dp_back[i-n-1]):
            if left & right & (k-x <= (y+z) < k):
                print(i)
                exit()
print(n)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
dp = [[0 for x in range(k+1)]for i in range(n+1)]
dp[0][0] = 1
for x in range(1,n+1):
    for y in range(k+1):
        z = y-a[x-1]
        if dp[x-1][y] or (z>=0 and dp[x-1][z]):
            dp[x][y] = 1

dp_back = [[0 for x in range(k+1)]for i in range(n+1)]
dp_back[0][0] = 1
for x in range(1,n+1):
    for y in range(k+1):
        z = y-a[-x]
        if dp_back[x-1][y] or (z>=0 and dp_back[x-1][z]):
            dp_back[x][y] = 1
for i in range(n):
    x = a[i]
    for y, left in enumerate(dp[i]):
        for z, right in enumerate(dp_back[i-n]):
            if left & right & (k-x <= (y+z) < k):
                print(i)
                exit()
print(n)

Submission status: Wrong Answer

Solution code:
n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)
if n > 400 or k > 400:
    exit()

sum_possibility = [0] * 801
sum_possibility[0] = 1

for i in range(n+1):
    if not 1 in sum_possibility[max(0, k-sum(a[i:])):k]:
        break
    for j in range(800, -1, -1):
        if sum_possibility[j] is not 0 and j + a[i] < 801:
            sum_possibility[j + a[i]] = 1
print(n-i)

Submission status: Wrong Answer

Solution code:
n, k = [int(item) for item in input().split()]
a = sorted([int(item) for item in input().split()], reverse=True)

sum_possibility = [0] * 10001
sum_possibility[0] = 1

for i in range(n):
    if not 1 in sum_possibility[max(0, k-sum(a[i:])):k]:
        break
    for j in range(10000, -1, -1):
        if sum_possibility[j] is not 0 and j + a[i] < 10001:
            sum_possibility[j + a[i]] = 1
print(n-i)

Submission status: Wrong Answer

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    def need(i: int)->bool:
        dp = [[False] * (K) for _ in range(N)]
        dp[0][0] = True

        card_num = 0
        for n, a in enumerate(A):
            if n == i:
                break
            for k in range(K):
                dp[card_num + 1][k] = \
                    dp[card_num][k] or (a <= k and dp[card_num][k - a])
            card_num += 1

        return any(dp[N - 1][max(K - A[i], 0):])

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    A.sort()

    def need(i: int)->bool:
        dp = [[False] * (K) for _ in range(N)]
        dp[0][0] = True

        card_num = 0
        for n, a in enumerate(A):
            if n == i:
                break
            for k in range(K):
                dp[card_num + 1][k] = \
                    dp[card_num][k] or (a <= k and dp[card_num][k - a])
            card_num += 1

        return any(dp[N - 1][max(K - A[i], 0):])

    l, r = -1, N
    while l + 1 < r:
        m = (l + r) // 2
        if need(m):
            r = m
        else:
            l = m

    return l+1


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    count = 0
    for i in range(N):
        dp = [[False] * (K + 1) for _ in range(N)]
        dp[0][0] = True

        for n, a in enumerate(A[:i] + A[i+1:]):
            for k in range(K + 1):
                dp[n+1][k] = dp[n][k]
                if a <= k:
                    dp[n+1][k] |= dp[n][k - a]

        if not any(dp[N-1][max(K - A[i], 0):]):
            count += 1

    return count


if __name__ == "__main__":
    N, K = map(int, input().split())
    A = [int(s) for s in input().split()]
    ans = no_need(N, K, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
dp=[set()]*(K+1)
for i in range(N):
    dpc=dp.copy()
    a=A[i]
    for k in range(K+1):
        if k+a>K:break
        if len(dpc[k])!=0 or k==0:
            dp[k+a]=dpc[k]|{i,}
cnt=0
for i in range(N):
    a=A[i]
    if a>=K:
        cnt+=1
        continue
    for j in range(K-a,K):
        if i not in dp[j] and len(dp[j])!=0:
            cnt+=1
            break
print(N-cnt)

Submission status: Wrong Answer

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

a.sort()

x = [set()] * n
y = [set()] * n

x[0].add(0)
x[0].add(a[0])
y[n-1].add(0)
y[n-1].add(a[n-1])

for i in range(1, n-1):
    temp = set()
    for t in x[i-1]:
        temp.add(t + a[i])
    x[i] = temp | x[i-1]
    temp = set()
    for t in y[n-i]:
        temp.add(t + a[n-1-i])
    y[n-1-i] = temp | y[n-i]

#print(x)
#print(y)

ans = n

if a[0] >= k:
    print(0)
    exit()
for t in y[1]:
    if k - a[0] <= t < k:
        ans -= 1
        break

if a[n-1] >= k:
    ans -= 1
else:
    for t in x[n-2]:
        if k - a[n-1] <= t < k:
            ans -= 1
            break

for i in range(1, n-1):
    if a[i] >= k:
        ans -= n-i
        break
    #print(a[i], x[i-1], y[i+1])
    for b in x[i-1]:
        for c in y[i+1]:
            if k - a[i] <= b + c < k:
                ans -= 1
                #print(k, a[i], b, c)
                break
        else:
            continue
        break

print(ans)

Submission status: Wrong Answer

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    dp = [[0 for _ in range(k)] for _ in range(n)]
    dp[0][0] = 1
    t = 1
    check = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k - a[i]):
            if dp[t - 1][j] == 1:
                dp[t][j] = 1
                temp = j + a[i]
                if k - a[m] <= temp < k:
                    check = 1
                    break
                elif temp < k - a[m]:
                    dp[t][temp] = 1
        if check == 1:
            break
        t += 1
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Wrong Answer

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    dp = [[0 for _ in range(k)] for _ in range(n)]
    dp[0][0] = 1
    t = 1
    check = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k):
            if dp[t - 1][j] == 1:
                dp[t][j] = 1
                temp = j + a[i]
                if k - a[m] <= temp < k:
                    check = 1
                    break
                elif temp < k - a[m]:
                    dp[t][temp] = 1
        if check == 1:
            break
        t += 1
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Wrong Answer

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    dp = [[0 for _ in range(k)] for _ in range(n)]
    dp[0][0] = 1
    t = 1
    check = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k):
            if dp[t - 1][j] == 1:
                temp = j + a[i]
                if k - a[m] <= temp < k:
                    check = 1
                    break
                elif temp < k - a[m]:
                    dp[t][temp] = 1
        if check == 1:
            break
        t += 1
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

Submission status: Wrong Answer

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

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

ans = n

for c in range(n):
    s = set()
    s.add(0)
    for i in range(n):
        if i == c:
            continue
        next = set()
        check = 0
        for x in s:
            if k - a[c] <= x + a[i] < k:
                check = 1
                break
            elif x + a[i] < k - a[c]:
                next.add(x + a[i])
        if check == 1:
            ans -= 1
            break
        s = s | next

print(ans)

Submission status: Wrong Answer

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

a.sort()

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

ans = n

for c in range(n):
    res = 10 ** 10
    s = set()
    s.add(0)
    for i in range(n):
        if i == c:
            continue
        next = set()
        check = 0
        for x in s:
            if k - a[c] <= x + a[i] < k:
                check = 1
                break
            elif x < k - a[c]:
                next.add(x + a[i])
        if check == 1:
            ans -= 1
            break
        s = s | next

print(ans)

Submission status: Wrong Answer

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

a.sort()

if a[0] >= k:
    print(0)
    exit()

m = 0
s = [0 for _ in range(n)]
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    if s[i] >= k:
        m = i
        break

if m == 0:
    print(n)
    exit()

u = s[m] - k
for i in range(1, m + 1):
    if a[i] > u:
        print(i)
        exit()

Submission status: Wrong Answer

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

a.sort()

if a[0] >= k:
    print(0)
    exit()

m = 0
s = [0 for _ in range(n)]
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    if s[i] >= k:
        m = i
        break

if m == 0:
    print(n)
    exit()

u = s[m] - k
for i in range(1, m + 1):
    if s[i] > k:
        print(i - 1)
        exit()