Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
def f(x):
    y=A[x]
    if y>=K:
        return True
    L=set()
    L.add(0)
    for i in range(N):
        if i==x:
            continue
        T=set()
        s=A[i]
        for k in L:
            T.add(k)
            if k+s>=K:
                continue
            if k+s+y>=K:
                return True
            T.add(k+s)
        L=T
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    if A[x]>=K:
        return True
    L=set()
    L.add(0)
    for i in range(N):
        T=set()
        s=A[i]
        if i==x:
            s=0
        for k in L:
            T.add(k)
            if k+s<K:
                T.add(k+s)
        L=T
    for k in L:
        if k+A[x]>=K:
            return True
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
def f(x):
    L=[set() for i in range(N+1)]
    L[0].add(0)
    for i in range(N):
        s=A[i]
        if i==x:
            s=0
        for k in L[i]:
            L[i+1].add(k)
            if k+s<K:
                L[i+1].add(k+s)
    for k in L[N]:
        if k+A[x]>=K:
            return True
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def preliminary(k, aaa):
    dp = [False] * k
    dp[0] = True
    curr_max = 0
    fwd = []
    for a in aaa:
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        fwd.append(dp[:])
        curr_max += a

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    bwd = []
    for a in reversed(aaa):
        for i in range(min(curr_max, k - a - 1), -1, -1):
            if dp[i]:
                dp[i + a] = True
        bwd.append([i for i, v in enumerate(dp) if v][1:])
        curr_max += a
    bwd.reverse()

    dummy = [False] * k
    dummy[0] = True
    fwd.append(dummy)
    bwd.append([])

    return fwd, bwd


def get_judge(k, aaa):
    fwd, bwd = preliminary(k, aaa)
    cache = [None] * k

    def judge(m):
        am = aaa[m]
        if cache[am] is None:
            dp = fwd[m - 1]
            ndp = dp[:]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        ndp[i + j] = True
            cache[am] = any(ndp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    if sum(aaa) < k:
        return n

    aaa.sort()
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    judge = get_judge(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(k, aaa))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
from scipy.ndimage.interpolation import shift


def judge(e):
    ae = aaa[e]
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    for i, a in enumerate(aaa):
        if i == e:
            continue
        dp |= shift(dp, a)
    return dp[-ae:].any()


def solve(k, aaa):
    l = 0
    r = bisect.bisect_left(aaa, k) - 1
    m = (l + r) // 2
    while l <= r:
        if judge(m):
            r = m - 1
        else:
            l = m + 1
        m = (l + r) // 2

    return l


n, k = map(int, input().split())
aaa = list(map(int, input().split()))
aaa.sort()
print(solve(k, aaa))

Submission status: Time Limit Exceeded

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)

Submission status: Time Limit Exceeded

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

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

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if sum(B) < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

    if 1 in dp[K-A[m]:K]:
        r = m
    else:
        l = m

print(r)

Submission status: Time Limit Exceeded

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

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

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if sum(B) < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

    for k in range(K - A[m], K + 1):
        if dp[k]:
            if k >= K:  # 不要
                l = m
            else:
                r = m
            break
    else:
        l = m

print r

Submission status: Time Limit Exceeded

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

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

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m+1:]

    if sum(B) < K-A[m]:
        l = m
        continue

    dp = [False] * (K+1)
    dp[0] = True
    for i in range(N-1):
        for j in range(K+1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j-B[i]]

    for k in range(K-A[m], K+1):
        if dp[k]:
            if k >= K:  # 不要
                l = m
            else:
                r = m
            break
    else:
        l = m

print(r)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n, k = f.read_int_list()
    a = f.read_int_list()
    a.sort(reverse=True)

    # if n > 400: return 0

    def check(ind):
        aa = a[:]
        aa.pop(ind)
        dp = [False] * k
        dp[0] = True

        for i in xrange(n-1):
            dp2 = dp[:]
            for j in xrange(k):
                if not dp[j]: continue
                if aa[i] + j < k:
                    dp2[aa[i]+j] = True
            dp = dp2

        return any(dp[k-a[ind]:])

    mi = -1
    ma = n

    while ma - mi > 1:
        mid = (ma+mi)/2
        if check(mid):
            mi = mid
        else:
            ma = mid

    return n-ma

    # need = 0
    # for i in xrange(n):
    #     if check(i): need += 1
    #
    # return n-need

class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False] * K
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP1[j+a] = True
    DP = DP1 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True
 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
from operator import add
from itertools import accumulate
 
N, K = inpl()
A = sorted(inpl())
S = list(accumulate(A, add))
A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True
 
if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
from operator import add
from itertools import accumulate

N, K = inpl()
A = sorted(inpl())
S = list(accumulate(A, add))
A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, K = inpl()
A = sorted(inpl(), reverse=True)

DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, K = inpl()
A = sorted(inpl(), reverse=True)

DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0):
        if d:
            if j + a >= K:
                OK[i] = True
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Time Limit Exceeded

Solution code:
def is_needed(i):
    dp = [False] * k
    dp[0] = True
    lm = 0
    for j, w in enumerate(aa):
        if i == j:
            continue
        set_lm = False
        for l in range(min(k - w - 1, lm), -1, -1):
            if dp[l]:
                dp[l + w] = True
                if not set_lm:
                    lm = l + w
                    set_lm = True
    return any(dp[k - aa[i]:])


n, k = map(int, input().split())
aa = sorted(map(int, input().split()))

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)

Submission status: Time Limit Exceeded

Solution code:
def is_needed(i):
    dp = [False] * k
    dp[0] = True
    for j, w in enumerate(aa):
        if i == j:
            continue
        for l in range(k - 1, w - 1, -1):
            if dp[l - w]:
                dp[l] = True
    return any(dp[k - aa[i]:])


n, k = map(int, input().split())
aa = sorted(map(int, input().split()))

l, h = 0, n - 1
while l <= h:
    c = (l + h) // 2
    if is_needed(c):
        h = c - 1
    else:
        l = c + 1
print(l)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

n,k = readln()
a = list(filter(lambda x: x < k,readln()))
m = k
f = [0 for i in range(0,m+1)]
f[0] = 1
for x in a:
    for index in range(x,m+1):
        i = m - index
        f[x+i] = f[x+i] + f[i]

ans = 0
s = f[:]
for x in a:
    for i in range(0,x):
        s[i] = f[i]
    for i in range(0,m-x):
        s[x+i] = f[x+i] - s[i]
    b = 1;
    for i in range(k-x,k):
        if s[i] > 0:
            b = 0
            break
    ans = ans + b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

n,k = readln()
a = list(filter(lambda x: x < k,readln()))
m = k
f = [0 for i in range(0,m+1)]
f[0] = 1
for x in a:
    for index in range(x,m+1):
        i = m - index
        f[x+i] = f[x+i] + f[i]
ans = 0
for x in a:
    s = f[:]
    for i in range(0,m-x):
        s[x+i] = s[x+i] - s[i]
    b = 1;
    for i in range(k-x,k):
        if s[i] > 0: b = 0
    ans = ans + b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def check(K, x, nums):
    if nums[x] >= K:
        return True
    bitset = [0 for i in range(0, K)]
    bitset[0] = 1
    for i in range(0, len(nums)):
        if i == x:
            continue
        shift = nums[i]
        tmp = [0 for j in range(0, shift)]
        tmp = tmp + bitset
        for j in range(0, K):
            if bitset[j] == 0 and (bitset[j] == 1 or tmp[j] == 1):
                bitset[j] = 1
                if j >= K - nums[x]:
                    return True
    return False

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

nums = list(map(int, input().split()))
nums.sort()

if sum(nums) < K:
    print(str(N))
    quit()
if nums[0] >= K:
    print("0")
    quit()

l = 0
r = N
while l < r:
    mid = int((l + r) / 2)
    if check(K, mid, nums):
        r = mid
    else:
        l = mid + 1
print(str(l))

Submission status: Time Limit Exceeded

Solution code:
def check(K, x, nums):
    if nums[x] >= K:
        return True
    bitset = [0 for i in range(0, K)]
    bitset[0] = 1
    for i in range(0, len(nums)):
        if i == x:
            continue
        shift = nums[i]
        tmp = [0 for j in range(0, shift)]
        tmp = tmp + bitset
        for j in range(0, K):
            if bitset[j] == 1 or tmp[j] == 1:
                bitset[j] = 1
                if j >= K - nums[x]:
                    return True
    return False

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

nums = list(map(int, input().split()))
nums.sort()

if sum(nums) < K:
    print(str(N))
    quit()
if nums[0] >= K:
    print("0")
    quit()

l = 0
r = N
while l < r:
    mid = int((l + r) / 2)
    if check(K, mid, nums):
        r = mid
    else:
        l = mid + 1
print(str(l))

Submission status: Time Limit Exceeded

Solution code:
def check(K, x, nums):
    if nums[x] >= K:
        return True
    bitset = [0 for i in range(0, K)]
    bitset[0] = 1
    for i in range(0, len(nums)):
        if i == x:
            continue
        shift = nums[i]
        tmp = [0 for j in range(0, shift)]
        tmp = tmp + bitset
        for j in range(0, K):
            if bitset[j] == 1 or tmp[j] == 1:
                bitset[j] = 1
    for i in range(K - nums[x], K):
        if bitset[i] == 1:
            return True
    return False

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

nums = list(map(int, input().split()))
nums.sort()

if sum(nums) < K:
    print(str(N))
    quit()
if nums[0] >= K:
    print("0")
    quit()

l = 0
r = N
while l < r:
    mid = int((l + r) / 2)
    if check(K, mid, nums):
        r = mid
    else:
        l = mid + 1
print(str(l))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
ldp=[[0]*k for _ in xrange(n)]
rdp=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    ldp[i][0]=True
    rdp[i][0]=True
    if a[i]<k:
        ldp[i][a[i]]=True
    if a[n-i-1]<k:
        rdp[i][a[n-1-i]]=True
for i in xrange(1,n):
    for j in xrange(k):
        if j-a[i]>=0:
            ldp[i][j]|=ldp[i-1][j-a[i]]|ldp[i-1][j]
        else:
            ldp[i][j]|=ldp[i-1][j]
        if j-a[n-1-i]>=0:
            rdp[i][j]|=rdp[i-1][j-a[n-1-i]]|rdp[i-1][j]
        else:
            rdp[i][j]|=rdp[i-1][j]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            rsum[i][j]=rdp[i][j]
        else:
            rsum[i][j]=rsum[i][j-1]+rdp[i][j]
cnt=0
for i in xrange(n):
    if k-a[i]<=0:
        cnt+=1
        continue
    for j in xrange(k):
        if i==0:
            left=0
        elif i==n-1:
            if ldp[i-1][j] and a[i]+j>=k:
                cnt+=1
                break
            continue
        else:
            if ldp[i-1][j]:
                left=j
            else:
                continue
        if k-a[i]-left<=0:
            cnt+=1
            break
        if rsum[n-2-i][k-1-left]-rsum[n-2-i][k-a[i]-left-1]:
            cnt+=1
            break
print n-cnt

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = [False]*K
	dp2[0] = True
	can_make = []
	can_make2 = [0]
	for i in range(N):
		if i == n:
			continue
		elif A[i] >= K:
			break
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2.extend(can_make)
		can_make = []
		dp2 = dp[:]
	return False

l = -1
r = N
while r - l > 1:
	m = (r+l)//2
	if A[m-1] == A[m] and m > 0:
		m = bisect_left(A,A[m],0,m)
	if is_necessary(m):
		r = m
	else:
		l = m

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = [False]*K
	dp2[0] = True
	can_make = []
	can_make2 = [0]
	for i in range(N):
		if i == n:
			continue
		elif A[i] >= K:
			break
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2.extend(can_make)
		can_make = []
		dp2 = dp[:]
	return False

l = -1
r = N
while r - l > 1:
	m = (r+l)//2
	while A[m-1] == A[m] and m > 0:
		m -= 1
	if is_necessary(m):
		r = m
	else:
		l = m

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = [False]*K
	dp2[0] = True
	can_make = []
	can_make2 = [0]
	for i in range(N):
		if i == n:
			continue
		elif A[i] >= K:
			break
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2.extend(can_make)
		can_make = []
		dp2 = dp[:]
	return False

l = -1
r = N
while r - l > 1:
	m = (r+l)//2
	if m > 0 and A[m-1] == A[m]:
		m = bisect_left(A,A[m])
	if is_necessary(m):
		r = m
	else:
		l = m

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = []
	can_make2 = [0]
	#card = A[:n] + A[n+1:]
	for i in range(N):
		if i == n:
			continue
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2.extend(can_make)
		can_make = []
		dp2 = dp[:]
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = []
	can_make2 = [0]
	#card = A[:n] + A[n+1:]
	for i in range(N):
		if i == n:
			continue
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2 += can_make
		can_make = []
		dp2 = dp[:]
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = [0]
	can_make2 = [0]
	#card = A[:n] + A[n+1:]
	for i in range(N):
		if i == n:
			continue
		a = A[i]
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2 = can_make[:]
		dp2 = dp[:]
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
S = sum(A)

if S < K:
	print(N)
	exit()
elif A[0] >= K:
	print(0)
	exit()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = [0]
	can_make2 = can_make[:]
	card = A[:n] + A[n+1:]
	for a in card:
		for j in can_make2:
			if dp2[j] and j+a < K and not dp2[j+a]:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
		can_make2 = can_make[:]
		dp2 = dp[:]
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = [0]
	can_make2 = can_make[:]
	card = A[:n] + A[n+1:]
	for a in card:
		for j in can_make2:
			if dp2[j] and j+a < K and dp2[j+a] == False:
				if j + a >= K - A[n]:
					return True
				dp[j+a] = True
				can_make.append(j+a)
			elif j + a >= K:
				break
		can_make2 = sorted(can_make[:])
		dp2 = dp[:]
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
A.sort()
print(A, file=sys.stderr)

def is_necessary(n):
	if A[n] >= K:
		return True
	dp = [False]*K
	dp[0] = True
	dp2 = dp[:]
	can_make = [0]
	can_make2 = can_make[:]
	card = A[:n] + A[n+1:]
	for a in card:
		for j in can_make2:
			if dp2[j] and j+a < K and dp2[j+a] == False:
				dp[j+a] = True
				can_make.append(j+a)
				if j + a >= K - A[n]:
					print(n, True, dp, file=sys.stderr)
					return True
		can_make2 = can_make[:]
		dp2 = dp[:]
	print(n, False, dp, file=sys.stderr)
	return False

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

print(l+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
# sys.stdin = open('d3.in')

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

prefix = [set() for _ in range(n + 1)]
# suffix = [set() for _2 in range(n + 1)]

prefix[0] = {0}
for i in range(n):
    for v in prefix[i]:
        prefix[i+1].add(v)
        if v + a[i] <= k:
            prefix[i+1].add(v + a[i])

suffix_i = {0}

# Cumulative sums
c_suffix = [[0] * (k+1) for _3 in range(n + 1)]

for j in range(k):
    c_suffix[n][j + 1] = c_suffix[n][j] + (j in suffix_i)

for i in range(n - 1, -1, -1):
    to_add = set()
    for v in suffix_i:
        if v + a[i] <= k:
            to_add.add(v + a[i])
    suffix_i.update(to_add)
    for j in range(k):
        c_suffix[i][j + 1] = c_suffix[i][j] + (j in suffix_i)


def find(i):
    if k <= a[i]:
        return 0
    for s in prefix[i]:
        start = max(0, k - a[i] - s)
        stop = k - s
        if c_suffix[i + 1][stop] - c_suffix[i + 1][start] > 0:
            return 0
    return 1


res = 0
for i in range(n):
    res += find(i)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.stdin = open('d3.in')

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

prefix = [set() for _ in range(n + 1)]
suffix = [set() for _2 in range(n + 1)]

prefix[0] = {0}
for i in range(n):
    for v in prefix[i]:
        prefix[i+1].add(v)
        if v + a[i] <= k:
            prefix[i+1].add(v + a[i])

suffix[n] = {0}
for i in range(n - 1, -1, -1):
    suffix[i] = set(suffix[i + 1])
    for v in suffix[i + 1]:
        if v + a[i] <= k:
            suffix[i].add(v + a[i])

# Cumulative sums
c_suffix = [[0] * (k+1) for _3 in range(n + 1)]
for i in range(n + 1):
    for j in range(k):
        c_suffix[i][j + 1] = c_suffix[i][j] + (j in suffix[i])


def find(i):
    if k <= a[i]:
        return 0
    for s in prefix[i]:
        start = max(0, k - a[i] - s)
        stop = k - s
        if c_suffix[i + 1][stop] - c_suffix[i + 1][start] > 0:
            return 0
    return 1


res = 0
for i in range(n):
    res += find(i)
print(res)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# sys.stdin = open('d3.in')

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

prefix = [list() for _ in range(n + 1)]
suffix = [set() for _2 in range(n + 1)]

prefix[0] = [0]
for i in range(n):
    values = set(prefix[i])
    for v in prefix[i]:
        if v + a[i] <= k:
            values.add(v + a[i])
    prefix[i + 1] = list(sorted(values))

suffix[n] = {0}
for i in range(n - 1, -1, -1):
    suffix[i] = set(suffix[i + 1])
    for v in suffix[i + 1]:
        if v + a[i] <= k:
            suffix[i].add(v + a[i])

# Cumulative sums
c_suffix = [[0] * (k+1) for _3 in range(n + 1)]
for i in range(n + 1):
    for j in range(k):
        c_suffix[i][j + 1] = c_suffix[i][j] + (j in suffix[i])


def find(i):
    if k <= a[i]:
        return 0
    for s in prefix[i]:
        start = max(0, k - a[i] - s)
        stop = k - s
        if c_suffix[i + 1][stop] - c_suffix[i + 1][start] > 0:
            return 0
    return 1


res = 0
for i in range(n):
    res += find(i)
print(res)