Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
#!/usr/bin/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: 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)

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

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

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

    return n-ma


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:
# -*- 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)] for _ in range(N+1)]

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

Submission status: Wrong Answer

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 - 1, lm + w), w - 1, -1):
            if dp[l - w]:
                dp[l] = True
                if not set_lm:
                    lm = l
    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: Wrong Answer

Solution code:
import copy
import itertools

lst = [int(e) for e in input().split(" ")]
n = lst[0]
k = lst[1]

a = sorted([int(e) for e in input().split(" ")])

result_num = 0



def test(target):
    """
    True => いらない
    False => ひつよう
    """
    result = False
    tst_list = copy.deepcopy(a)

    if target >= len(tst_list):
        return False

    v = tst_list.pop(target)

    for i in range(len(tst_list)):
        c = list(itertools.combinations(tst_list, i))
        for e in c:
            if k - v <= sum(e):
                if sum(e) >= k:
                    continue
                else:
                    return False
    else:
        return True

    return False

count = 1
i = int(len(a) / 2)

last_true = 0

hey = False

while True:
    result = test(i)
    if result:
        # 進む
        new_i = i + int(len(a) / (2**count))
        if last_true < i + 1:
            last_true = i + 1
    else:
        # 戻る
        new_i = i - int(len(a) / (2**count))

    if new_i == i:
        if test(i + 1):
            if last_true < i + 1 + 1:
                last_true = i + 1 + 1
        if test(i - 1):
            if last_true < i:
                last_true = i
        break

    count += 1

    i = new_i

"""
for i in range(len(a)):
    result = test(i)
    if result:
        result_num += 1
"""

if last_true >= len(a):
    print(len(a))
else:
    print(last_true)

Submission status: Wrong Answer

Solution code:
import copy
import itertools

lst = [int(e) for e in input().split(" ")]
n = lst[0]
k = lst[1]

a = sorted([int(e) for e in input().split(" ")])

result_num = 0


def test(i):
    """
    True => いらない
    False => ひつよう
    """
    result = False
    tst_list = copy.deepcopy(a)
    v = tst_list.pop(i)

    for i in range(len(tst_list)):
        c = list(itertools.combinations(tst_list, i))
        for e in c:
            if k - v <= sum(e):
                if sum(e) >= k:
                    continue
                else:
                    return False
    else:
        result = True

    return result


for i in range(len(a)):
    result = test(i)
    if result:
        result_num += 1


print(result_num)

Submission status: Wrong Answer

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 or nums[0] >= K:
    print(str(N))
    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: Wrong Answer

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

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

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

dp = [[False for i in range(0, N)] for j in range(0, K)]

import numpy as np
res = N
for i in range(0, N):
    n = nums[:i] + nums[i+1:]
    dp_arr = np.array(dp[:])
    dp_arr[0, :] = True
    for j in range(1, K):
        find = False
        for k in range(0, len(n)):
            if j - n[k] < 0:
                continue
            if  dp_arr[j - n[k]][k - 1]:
                dp_arr[j][k] = True
                if j >= K - nums[i]:
                    find = True
                    res -= 1
                    break
        if find:
            break
print(str(res))

Submission status: Wrong Answer

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 k<=a[i] or k<=a[n-1-i]:continue
    ldp[i][a[i]]=True
    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: Wrong Answer

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):
    if k<=a[i] or k<=a[n-1-i]:continue
    ldp[i][0]=True
    rdp[i][0]=True
    ldp[i][a[i]]=True
    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]
lsum=[[0]*k for _ in xrange(n)]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            lsum[i][j]=int(ldp[i][j])
            rsum[i][j]=int(rdp[i][j])
        else:
            lsum[i][j]=lsum[i][j-1]+int(ldp[i][j])
            rsum[i][j]=rsum[i][j-1]+int(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: Wrong Answer

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):
    if k<=a[i] or k<=a[n-1-i]:continue
    ldp[i][a[i]]=1
    rdp[i][a[n-1-i]]=1
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]
lsum=[[0]*k for _ in xrange(n)]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            lsum[i][j]=ldp[i][j]
            rsum[i][j]=rdp[i][j]
        else:
            lsum[i][j]=lsum[i][j-1]+ldp[i][j]
            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:
                left=0
        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: Wrong Answer

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):
    if k<=a[i]or k<=a[n-1-i]:continue
    ldp[i][a[i]]=1
    rdp[i][a[n-1-i]]=1
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]
lsum=[[0]*k for _ in xrange(n)]
rsum=[[0]*k for _ in xrange(n)]
for i in xrange(n):
    for j in xrange(k):
        if j==0:
            lsum[i][j]=ldp[i][j]
            rsum[i][j]=rdp[i][j]
        else:
            lsum[i][j]=lsum[i][j-1]+ldp[i][j]
            rsum[i][j]=rsum[i][j-1]+rdp[i][j]
used=[False]*n
for i in xrange(n):
    if k-a[i]<=0:
        used[i]=True
        continue
    for j in xrange(k):
        if i==0:
            left=0
        elif i==n-1:
            if ldp[i-1][j] and k-a[i]<=j<k:
                used[i]=True
                break
            continue
        else:
            if ldp[i-1][j]:
                left=j
            else:
                left=0
        if k-a[i]-left<=0:
            used[i]=True
            break
        if rsum[n-2-i][k-1-left]-rsum[n-2-i][k-a[i]-left-1]:
            used[i]=True
            break
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Wrong Answer

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)
		can_make2 = can_make[:]
		dp2 = dp[:]
	if True in dp[K-n:]:
		#print(n, dp, file=sys.stderr)
		return True
	else:
		return False

l = -1
r = N
while r - l > 1:
	#print((r+l)//2, is_necessary((r+l)//2), file=sys.stderr)
	if is_necessary((r+l)//2):
		r = (r+l)//2
	else:
		l = (r+l)//2

print(l+1)

Submission status: Wrong Answer

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)
if A[0] >= K:
	print(0)
	exit()

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

l = -1
r = N
while r - l > 1:
	#print((r+l)//2, is_necessary((r+l)//2), file=sys.stderr)
	if is_necessary((r+l)//2):
		r = (r+l)//2
	else:
		l = (r+l)//2

print(l+1)

Submission status: Wrong Answer

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)
if A[0] >= K:
	print(0)
	exit()

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

l = 0
r = N
while r - l > 1:
	#print((r+l)//2, is_necessary((r+l)//2), file=sys.stderr)
	if is_necessary((r+l)//2):
		r = (r+l)//2
	else:
		l = (r+l)//2

print((r+l)//2+1)

Submission status: Wrong Answer

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

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

l = 0
r = N
while r - l > 1:
	#print((r+l)//2, is_necessary((r+l)//2), file=sys.stderr)
	if is_necessary((r+l)//2):
		r = (r+l)//2
	else:
		l = (r+l)//2

print((r+l)//2+1)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[::-1]
    b.pop(w)

    for j in b[::-1]:
        n += j
        #in need
        if K-i <= n < K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[::-1]
    b.pop(w)

    for j in b:
        n += j
        #in need
        if K-i <= n < K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

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

a.sort()

s = 0
for i in range(len(a)):
  s += a[i]
  if s >= k:
    break

aa = [x for x in a if x < a[i]]
bb = [x for x in a if x < k]

cc = []
for i in range(len(aa)):
  c = bb[:i] + bb[i+1:]
  t = k - bb[i]
  flg = 0
  for j in range(2 ** len(c)):
    s = 0
    for l in range(len(c)):
      if (j // 2 ** l) % 2 == 1:
        s += c[l]
    if s >= t and s <= k -1:
      flg = 1
      break
  if flg== 0:
    cc.append(bb[i])
print(len(cc))

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    for i in xrange(idx-cnt-1,-1,-1):
        if tmp+a[i]>=k:
            used[i]=True
        else:
            idx=i
            break
    cnt+=1
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[:]
    b.pop(w)

    for j in b:
        n += j
        #in need
        if n >= K-i and n <= K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[:]
    b.pop(w)

    for j in b:
        n += j
        #in need
        if n > K-i and n <= K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[:]
    b.pop(w)

    for j in b:
        n += j
        #in need
        if n >= K-i and n < K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

Solution code:
import math
import itertools

if __name__=="__main__":
    N,K = list(map(int,input().split()))
    a=list(map(int,input().split()))
    a=sorted(a)
    b=list(itertools.accumulate(a))
    #first=next(x for x in b if x>=K)
    atleastK = [i for i in range(len(b)) if b[i]>=K]
    if atleastK:
        first = atleastK[0]
        bb = b[first]
        unnec = [x for x in range(first+1) if bb-a[x] >= K]
    else:
        unnec = a

    print(len(unnec))

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    now=idx-cnt-1
    f=0
    while now>=0:
        if tmp+a[now]>=k:
            used[now]=True
            now-=1
        else:
            pre=now
            tmp1=a[now]
            if tmp+sum(a[0:now+1])<k:
                f=1
                break
            while now>=0 and tmp+tmp1<k:
                now-=1
                tmp1+=a[now]
            for j in xrange(now,pre+1):
                used[j]=True
            now=pre-1
    if f==1:
        idx=pre
    cnt+=1
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    now=idx-cnt-1
    f=0
    while now>=0:
        if tmp+a[now]>=k:
            used[now]=True
            now-=1
        else:
            r=now
            tmp1=a[now]
            if tmp+sum(a[0:now+1])<k:
                f=1
                break
            while now>=0 and tmp+tmp1<k:
                now-=1
                tmp1+=a[now]
            if now==-1 and tmp+tmp1<k:
                f=1
                break
            else:
                for j in xrange(now,r+1):
                    used[j]=True
                now-=1
    if f==1:
        idx=r
    cnt+=1
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
a = sorted(map(int, raw_input().split()))
res = N
for i,w in zip(a[::-1],range(len(a))[::-1]):
    n = 0
    b = a[:]
    b.pop(w)
    for j in b:
        n += j
        #in need
        if n > K-i and n < K:
            res -= 1
            #print n,i
            break
print res

Submission status: Wrong Answer

Solution code:
import math
import itertools

if __name__=="__main__":
    N,K = list(map(int,input().split()))
    a=list(map(int,input().split()))
    a=sorted(a)
    b=list(itertools.accumulate(a))
    #first=next(x for x in b if x>=K)
    atleastK = [i for i in range(len(b)) if b[i]>=K]
    if atleastK:
        first = atleastK[0]
        bb = b[first]
        unnec = [x for x in range(first+1) if bb-a[x] < K]
    else:
        unnec = a

    print(len(unnec))

Submission status: Wrong Answer

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
cards = sorted(map(int, sys.stdin.readline().split()) , reverse=True)
i = 0
s = 0
j = -1
while i < N:
    s += cards[i]
    if s >= K:
        s = 0
        j = i
    i += 1
if s > K:                                                                                                                                                                                                                             
    print N
else:
    print N-j-1

Submission status: Wrong Answer

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    f=0
    for i in xrange(idx-cnt-1,-1,-1):
        if tmp+a[i]>=k:
            used[i]=True
        else:
            f=1
            idx=i
            break
    if f==0:
        break
    cnt+=1
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Wrong Answer

Solution code:
import sys

N, K = map(int, sys.stdin.readline().split())
cards = sorted(map(int, sys.stdin.readline().split()) , reverse=True)
i = 0
s = 0
j = None
while i < N:
    s += cards[i]
    if s >= K:
        s = 0
        j = i
    i += 1
if j == None:
    print N
else:
    if s > K:                                                                                                                                                                                                                         
        print N
    else:
        print N-j-1

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
num_card, sum_num = map(int, input().split())
l_card = list(map(int, input().split()))

ans = 0
for i in range(1, num_card + 1):
    l_card_com = list(itertools.combinations(l_card, i))
    for card in l_card_com:
        sum_card = 0
        for j in card:
            sum_card += j
        if sum_card >= sum_num:
            card_len = len(card)
            ans += (num_card - card_len)

if ans == 0:
    ans += num_card

print(ans)

Submission status: Wrong Answer

Solution code:
NK = list(map(int, input().split()))

N = NK[0]
K = NK[1]

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

s = sum(A)
c = 0

if s < K:
    print(N)
else:
    for i in A:
        if s - i >= K:
            c += 1
    print(c)

Submission status: Wrong Answer

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

total = sum(a)
if total < k:
    print(n)
    exit()

small = 0
while small < n and a[small] < k:
    small += 1

cnt = 0
for i in range(small):
    able = [False for i in range(k)]
    able[0] = True
    for c in range(small):
        if c == i:
            continue
        for j in range(k-1, -1, -1):
            if able[j] and j+a[c] < k:
                able[j+a[c]] = True
    if not any(able[k-a[i]:k-1]):
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

total = sum(a)
if total < k:
    print(n)
    exit()

small = 0
while small < n and a[small] < k:
    small += 1
    
cnt = 0
for i in range(small):
    able = [False for i in range(k)]
    able[0] = True
    for j in range(k-1, -1, -1):
        if able[j] and j+a[i] < k:
            able[j+a[i]] = True
    if not any(able[k-a[i]:k-1]):
        cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

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


mask = (1<<k)-1

dpl = [1]
dp = 1
for i in a:
    dp |= dp<<i
    dp &= mask
    dpl.append(dp)

dpr = [1]
dp = 1
for i in a[::-1]:
    dp |= dp<<i
    dp &= mask
    dpr.append(dp)


ans = 0
for i in range(n):
    l = dpl[i]
    r = dpr[n-1-i]
    #print(bin(l),bin(r))
    mask = ((1<<a[i])-1)<<(k-a[i])
    #print(bin(mask))
    for j in range(k):
        if l>>j&1 and r&mask:
            break
        mask >>= 1
    else:
        #print(i)
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*arr, = map(int, input().split())

arr = [v for v in arr if v < k]

can_obtain = 1
mask = (1 << 2 * k) - 1

for v in arr:
    can_obtain |= can_obtain << v
    can_obtain &= mask


ans = 0

for i in range(len(arr)):
    can_obtain_excluded = 1
    for j in range(len(arr)):
        if i != j:
            can_obtain_excluded |= can_obtain_excluded << arr[j]
            can_obtain_excluded &= mask
    can_obtain_excluded_with = can_obtain_excluded << arr[i]
    can_obtain_excluded_with >>= k
    if not (can_obtain_excluded_with & ((1 << arr[i]) - 1)):
        ans += 1


print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*arr, = map(int, input().split())

arr = [v for v in arr if v < k]

can_obtain = 1
mask = (1 << 2 * k) - 1

for v in arr:
    can_obtain |= can_obtain << v
    can_obtain &= mask


ans = 0

for i in range(len(arr)):
    can_obtain_excluded = 1
    for j in range(len(arr)):
        if i != j:
            can_obtain_excluded |= can_obtain_excluded << arr[j]
    can_obtain_excluded_with = can_obtain_excluded << arr[i]
    can_obtain_excluded_with >>= k
    if not (can_obtain_excluded_with & ((1 << arr[i]) - 1)):
        ans += 1


print(ans)