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: Runtime Error

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

a.sort()
ans = 0

for i in range(N):
  if a[-1 -i] < K:
    break
  ans += 1

n = N - ans
D = []
re = a[0]
cnt = 0
for i in range(n):
 if re == a[i]:
   cnt += 1
 else:
   D.append([re, cnt])
   cnt = 1
 re = a[i]
else:
  D.append([re, cnt])

L = [{} for _ in range(2 * K)]
M = [[0] * (2 * K) for _ in range(2 * K)]
for i in D:
  for j in range(i[1]):
    if i[0] * (j + 1) >= 2 * K:
      break
    L[i[0] * (j + 1)][i[0]] = 1
    M[i[0] * (j + 1)][i[0]] = 1

for i in D:
  for j in range(i[1]):
    for k in range(K):
      t = i[0] * (j + 1)
      if k + t >= 2 * K:
        break
      if len(L[k]) > 0:
        if M[k][t] == 0:
          for l in L[k].keys():
            M[k + t][l] = 1
            L[k + t][l] = 1
          M[k + t][t] = 1
          L[k + t][l] = 1

for i in D:
  for j in range(K, K + i[0]):
    if len(L[j]) > 0 and M[j][i[0]] == 1:
      ans += i[1]
      break

print(N - ans)

Submission status: Runtime Error

Solution code:
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	l, r = 0, N-1
	while l < r:
		m = (l+r)>>1
		p = True
		if m == 0 and solve(N, K, A[1:], A[0]):
			l = m+1
			continue
		if solve(N, K, A[:m]+A[m+1:], A[m]):
			l = m+1
		else:
			r = m
	if l == N-1 and solve(N, K, A[:N-1], A[N-1]):
		l = N
	print(l)


def solve(n, k, a, ai):
	dp = [[False for _ in range(k+1)] for _ in range(n)]
	dp[0][0] = True
	if a[0] > k:
		dp[0][k] = True
	else:
		dp[0][a[0]] = True
	for i in range(1, n-1):
		for j in range(k-1):
			if not dp[i-1][j]:
				continue
			dp[i][j] = True
			if j + a[i] > k:
				dp[i][k] = True
			else:
				dp[i][j+a[i]] = True
	return not any(map(lambda j: dp[n-2][j], range(k-ai, k)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
	N, K = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()
	l, r = 0, N-1
	while l < r:
		m = (l+r)>>1
		p = True
		if solve(N, K, A[:m]+A[m+1:], A[m]):
			l = m+1
		else:
			r = m
	if l == N-1 and solve(N, K, A[:N-1], A[N-1]):
		l = N
	print(l)


def solve(n, k, a, ai):
	dp = [[False for _ in range(k+1)] for _ in range(n)]
	dp[0][0] = True
	if a[0] > k:
		dp[0][k] = True
	else:
		dp[0][a[0]] = True
	for i in range(1, n-1):
		for j in range(k-1):
			if not dp[i-1][j]:
				continue
			dp[i][j] = True
			if j + a[i] > k:
				dp[i][k] = True
			else:
				dp[i][j+a[i]] = True
	return not any(map(lambda j: dp[n-2][j], range(k-ai, k)))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

cnt = 0
# if sum(a) < K:
#     cnt = len(a)
#     print(cnt)
#     exit()

# a.sort()

def solve(rest_min,b):
    dp = [[False for i in range(K+1)]for j in range(N-1)]
    for i in range(N-1):
        if b[i] < K:
            dp[i][b[i]] = True
        for j in range(K+1):
            if dp[i-1][j]:
                dp[i][j] = True
                if j+b[i] < K:
                    dp[i][j+b[i]] = True


    # print(dp)
    for j in range(rest_min,K+1):
        if dp[-1][j]:
            return True
    return False



for i in range(N):
    rest_min = K-a[i]
    rest_max = K-1
    b = copy.deepcopy(a)
    b.remove(a[i])
    if solve(rest_min,b):
        pass
    else:
        cnt += 1
    """
    もし残りのカードでこの範囲の数を作れれば必要
    無理ならcnt += 1
    """

print(cnt)

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

cnt = 0
# if sum(a) < K:
#     cnt = len(a)
#     print(cnt)
#     exit()

a.sort()

#あるインデックスのものをのぞいて，その値を含むようなものが存在するか調べる
def solve(rest_min,rest_max,b,i,sum):
    if i == len(b):
        return rest_min < sum < rest_max
    if sum > rest_max:
        return False
    if(solve(rest_min,rest_max,b,i+1,sum)):
        return True
    if(solve(rest_min,rest_max,b,i+1,sum+b[i])):
        return True
    return False



for i in range(N):
    rest_min = K-a[i]
    rest_max = K-1

    b = copy.deepcopy(a)
    b.remove(a[i])
    if solve(rest_min,rest_max,b,i=0,sum=0):
        pass
    else:
        cnt += 1
    """
    もし残りのカードでこの範囲の数を作れれば必要
    無理ならcnt += 1
    """

print(cnt)

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7

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

cnt = 0
# if sum(a) < K:
#     cnt = len(a)
#     print(cnt)
#     exit()

a.sort()

#あるインデックスのものをのぞいて，その値を含むようなものが存在するか調べる
def solve(rest_min,rest_max,b,i,sum):
    if i == len(b):
        return rest_min < sum < rest_max
    if(solve(rest_min,rest_max,b,i+1,sum)):
        return True
    if(solve(rest_min,rest_max,b,i+1,sum+b[i])):
        return True
    return False



for i in range(N):
    rest_min = K-a[i]
    rest_max = K-1

    b = copy.deepcopy(a)
    b.remove(a[i])
    if solve(rest_min,rest_max,b,i=0,sum=0):
        pass
    else:
        cnt += 1
    """
    もし残りのカードでこの範囲の数を作れれば必要
    無理ならcnt += 1
    """

print(cnt)

Submission status: Runtime Error

Solution code:
def main():
    def accumulate(X):
        ret = [X[0]]
        for x in X[1:]:
            ret.append(ret[-1] + x)
        return ret
    
    N, K = map(int, raw_input().split())
    A = list(map(int, raw_input().split()))
 
    # K以上の数はすべて必要なのでA未満の数だけを考える
    A = sorted([a for a in A if a < K], reverse=True)
    N = len(A)
 
    # dp1[i][k] := 1 ~ iまでのカードを使って数kが作れるか
    dp1 = [[0] * (K + 1) for i in range(N + 1)]
    dp1[0][0] = 1
    # dp2[i][k] := N ~ iまでのカードを使って数kが作れるか
    dp2 = [[0] * (K + 1) for i in range(N + 1)]
    dp2[0][0] = 1
 
    # dpテーブルを計算
    for i in range(1, N + 1):
        for k in range(K + 1):
            dp1[i][k] = max(dp1[i][k], dp1[i - 1][k])
            if A[i - 1] <= k:
                dp1[i][k] = max(dp1[i][k], dp1[i - 1][k - A[i - 1]])
 
            dp2[i][k] = max(dp2[i][k], dp2[i - 1][k])
            if A[N - i] <= k:
                dp2[i][k] = max(dp2[i][k], dp2[i - 1][k - A[N - i]])
 
    # 累積和を取っておく
    for i in range(N + 1):
        dp2[i] = list(accumulate(dp2[i]))
 
    # ansを計算
    need = 0
    for i in range(1, N + 1):
        for k in range(K + 1):
            # 1 ~ i番目まででkが作れない
            if not dp1[i - 1][k]:
                continue
 
            # 1 ~ i番目までだけで必要な条件が作れる
            if K - A[i - 1] <= k < K:
                need += 1
                break
 
            # 範囲外参照
            if K - A[i - 1] - k - 1 < 0:
                continue
 
            if dp2[N - i][K - k] - dp2[N - i][K - A[i - 1] - k - 1] > 0:
                need += 1
                break
 
    print(N - need)
 
main()

Submission status: Runtime Error

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

def check_needed(index):
    memo = [[0] * (max_k + 1) for _ in range(n+1)]
    memo[0][0] = 1
    for i in range(n):
        for j in range(max_k + 1):
            if memo[i][j] == 1: 
                memo[i+1][j] = 1 
                if i != index:
                    memo[i+1][j+a[i]] = 1 
    return (1 in memo[n][max(k-a[index], 0):k])

l = -1
r = n
while r-l > 1:
    mid = (l+r) // 2
    if not check_needed(mid):
        r = mid
    else:
        l = mid
if sum(a) < k:
    print(n)
else:
    print(n - r)

Submission status: Runtime Error

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][k - A[i]:]):
            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: Runtime Error

Solution code:
def no_need(N: int, K: int, A: list) -> int:
    count = 0
    for i in range(N):
        # s[i] を要素の和が i 以上の部分集合の個数とする。
        s = [0] * (K + 1)
        s[0] = 1

        for a in A[:i] + A[i+1:]:
            for k in range(K, -1, -1):
                s[min(K, a + k)] += s[k]

        s[0] = 0
        for k in range(K, 0, -1):
            s[k-1] += s[k]

        count += 1 if s[K - A[i]] - s[K] == 0 else 0

    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: Runtime Error

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

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

SUM=0
for a in A:
    SUM+=a
    if SUM>=K:
        MAX_NO_NEED=a
        break

else:
    print(N)
    sys.exit()
        

A=[a for a in A if a<K]
L=len(A)

MIN=-1
MAX=A.index(MAX_NO_NEED)-1

while MIN!=MAX:

    x=(MIN+MAX+1)//2
    base=A[x]

    SET={base}
    flag=0
    
    for i in range(L):
        #print(x,i,SET)
        if i==x:
            continue
        a=A[i]
        NSET=copy.copy(SET)
        
        for j in SET:
            
            if K<=a+j<K+base:
                flag=1
                break
            elif a+j<K:
                NSET.add(a+j)

        if flag==1:
            #print(x,SET)
            MAX=x-1
            break

        SET=NSET

    else:
        MIN=x
        continue

print(MIN+1)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
if N==1:
    if K-a[0]<=0:
        print(1)
    else:
        print(0)
def dp(i):
    res=[[0 for k in range(K)] for j in range(N-1)]
    L=[]
    for j in range(N):
        if i!=j:
            L.append(j)
    for j in range(N-1):
        for k in range(K):
            if j==0:
                if k==a[L[j]] or k==0:
                    res[j][k]=1
                else:
                    res[j][k]=0
                continue
            if res[j-1][k]==1:
                if k+a[L[j]]<K:
                    res[j][k+a[L[j]]]=1
                res[j][k]=1
    return res

def check(i):
    table=dp(i)[N-2]
    for j in range(max(K-a[i],0),K):
        if table[j]==1:
            return False
    return True

X=sorted([(a[i],i) for i in range(N)])
low=-1
high=N
mid=(low+high)//2
while((high-low)>1):
    mid=low+(high-low)//2
    #range(low,mid) or range(mid,high)
    flag=check(X[mid][1])
    if flag:
        low=mid
    else:
        high=mid
print(low+1)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
if N==1:
    if K-a[0]<=0:
        print(1)
    else:
        print(0)
def dp(i):
    res=[[0 for k in range(K)] for j in range(N-1)]
    L=[]
    for j in range(N):
        if i!=j:
            L.append(j)
    for j in range(N-1):
        for k in range(K):
            if j==0:
                if k==a[L[j]] or k==0:
                    res[j][k]=1
                else:
                    res[j][k]=0
                continue
            if res[j-1][k]==1:
                if k+a[L[j]]<K:
                    res[j][k+a[L[j]]]=1
                res[j][k]=1
    return res

def check(i):
    table=dp(i)[N-2]
    for j in range(max(K-a[i],0),K):
        if table[j]==1:
            return False
    return True

X=sorted([(a[i],i) for i in range(N)])
low=0
high=N
mid=(low+high)//2
if check(X[N-1][1]):
    print(N)
    exit()
if not(check(X[0][1])):
    print(0)
    exit()
while((high-low)>1):
    mid=(low+high)//2
    #range(low,mid) or range(mid,high)
    flag=check(X[mid][1])
    if flag:
        low=mid
    else:
        high=mid
print(low+1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef long long llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define print(a) cout << a << endl;
#define n_max 5005


int A[n_max];
int n,k;

bool judge( int ind){
    int dp[5000]={};
    if(A[ind] >=k) return true;
    dp[0]=1;
    REP(i,n){
        int a= A[i];
        if(i==ind) continue;
        REPR(j,k){
            if( j-a >= 0 and dp[j-a] ==1 ) dp[j]=1;
        }
    }
    FOR(i,k-A[ind],k) if(dp[i] == 1) return true;
    return false;
}
int main(){
    cin >> n >> k;
    REP(i,n) cin >> A[i];
    sort(A,A+n);
    int left = -1;
    int right = n-1;
    int mid;
    while(1){
        if(left + 1 >= right ) break;
        mid=(left + right) / 2;
        if(judge(mid)){
            right= mid-1 ;
        }
        else left = mid;
    }

    if(judge(right)){
        cout << left + 1  << endl;
    }
    else cout << right +1 << endl;


}

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i in range(N):
    a_ = a[i]
    if Smax + a_ >= K:
        ans = N-i-1
    updated = False
    for j in range(min(Smax,K-a_-1),-1,-1):
        if dp[j]:
            dp[j+a_=True
            if not updated:
                Smax = max(Smax,j+a_)
                updated = True

print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
for i in range(N):
    i = N-i-1
    for j in range(K):
        if j < a[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j],dp[i+1][j-a[i]]+a[i])
print(0)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
import numpy as np
b = np.cumsum(np.array(a))
if b[-1] < K:
    print(N)
    exit()
elif b[0] >= K:
    print(0)
    exit()
import bisect
i = bisect.bisect(b,K)
w = K-a[i]
b = b[:i]
while b[-1] >= w:
    i = bisect.bisect(b,w)
    w -= a[i]
    if w <= 0:
        break
    b = b[:i]
    if len(b)==0:
        break
print(i)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, K = map( int, input().split())
A = list( map( int, input().split()))
RA = A.sort( reverse = True)
s = 0
ans = 0
for a in RA:
    if s+a < K:
        s += A
        ans += 1
    else:
        ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()
Inf = 5001

def DP(i, K, L, memo = {}):
    if i == 0:
        return (True if K == 0 else False)
    try:
        return memo[(i, K)]
    except KeyError:
        if DP(i-1, K-L[i-1], L, memo) or DP(i-1, K, L, memo):
            ret = True 
        else:
            ret = False
        memo[(i, K)] = ret
        return ret

low, high = 0, N+1
while high - low > 1:
    L = copy.deepcopy(A)
    mid = (high + low)//2
    l = L.pop(mid-1)  
    if l >= K:
        high = mid
    else:
        memo = {}
        for i in range(1, l + 1):
            if DP(N-1, K-i, L, memo):
                high = mid
                break
        else:
            low = mid

print(low)

Submission status: Runtime Error

Solution code:
import copy
N, K = map(int, input().split())
A = [int(_) for _ in input().split()]
A.sort()
Inf = 5001

def DP(i, K, L, memo = {}):
    if i == 0 and K == 0:
        return True
    elif i == 0:
        return False
    try:
        return memo[(i, K)]
    except KeyError:
        if DP(i-1, K-L[i-1], L, memo) or DP(i-1, K, L, memo):
            ret = True 
        else:
            ret = False
        memo[(i, K)] = ret
        return ret

low, high = 0, N+1
while high - low > 1:
    L = copy.deepcopy(A)
    mid = (high + low)//2
    del L[mid-1]
    memo = {}
    for i in range(1, A[mid-1] + 1):
        if DP(N-1, K-i, L, memo):
            high = mid
            break
    else:
        low = mid

print(low)

Submission status: Runtime Error

Solution code:
# 入力
file = open("g080D.txt", "r")
stdin = file

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()

a_ltk = [ai for ai in a if ai < k]
a_ltk.sort(reverse=True)
need = {ai:False for ai in a_ltk}

# 貪欲に足していく
for i in range(len(a_ltk)):
    cur = 0
    stack = []
    for j in range(i,len(a_ltk)):
        cur += a_ltk[j]
        stack.append(a_ltk[j])
        if cur >= k:
            for key in stack:
                need[key] = True
            stack.pop()
            cur -= a_ltk[j]

                
cnt = Counter(a_ltk)
ans = 0

for k,v in need.items():
    if not v:
        ans += cnt[k]
        
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from pprint import pprint
from collections import Counter, defaultdict, deque
import queue
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret


@mt
def slv2(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] < 0:
            return True
        dp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue
            tdp = dp[:]
            for j in range(K):
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp = tdp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    ans = 0
    for i in range(N):
        if not f(i):
            ans += 1

    return ans


@mt
def slv(N, K, A):
    @lru_cache(maxsize=None)
    def f(w):
        if K - A[w] <= 0:
            return True
        dp = [0] * (K)
        tdp = [0] * (K)

        for i, a in enumerate(A):
            if i == w:
                continue
            tdp[i] = dp[i]
            for j in range(K):
                if dp[j] and j + a < K:
                    tdp[j+a] = 1
            if a < K:
                tdp[a] = 1
            dp, tdp = tdp, dp

        if sum(dp[K-A[w]:]) > 0:
            return True

        return False

    A.sort()
    l = 0
    r = N-1
    x = 0
    while r-l > 1:
        # error_print(x)
        # x += 1
        c = (l+r)//2
        if f(c):
            r = c
        else:
            l = c

    if f(l):
        return l
    return r + 1 if not f(r) else l + 1


def main():
    N, K = read_int_n()
    A = read_int_n()
    print(slv(N, K, A))

    # for i in range(10000):
    #     N = random.randint(1, 50)
    #     K = random.randint(1, 50)
    #     A = [random.randint(1, 10) for _ in range(N)]
    #     x = slv(N, K, A[:])
    #     y = slv2(N, K, A[:])
    #     print(x, y)
    #     if x != y:
    #         print(N, K)
    #         print(' '.join(map(str, A)))
    #         return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

count = N
s = 0
for i in range(N-1,-1,-1):
    if s + N[i] < K:
        s += N[i]
    else:
        count = min(i,count)
print(count)

Submission status: Runtime Error

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

dp1 = [[False]*K for _ in range(N)]
dp2 = [[False]*K for _ in range(N)]
# dp[x][y] x枚目まで使った時にyに出来るか
# K-ai <= ai < K となる部分集合を探す

dp1[0][a[0]] = True
dp1[0][0] = True
for i in range(1,N):
    for j in range(K):
        dp1[i][j] = dp1[i-1][j] or (j-a[i] >= 0 and dp1[i-1][j-a[i]])

dp2[0][a[N-1]] = True
dp2[0][0] = True
for i in range(1,N):
    for j in range(K):
        dp2[i][j] = dp2[i-1][j] or (j-a[N-i-1] >= 0 and dp2[i-1][j-a[N-i-1]])
count = 0
for i in range(N):
    if K-a[i] <= 0:
        count += 1
        continue
    for j in range(K-a[i],K):
        f = False
        if i == 0:
            if dp2[N-2][j]:
                count += 1
                break
            else:
                continue
        elif i == N-1:
            if dp1[N-2][j]:
                count += 1
                break
            else:
                continue
        for k in range(j+1):
            if dp1[i-1][k] and dp2[N-i-2][j-k]:
                count += 1
                f = True
                break
        if f:
            break
print(N-count)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
if a_sum < K:
    print(N)
    exit()
if a_sum == K:
    print(0)
    exit()
count = 0
L = [i for i in a if i < K]
L_sum = sum(L)
if L_sum < K:
    print(len(K))
    exit()
if L_sum == K:
    print(0)
    exit()
for i in L:
    if L_sum - i >= K:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
a_sum = sum(a)
if a_sum < K:
    print(N)
    exit()
if a_sum == K:
    print(0)
    exit()
count = 0
L = [i for i in a if i < K]
L_sum = sum(L)
if L_sum < K:
    print(len(N))
    exit()
if a_sum == K:
    print(0)
    exit()
for i in L:
    if L_sum - i >= K:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import bisect

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

def solve(a,K):
  if A[a]>=K:
    return False
  bits=1
  for i in range(len(A)):
    if i!=a:
      bits|= bits<<A[i]
  cnt = (1<<A[a])-1
  bits >>= (K-A[a])
  if bits&cnt:
    return False
  else:
    return True

for i in range(N-1,-1,-1):
  if solve(i,K):
    ans=bisect.bisect_right(A, A[i])
    break
print(ans)

Submission status: Runtime Error

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

A.sort()

res = []

for n_ex in range(N):
  dp = [[False] * K for n in range(N+1)]
  dp[0][0] = True
  for n in range(N):
    for k in range(0, K):
      dp[n+1][k] = dp[n][k]
    if n != n_ex:
      for k in range(0, K - A[n]):
        if dp[n][k] == True:
          dp[n+1][k+A[n]] = True
  for k in range(K-A[n_ex], K):
    if dp[N][k] == True:
      res.append(n_ex)
      break
print(N-len(res))

Submission status: Runtime Error

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

A.sort()

res = []

for n_ex in range(N):
  A_tmp = A.copy()
  A_tmp.pop(n_ex)
  dp = [[False] * K for n in range(N)]
  dp[0][0] = True
  for cnt in range(1, N):
    for k in range(0, K):
      dp[cnt][k] = dp[cnt-1][k]
    for k in range(0, K - A_tmp[cnt-1]):
      if dp[cnt-1][k] == True:
        dp[cnt][k+A_tmp[cnt-1]] = True
  for k in range(K-A[n_ex], K):
    if dp[N-1][k] == True:
      res.append(n_ex)
      break
print(N-len(res))

Submission status: Runtime Error

Solution code:
ini=map(int,raw_input().split())
a=map(int,raw_input().split())
b=[]
for i in a:
    b.append(i)
b.sort()
c=[]
while True:
    sum=0
    add=0
    for i in b:
        sum+=i
    if sum<ini[1] and len(c)>=1:
        b.append(c[-1])
        c.pop(-1)
        c.reverse()
        while True:
            sum=0
            for i in c:
                sum+=i
            if sum<ini[1]:
                break
            time=0
            sum=0
            for i in c:
                sum+=i
                time+=1
                if sum>=ini[1]:
                    add+=time
                    for j in range(time):
                        c.pop(j)
                    sum=0
                    time=0
        break
    elif sum<ini[1] and len(c)==0:
        b=c
        break
    else:
        c.append(b[0])
        b.pop(0)
print ini[0]-len(b)-add

Submission status: Runtime Error

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

ok = []
for i in range(N):
    b = a.copy()
    del b[i]
    dp = [[0 for y in range(K)] for x in range(N-1)]
    for x in range(N-1):
        if b[x] < K:
            dp[x][b[x]] = 1
        for y in range(K):
            dp[x][y] += dp[x-1][y]
            if y > b[x]:
                dp[x][y] += dp[x-1][y-b[x]]
    if sum(dp[N-2][K-a[i]:K])>0:
        ok.append(a[i])

ans = N - len(ok)
print(ans)

Submission status: Runtime Error

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

l = 0
r = N

while(r > l):
    s = int((l+r)/2)
    if A[s] > K:
        r = s
        continue
    si = False
    dp = [[False for i in range(K+2)] for j in range(K+2)]
    dp[0][0] = True
    for i in range(1,N):
        for j in range(K):
            if(dp[i-1][j] == True):
                dp[i][j] = True
            if i != s and j >= A[i] and dp[i-1][j-A[i]]:
                dp[i][j] = True
    for i in range(K-A[s], K):
        if dp[N-1][i]:
            si = True
            break
    if(si == True):
        r = s
    else:
        l = s+1
    
print(r)

Submission status: Runtime Error

Solution code:
#ABC56 D input
nk = list(map(int, input().split()))
N = nk[0]
K = nk[1]

A = sorted(list(map(int, input().split())))

count = 0
for a in A:
    new_a = A[:]
    new_a.remove(a)
    dp = [[-1 for i in range(N)] for j in range(K+1)]
    for i in range(N):
        dp[0][i] = True
    for i in range(1,K+1):
        dp[i][0] = False
    
    for i in range(1,K+1):
        for j in range(1, N):
            dp[i][j] = dp[i][j-1]
            if(i >= new_a[j-1]):
                dp[i][j] = dp[i][j] or dp[i-new_a[j-1]][j-1]
    res = False         
    for i in range(K-a,K):
        res = res or dp[i][N-1]
    
    if(res == False):
        count += 1
        
print(count)

Submission status: Runtime Error

Solution code:
def whatIsMinNumber(X_copy,K):
    pickupNum = X_copy[len(X_copy)//2]
    X_rest = X[:]
    X_rest.remove(pickupNum)
    if can_do_number(X_rest,0,K-pickupNum,K-1):
        if len(X_copy) > 2:
            return whatIsMinNumber(X_copy[len(X_copy)//2+1:len(X_copy)],K)
        else:
            return pickupNum
    else:
        if len(X_copy) > 1:
            return whatIsMinNumber(X_copy[0:len(X_copy)//2],K)
        else:
            return pickupNum+1

def can_do_number(X,sum,min,max):
    if len(X) == 0:
        return False
    for i in range(0,len(X)):
        if min <= sum <= max:
            return True
        elif min <= sum+X[i] <= max:
            return True
        elif min > sum+X[i]:
            X_rest = X[:]
            sum = sum + X_rest.pop(i)
            can_do_number(X_rest,sum,min,max)
        else:
            pass
    return False

N,K = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort(reverse = True)
thenum = whatIsMinNumber(X[:],K)
print(len(list(filter((lambda x:x<thenum),X))))