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())
a = list(map(int, input().split()))
a = sorted(a)

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if a[i] >= K:
			return True
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		#dp = [[False] * K for _ in range(N - 1)]
		dp = [False] * K
		if b[0] < K:
			#dp[0][b[0]] = True
			dp[b[0]] = True
		if K - a[i] <= b[0] < K:
			return True
		for j in range(1, N - 1):
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				#if dp[j - 1][k] == True:
					#dp[j][k] = True
				#elif k > b[j]:
				if k > b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp[k] = True

				#if dp[j][k] == True and K - a[i] <= k < K:
				if dp[k] == True and K - a[i] <= k:
					return True

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid + 1, upper)


	print(bi_search(0, N - 1))

Submission status: Wrong Answer

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		#ok = False
		dp = [[False] * K for _ in range(N - 1)]
		if b[0] < K:
			dp[0][b[0]] = True
		if K - a[i] <= b[0] <= K:
			return True
		for j in range(1, N - 1):
			for k in range(1, K):
				if b[j] == K:
					return True
				elif dp[j - 1][k] == True:
					dp[j][k] = True
				elif k > b[j]:
					if dp[j - 1][k - b[j]] == True:
						dp[j][k] = True

				if dp[j][k] == True and K - a[i] <= k < K:
					return True

		return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid, upper)


	print(bi_search(0, N - 1))

Submission status: Wrong Answer

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

if N == 1:
	if a[0] >= K:
		print(0)
	else:
		print(1)

else:
	def check(i):
		if i == 0:
			b = a[1:]
		elif i == N - 1:
			b = a[:N - 1]
		else:
			b = a[:i] + a[i+1:]
		#print(b)
		ok = False
		dp = [[False] * K for _ in range(N - 1)]
		if b[0] < K:
			dp[0][b[0]] = True
		if K - a[i] <= b[0] < K:
			ok = True
		for j in range(1, N - 1):
			for k in range(1, K):
				if dp[j - 1][k] == True:
					dp[j][k] = True
				elif k > b[j]:
					if dp[j - 1][k - b[j]] == True:
						dp[j][k] = True

				if dp[j][k] == True and K - a[i] <= k < K:
					ok = True

		if ok:
			#del b, dp
			return True
		else:
			#del b, dp
			return False


	def bi_search(lower, upper):
		#print(lower, upper)
		mid = (lower + upper) // 2
		#print(mid)
		if mid == 0 and check(mid) == True:
			return 0
		elif mid == N - 2 and check(mid + 1) == False:
			return N
		elif check(mid) == False and check(mid + 1) == True:
			#print("hoge")
			return mid + 1
		elif check(mid) == True:
			return bi_search(lower, mid)
		else:
			return bi_search(mid, upper)


	print(bi_search(0, N - 1))

Submission status: Wrong Answer

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 = [[False] * k for _ in xrange(2)]
        dp[0][0] = True

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

        return any(dp[(n-1)%2][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: Wrong Answer

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):
        if i==x:
            continue
        y=A[x]
        T=set()
        s=A[i]
        for k in L:
            T.add(k)
            if k+y>=K:
                return True
            if k+s<K:
                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: Wrong Answer

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):
        if i==x:
            continue
        T=set()
        s=A[i]
        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 sa<K:
    print(N)
    sys.exit()
if A[0]>=K:
    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: Wrong Answer

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(dp[-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: Wrong Answer

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]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-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: Wrong Answer

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.copy())
        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]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            print(m, am, dp)
            cache[am] = any(dp[-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: Wrong Answer

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.copy())
        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]
            for i in bwd[m + 1]:
                for j in range(k - i - 1, -1, -1):
                    if dp[j]:
                        dp[i + j] = True
            cache[am] = any(dp[-am:])
        return cache[am]

    return judge


def solve(k, aaa):
    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: Wrong Answer

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(np.where(dp)[0].tolist())
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append([0])

    return fwd, bwd


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

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1]
        for i in bwd[m + 1][1:]:
            dp |= shift(dp, i)
        if dp[-aaa[m]:].any():
            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: Wrong Answer

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = []
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = []
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(dp.copy())
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append(np.zeros(k, np.uint8))

    return fwd, bwd


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

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1] | bwd[m + 1]
        if dp[-aaa[m]:].any():
            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: Wrong Answer

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = [dp.copy()]
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = [dp.copy()]
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(dp.copy())
    bwd.reverse()

    fwd.append(np.zeros(k, np.uint8))
    bwd.append(np.zeros(k, np.uint8))

    return fwd, bwd


def solve(k, aaa):
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1] | bwd[m + 1]
        if dp[-aaa[m]:].any():
            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: Wrong Answer

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = [dp.copy()]
    for a in aaa:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = [dp.copy()]
    for a in reversed(aaa):
        dp |= shift(dp, a)
        bwd.append(dp.copy())

    fwd.append(np.zeros(k, np.uint8))
    bwd.append(np.zeros(k, np.uint8))

    return fwd, bwd


def solve(k, aaa):
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1] | bwd[m + 1]
        if dp[-aaa[m]:].any():
            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: Wrong Answer

Solution code:
import bisect

import numpy as np
from scipy.ndimage.interpolation import shift


def preliminary(k, aaa):
    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    fwd = [dp.copy()]
    for a in aaa[:-1]:
        dp |= shift(dp, a)
        fwd.append(dp.copy())

    dp = np.zeros(k, np.uint8)
    dp[0] = 1
    bwd = [dp.copy()]
    for a in aaa[:0:-1]:
        dp |= shift(dp, a)
        bwd.append(dp.copy())

    fwd.append(np.zeros(k, np.uint8))
    bwd.append(np.zeros(k, np.uint8))

    return fwd, bwd


def solve(k, aaa):
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    fwd, bwd = preliminary(k, aaa)

    l = 0
    r = len(aaa) - 1
    m = (l + r) // 2
    while l <= r:
        dp = fwd[m - 1] | bwd[m + 1]
        if dp[-aaa[m]:].any():
            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: Wrong Answer

Solution code:
import bisect
from collections import Counter

import numpy as np
from scipy.ndimage.interpolation import shift


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


def solve(k, aaa):
    uk = bisect.bisect_left(aaa, k)
    aaa = aaa[:uk]

    cnt = Counter(aaa)
    bbb = list(cnt.keys())
    bbb.sort()

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

    return sum(cnt[b] for b in bbb[:l])


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

Submission status: Wrong Answer

Solution code:
import bisect
from collections import Counter

import numpy as np
from scipy.ndimage.interpolation import shift


def judge(e, k, aaa):
    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):
    cnt = Counter(aaa)
    bbb = list(cnt.keys())
    bbb.sort()

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

    return sum(cnt[b] for b in bbb[:l])


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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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)
if sum(A) < K:
    print(N)
    exit()

dp1 = [[0] * (2*K+1) for i in range(N+1)]
dp1[0][0] = 1
for i in range(1, N+1):
    for j in range(2*K+1):
        if A[i-1] > j:
            dp1[i][j] = dp1[i-1][j]
        else:
            dp1[i][j] = dp1[i-1][j] | dp1[i-1][j-A[i-1]]

dp2 = [[0] * (2*K+1) for i in range(N+1)]
dp2[N][0] = 1
for i in range(N)[::-1]:
    for j in range(2*K+1):
        if A[i] > j:
            dp2[i][j] = dp2[i+1][j]
        else:
            dp2[i][j] = dp2[i+1][j] | dp2[i+1][j-A[i]]

for i in range(N+1):
    dp2[i] = list(accumulate(dp2[i]))

ans = 0
for i in range(N):
    for j in range(K+1):
        if dp1[i][j] and (dp2[i+1][K-j-1] - dp2[i+1][K-A[i]-j]):
            break

        if i == N-1:
            if dp1[i][j]:
                break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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
    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: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_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 = [0] * (K+1)
    dp[0] = 1
    for i in range(N-1):
        for j in range(K+1)[::-1]:
            if B[i] > j or dp[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: Wrong Answer

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

print(r)

Submission status: Wrong Answer

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 = 0, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m+1:]

    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: Wrong Answer

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)
if sum(A) < K:
    print(N)
    exit()

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

    dp = [[False] * (K+1) for i in range(N-1)]
    dp[0][0] = True
    for i in range(1, N-1):
        for j in range(K+1):
            dp[i][j] = dp[i-1][j] | dp[i-1][j-B[i]]

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

print(r)

Submission status: Wrong Answer

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)
if sum(A) < K:
    print(N)
    exit()

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

    dp = [[False] * (K+1) for i in range(N-1)]
    dp[0][0] = True
    for i in range(1, N-1):
        for j in range(K+1):
            dp[i][j] = dp[i-1][j] | dp[i-1][j-B[i]]

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

Submission status: Wrong Answer

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)