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())
List  = list(map(int,input().split()))
upper = sum(List)
if upper < K:
  print(N)
  exit()
List = sorted(List)
counter = 0
for item in List:
  if item <= upper - K:
    counter +=1
  else:
    print(counter)
    exit()
print(counter)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
List  = list(map(int,input().split()))
upper = sum(set(List))
if upper < K:
  print(N)
  exit()
List = sorted(list(set(List)))
counter = 0
for item in List:
  if item <= upper - K:
    counter +=1
  else:
    print(counter)
    exit()
print(counter)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
for i in a:
	if i >= (k-i):
		cnt += 1
print (n-cnt)

Submission status: Wrong Answer

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    # print("N", N, "K", K)
    # print(Ai)

    return N, K, Ai


def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)

    lis = []
    buf = Ai[0]
    for i in range(1, N):
        lis.append(buf)
        buf += Ai[i]
    lis.append(buf)

    # print(lis)

    c = 0
    head = 0
    for i in range(0, N):
        if K <= lis[i]:
            for j in range(head, i + 1):
                if Ai[j] < K and lis[i] - Ai[j] >= K:
                    head += 1
                    c += 1
                else:
                    return c


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Wrong Answer

Solution code:
def args():
    N, K = tuple(map(int, input().split()))
    Ai = tuple(map(int, input().split()))

    # print("N", N, "K", K)
    # print(Ai)

    return N, K, Ai


def solve(N, K, Ai):
    sum_a = sum(Ai)
    if sum_a < K:
        return N

    Ai = sorted(Ai)

    lis = []
    buf = Ai[0]
    for i in range(1, N):
        lis.append(buf)
        buf += Ai[i]
    lis.append(buf)

    # print(lis)

    c = 0
    head = 0
    for i in range(0, N):
        if K <= lis[i]:
            for j in range(head, i + 1):
                if Ai[j] < K and lis[i] - Ai[j] > K:
                    head += 1
                    c += 1
                else:
                    return c


if __name__ == '__main__':
    res = solve(*args())
    print(res)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()

def check(d):#そいつが必要か
    global a,n,k
    x=a[d]
    dp=[0]*(k)#k-1まで
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]

def check(d):#そいつが必要か
    global a,n,k
    x=a[d]
    dp=[0]*(k)#k-1まで
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d-1
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]

def check(d):#そいつが必要か
    global a,n,k
    x=a[d]
    dp=[0]*(k)#k-1まで
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
                    else:
                        break
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]

def check(d):#そいつが必要か
    global a,n,k
    x=a[d]
    dp=[0]*(k)#k-1まで
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
                    if j+a[d]>=k:
                        return True
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
a=[int(i) for i in input().split()]

def check(d):#そいつが必要か
    global a,n,k
    x=a[d]
    dp=[0]*(k)#k-1まで
    for i in range(n):
        if i!=d:
            dp_sub=[0]*(k)
            for j in range(k-1):
                if j==0 or dp[j]!=0:
                    if j+a[i]<k:
                        dp_sub[j+a[i]]=1
            for j in range(k):
                if dp_sub[j]==1:
                    dp[j]=1
    z=-1
    for i in range(k-1,-1,-1):
        if dp[i]==1:
            return (i+a[d]>=k)
    return False
l,r=0,n-1
while l+1<r:
    d=(l+r)//2
    if check(d):#必要か
        r=d
    else:
        l=d
if check(l):
    print(l)
else:
    if check(r):
        print(r)
    else:
        print(r+1)

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
nn = len(fa)
if sum(a)<k:
    print(n)
elif nn==0:
    print(0)
else:
    fa.reverse()
    res = 0
    for i in range(nn):
        flag = 0
        ta = fa[i]
        na = fa[:i]+fa[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(nn-1):
            for l in range(k,0,-1):
                if l-na[j]>=0:
                    dp[l]=dp[l] or dp[l-na[j]]
        for j in range(k-ta,k):
            if dp[j]:
                flag = 1
                break
        if flag == 0:
            res = i
            break
    print(nn-res)

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
nn = len(fa)
if sum(a)<k:
    print(n)
elif nn==0:
    print(0)
else:
    fa.reverse()
    res = 0
    for i in range(nn):
        flag = 0
        ta = fa[i]
        na = fa[:i]+fa[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(nn-1):
            for l in range(k,0,-1):
                if l-na[j]>=0:
                    dp[l]=dp[l] or dp[l-na[j]]
        for j in range(k-ta,k):
            if dp[j]:
                flag = 1
                break
        if flag == 0:
            res = i
            break
    print(nn-i)

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
nn = len(fa)
if sum(a)<k:
    print(n)
elif nn==0:
    print(0)
else:
    fa.reverse()
    for i in range(nn):
        flag = 0
        ta = fa[i]
        na = fa[:i]+fa[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(nn-1):
            for l in range(k,0,-1):
                if l-na[j]>=0:
                    dp[l]=dp[l] or dp[l-na[j]]
        for j in range(k-ta,k):
            if dp[j]:
                flag = 1
                break
        if flag == 0:
            res = i
            break
    print(nn-i)

Submission status: Wrong Answer

Solution code:
import bisect
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
fa = a[:bisect.bisect_left(a,k)]
nn = len(fa)
if nn==0:
    print(0)
else:
    fa.reverse()
    for i in range(nn):
        flag = 0
        ta = fa[i]
        na = fa[:i]+fa[i+1:]
        dp = [False for _ in range(k+1)]
        dp[0]=True
        for j in range(nn-1):
            for l in range(k,0,-1):
                if l-na[j]>=0:
                    dp[l]=dp[l] or dp[l-na[j]]
        for j in range(k-ta,k):
            if dp[j]:
                flag = 1
                break
        if flag == 0:
            res = i
            break
    print(nn-i)

Submission status: Wrong Answer

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

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

l_minus = [i for i in a if i < K]

l_minus.sort()
#print(l_minus)

if l_minus != []:
    for i in range(len(l_minus)):
        if sum(l_minus[i:]) < K:
            if i!=0:
                print(i-1)
            else:
                print(len(l_minus))
            break
else:
    print(0)

Submission status: Wrong Answer

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

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

l_minus = [i for i in a if i < K]

l_minus.sort()
#print(l_minus)

if l_minus != []:
    for i in range(len(l_minus)):
        if sum(l_minus[i:]) < K:
            if i!=0:
                print(i-1)
            else:
                print(N)
            break
else:
    print(0)

Submission status: Wrong Answer

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

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

l_minus = [i for i in a if i < K]

l_minus.sort()
#print(l_minus)

for i in range(len(l_minus)):
    if sum(l_minus[i:]) < K:
        if i!=0:
            print(i-1)
        else:
            print(N)
        break

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(2)]
    dp[0][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[(i+1)%2][j] = dp[i%2][j]
                continue
            dp[(i+1)%2][j] = dp[i%2][j] | dp[i%2][j-L[i]]
        
    res = False
    for j in range(K-A[n], K):
        if dp[N%2][j]:
            res = True
            break
            
    return res

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

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

A.sort()

def f(n): #aiが必要か不必要か判定
    if A[n] >= K:
        return True
    if n == 0:
        L = A[n+1:]
    elif n == N-1:
        L = A[:n]
    else:
        L = A[:n] + A[n+1:]
    
    dp = [[False]*K for _ in range(N)]
    for i in range(N):
        dp[i][0] = True
    for i in range(N-1):
        for j in range(K):
            if j < L[i]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j] | dp[i][j-L[i]]
                
    res = False
    for j in range(K-A[n], K):
        if dp[-1][j]:
            res = True
            break
            
    return res

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    if a[i] >= k:
        return True
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= (res << j)
        res &= mask
    return res >> (k - a[i]) 

def main():
    lo = 0
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i
    
    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    if a[i] >= k:
        return True
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 

def main():
    lo = 0
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i
    
    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    if a[i] >= k:
        return True
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 

def main():
    lo = 0
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i
    
    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
def cumsum(List):
    n = len(List)
    res = [0]*(n+1)
    for i in range(n):
        res[i]=res[i-1]+List[i]
    return res

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
a.reverse()
for i in range(N):
    x = dp1[i-1]
    y = dp2[(i+2)%(N+1)]
    sy = cumsum(y)
    for j in range(K+1):
        if x[j]:
            if sy[K-1]-sy[K-a[i]-1]:
                ans+=1
                break
print(N-ans)

Submission status: Wrong Answer

Solution code:
def cumsum(List):
    n = len(List)
    res = [0]*(n+1)
    for i in range(n):
        res[i]=res[i-1]+List[i]
    return res

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
for i in range(N):
    x = dp1[i-1]
    y = dp2[(i+2)%(N+1)]
    sy = cumsum(y)
    for j in range(K+1):
        if x[j]:
            if sy[K-1]-sy[K-a[i]-1]:
                ans+=1
                break
print(N-ans)

Submission status: Wrong Answer

Solution code:
def cumsum(List):
    n = len(List)
    res = [0]*(n+1)
    for i in range(n):
        res[i]=res[i-1]+List[i]
    return res

N, K = map(int, input().split())
a = list(map(int, input().split()))
a = [i for i in a if i<=K]
N = len(a)
dp1 = [[0]*(K+1) for _ in range(N+1)]
dp2 = [[0]*(K+1) for _ in range(N+1)]
dp1[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp1[i+1][j+a[i+1]]|=dp1[i][j]
        dp1[i+1][j]|=dp1[i][j]
a.reverse()
dp2[-1][0] = 1
for i in range(-1, N-1):
    for j in range(K):
        if j+a[i+1]<=K:
            dp2[i+1][j+a[i+1]]|=dp2[i][j]
        dp2[i+1][j]|=dp2[i][j]
dp2.reverse()
ans = 0
for i in range(N):
    x = dp1[i-1]
    y = dp2[(i+2)%(N+1)]
    sy = cumsum(y)
    for j in range(K+1):
        if x[j]:
            if sy[K]-sy[K-a[i]]:
                ans+=1
                break
print(N-ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c=0
x=0
if sum(a)<k:
  c=n
else:
  for i in range(n):
    x=x+a[i]
    if x>=k:
      break
  for j in range(i):
    j_1=j-1
    x=x-a[j]
    if x>=k:
      c=c+1
    elif a[j] == a[j_1]:
      c=c+a.count(a[j])-1
    else:
      break
print(c)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c=0
x=0
if sum(a)<k:
  c=n
else:
  for i in range(n):
    x=x+a[i]
    if x>=k:
      break
  for j in range(i):
    x=x-a[j]
    if x>=k:
      c=c+1
    else:
      break
print(c)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()

#必要ないならTrueを返す
def test(i):
    b=itertools.chain(a[:i],a[i+1:])
    dp=[False]*k
    dp[0]=True
    for u in b:
        dp[u:]=np.logical_or(dp[u:],dp[:-u])
    return not any(dp[-a[i]:])
    

low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if test(mid):
        low=mid
    else:
        high=mid
    
if test(high):
    print(high+1)
else:
    print(high)

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = LI(); A.sort()
    cur = int(0)
    """ 部分点
        for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if K-A[i]>=0:
            #Kがちっちゃい時注意
            if sum(dp[-1][K - A[i]:K]) == 0:
                cur += 1
        else:
            if sum(dp[-1][:K]) == 0:
                cur += 1
    print(cur)
    """
    cur = int(0)
    ilower = 0; iupper = N-1; ic = (ilower+iupper)//2
    while(True):
        a = A[0:ic] + A[ic+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if iupper - ilower >= 2:
            if K - A[ic] >= 0:
                if sum(dp[-1][max(0, K - A[ic]):K])==0:
                    ilower = ic
                    ic = (ic + iupper) // 2
                else:
                    iupper = ic
                    ic = (ic + ilower) // 2
            else:
                ilower = ic
                ic = (ic + iupper) // 2
        else:
            if sum(dp[-1][K - A[ic]:K])==0:
                ic = iupper
                a = A[0:ic] + A[ic + 1:]
                dp = [[0] * (K + 1) for _ in range(N)]
                dp[0][0] = 1
                for j in range(N - 1):
                    for k in range(K + 1):
                        dp[j + 1][k] = max(dp[j][k], dp[j + 1][k])
                        if k - a[j] >= 0:
                            dp[j + 1][k] = max(dp[j + 1][k], dp[j][k - a[j]])
                if sum(dp[-1][max(0, K - A[ic]):K]) == 0:
                    cur = iupper
                else:
                    cur = ilower
            else:
                ic = ilower
                a = A[0:ic] + A[ic + 1:]
                dp = [[0] * (K + 1) for _ in range(N)]
                dp[0][0] = 1
                for j in range(N - 1):
                    for k in range(K + 1):
                        dp[j + 1][k] = max(dp[j][k], dp[j + 1][k])
                        if k - a[j] >= 0:
                            dp[j + 1][k] = max(dp[j + 1][k], dp[j][k - a[j]])
                if sum(dp[-1][max(0, K - A[ic]):K]) == 0:
                    cur = ilower
                else: cur = -1
            break
#    print(cur)
    if cur==-1:
        ans = 0
    else:
        ans = bisect.bisect(A,A[cur])
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = LI()
    dp = [[0]*(N+1) for _ in range(K+1)]
    cur = int(0)
    for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if sum(dp[-1][K-A[i]:K])==0:
            cur +=1
    print(cur)



import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = LI(); A.sort()
    dp = [[0]*(N+1) for _ in range(K+1)]
    cur = int(0)
    for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
#        print(dp)
        if sum(dp[N-1][K-A[i]:K])==0:
            cur +=1
    print(cur)



import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
def examD():
    N, K = LI()
    A = LI(); A.sort()
    dp = [[0]*(N+1) for _ in range(K+1)]
    cur = int(0)
    for i in range(N):
        a = A[0:i] + A[i+1:]
        dp = [[0] * (K + 1) for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N-1):
            for k in range(K+1):
                dp[j+1][k] = max(dp[j][k],dp[j+1][k])
                if k-a[j]>=0:
                    dp[j+1][k] = max(dp[j+1][k],dp[j][k-a[j]])
        print(dp)
        if sum(dp[N-1][K-A[i]:K])==0:
            cur +=1
    print(cur)



import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
A=[int(x) for x in input().split()]
A.sort()
result=N
for i in range(N):
  for j in range(i+1):
     if sum(A[j:i+1])>=X and sum(A[j+1:i+1])<X:
        result = min(result,j)
print(result)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
A=[int(x) for x in input().split()]
A.sort()
result=N
for i in range(N):
  for j in range(i):
     if sum(A[j:i+1])>=X and sum(A[j+1:i+1])<X:
        c=j
        if A[j]==A[j+1]:
          for k in range(j):
            if A[j] != A[j-k]:
              c=j-k          
        result = min(result,c)
print(result)

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
A=[int(x) for x in input().split()]
A.sort()
result=N
for i in range(N):
  for j in range(i):
     if sum(A[j:i+1])>=X and sum(A[j+1:i+1])<X:
        result = min(result,j)
print(result)

Submission status: Wrong Answer

Solution code:
def check(m):
    DP = [False]*(k+1)
    DP[0] = True
    for i in range(n):
        if i == m:
            continue
        for j in reversed(range(k+1-a[i])):
            DP[a[i]+j] = DP[a[i]+j] or DP[j]
    return any(DP[i] for i in range(k-a[m], k))

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

a = [i for i in a if i <k]
a.sort()
n = len(a)

left = -1
right = n

while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(left)

Submission status: Wrong Answer

Solution code:
def check(m):
    DP = [False]*(k+1)
    DP[0] = True
    for i in range(n):
        if i == m:
            continue
        for j in reversed(range(k+1-a[i])):
            DP[a[i]+j] = DP[a[i]+j] or DP[j]
    return any(DP[i] for i in range(k-a[m], k))

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

a = [i for i in a if i <k]
a.sort()
n = len(a)

left = -1
right = n

while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
#sum of sub >=k 
l.sort()
s=sum(l)
if s<k:
    print(n)
else: 
    cnt=0 
    for i in l:
        if s-i<k:
            cnt+=1 
    print(cnt)

Submission status: Wrong Answer

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

    dp = [[10 ** 11 for _ in range(2*K-1)] for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 10 ** 10
    for i in range(N):
        for j in range(K):
            if dp[i][j] < 10 ** 10 + 1:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j])
                if j + a[i] <= 2*(K-1):
                    dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]], dp[i][j], a[i])

    dp_last = dp[-1][K:]
    ans = 0
    i = 0
    prev = 0
    for i in range(N):
        if a[i] == prev:
            i += 1
            ans += 1
            continue
        else:
            prev = a[i]
        ok = 0
        for j in range(min(a[i], len(dp_last))):
            if dp_last[j] <= a[i]:
                ok = 1
                break
        if ok:
            break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
n, k= map(int, input().split())
a=list(map(int,input().split()))
if sum(a)<k:
  print(n)
  sys.exit()
answer=0
b=[]
c=[]
d=[]
for _ in range(2):
  for i in range(n):
    b.append(a[i])
    c.append(i)
    if sum(b)>=k:
      while sum(b)>=k:
        if sum(b)-b[0]>=k:
          d.append(c[0])
          b.pop(0)
          c.pop(0)
        else:
          break
      for j in range(len(b)):
        if sum(b)-b[j]>=k:
          d.append(j)
          answer+=1
      b=[]
  a.reverse()
  b=[]
print(len(list(set(d))))

Submission status: Wrong Answer

Solution code:
n, k= map(int, input().split())
a=list(map(int,input().split()))
answer=0
b=[]
c=[]
d=[]
for _ in range(2):
  for i in range(n):
    b.append(a[i])
    c.append(i)
    if sum(b)>=k:
      while sum(b)>=k:
        if sum(b)-b[0]>=k:
          d.append(c[0])
          b.pop(0)
          c.pop(0)
        else:
          break
      for j in range(len(b)):
        if sum(b)-b[j]>=k:
          d.append(j)
          answer+=1
      b=[]
  a.reverse()
  b=[]
print(len(list(set(d))))

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
# print(l)
a = 0
maisu = 0
end_maisu = 0
ans = 0
for i in range(n):
    maisu += 1
    a += l[i]
    if a >= k:
        a -= l[i]
        ans += 1
        end_maisu = maisu
        maisu = 0
end_maisu -= 1
if end_maisu < 0:
    end_maisu = 0
# print(end_maisu - 1)
print(n - ans - end_maisu)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
# print(l)
a = 0
maisu=0
ans = 0
for i in range(n):
    maisu+=1
    a += l[i]
    if a >= k:
        a = 0
        ans += maisu
        maisu = 0
print(n - ans)