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:
# -*- coding:utf-8 -*-
from itertools import combinations
n,k = map(int,input().split())
a = list(map(int, input().split()))
a=sorted(a)
o=0
discard = []
hold = []
checked = []
if sum(a) < k:
    o = n
else:
    for i in range(n,-1,-1):
        b = list(combinations(a, i+1))

        b = reversed(b)
        # 組み合わせ全通り
        for c in b:
            # それぞれの組み合わせ検証
            s = sum(c)
            if s >= k:
                # 良い集合だけを検証、なければそれ以下の集合は検証しない
                c = reversed(c)
                for d in c:
                    if (s-d) >=k:
                        discard.append(d)
                        discard=list(set(discard))
                    else:
                        # 未満になれば、その数値は必要、それ以後の取り出しは無意味なのでbreak
                        hold.append(d)
                        hold=list(set(hold))
                        break
                    checked.append(d)
            else:
                break
    ans = list(set(discard)-set(hold))
    o = len(ans)
print(o)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from itertools import combinations
n,k = map(int,input().split())
a = list(map(int, input().split()))
a=sorted(a)
o=0
discard = []
hold = []
checked = []
if sum(a) < k:
    print(n)
else:
    for i in range(n,-1,-1):
        b = list(combinations(a, i+1))
        # 組み合わせ全通り
        for c in b:
            # それぞれの組み合わせ検証
            s = sum(c)
            if s >= k:
                # 良い集合だけを検証、なければそれ以下の集合は検証しない
                c = sorted(c)
                for d in c:
                    if (s-d) >=k:
                        discard.append(d)
                        discard=list(set(discard))
                    else:
                        # 未満になれば、その数値は必要、それ以後の取り出しは無意味なのでbreak
                        hold.append(d)
                        hold=list(set(hold))
                        break
                    checked.append(d)
            else:
                break
    ans = list(set(discard)-set(hold))
    o = n - len(ans)
    print(o)

Submission status: Wrong Answer

Solution code:
input_lines1 = str(input())
input_lines2 = str(input())

N = int(input_lines1.split(' ')[0])
K = int(input_lines1.split(' ')[1])

a = []
inputLines2StrAry = input_lines2.split(' ')

dame = [0] * N
count = 0

def sumAryNumber(ary,numberAry):
    result = 0
    for number in numberAry:
        result = result + int(ary[number])
    return result

for kosuu in range(N + 1):
    if kosuu == 0:
        b = 1
    else:
        for kaishi in range(N - kosuu + 1):
            addResult = sumAryNumber(inputLines2StrAry,range(kaishi,kaishi + kosuu))
            if addResult >= K:
                for banme in range(kaishi,kaishi + kosuu):
                    dame[banme] = dame[banme] + 1
                    if addResult - int(inputLines2StrAry[banme]) >= K:
                        dame[banme] = dame[banme] - 1

for dameNakami in dame:
    if dameNakami == 0:
        count = count + 1

print(count)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
l.reverse()
s = 0
for i in range(n):
    x = l[i]
    l.remove(x)
    ll = l[:]
    sum = 0
    for j in range(n-1):
        if sum + ll[j] < k:
            sum += ll[j]
    if sum + x >= k:
        pass
    else:
        s = i
        break
    l.insert(i, x)

print(n-s)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product as p
N, K = map(int, input().split())
a = np.array(list(map(int, input().split())))
bs = np.array(list(p((True, False), repeat=N)))

z = np.zeros(N, dtype=int)
ids = np.arange(N)
if sum(a) < K:
 print(0)
else:
 for i in range(N):
  Si = sum(a[bs[i,:]])
  if Si < K: continue
  for j in ids[bs[i,:]]:
   if Si - a[j] < K: z[j] = 1
 print(N-sum(z))

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product as p
N, K = map(int, input().split())
a = np.array(list(map(int, input().split())))
bs = np.array(list(p((True, False), repeat=N)))

z = np.zeros(N, dtype=int)
ids = np.arange(N)
if sum(a) < K:
 print(0)
else:
 for i in range(N):
  Si = sum(a[bs[i,:]])
  if Si < K: continue
  for j in ids[bs[i,:]]:
   if Si - a[j] < K: z[j] = 1
 print(sum(z))

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from itertools import combinations
n,k = map(int,input().split())
a = list(map(int, input().split()))
o=0
discard = []
hold = []
check = False
for i in range(n,-1,-1):
    b = list(combinations(a, i+1))
    for c in b:
        if sum(c) >= k:
            check = True
            # 良い集合 c
            for d in c:
                if (sum(c)-d) >=k:
                    discard.append(d)
                    discard=list(set(discard))
                else:
                    hold.append(d)
                    hold=list(set(hold))
        else:
            pass
o = n if not check else len(discard)-len(hold)
print(o)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().strip().split())
ai = list(map(int, input().strip().split()))
 
ai.sort()
ssum = 0
flag = False
for i in range(N):
	ssum += ai[i]
	if ssum >= K:
		flag = True
		break
if flag:
	j = 0
	cnt = 0
	while(j <= i):
		ssum -= ai[j]
		if ssum >= K:
			cnt += 1
		else:
			break
		j += 1
	print(cnt)
else:
	print(N)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product as p
import sys

N, K = map(int, input().split())
a = np.array(list(map(int, input().split())))
bs = np.array(list(p((True, False), repeat=N)))
print(bs, file=sys.stderr)

if sum(a) < K:
 print(0)
else:
 C = 0
 for i in range(N):
  Sa = sum(a[bs[i,:]])
  if Sa >= K and Sa - a[i] < K:
   C+=1
 print(C)

Submission status: Wrong Answer

Solution code:
import math
def main():
    global K,N,A,AM
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()

    flag = (max(A) >= K)  # よい部分集合がないということはない
    AM = sum(A)
    if not flag and AM < K:  # よい集合が存在しない
        print(len(A))
        return

    print(binary_search_for_integer(len(A)-1, -1))


def binary_search_for_integer(ok, ng):
    while math.fabs(ok-ng) > 1:
        mid = (ok+ng)/2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def solve(x):
    if AM - x >= K:
        return False
    else:
        return True


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

A = sorted(A)[::-1]

res = 0
for i in range(N):
    tmp1 = [A[i]]
    flag = False
    for j in range(N):
        if i == j:
            continue

        tmp2 = []
        for t in tmp1:
            now = t + A[j]
            if now < K:
                tmp2.append(now)
            else:
                if now - A[i] >= K:
                    res += 1
                    flag = True
                    break

        if flag:
            break

        for t in tmp2:
            tmp1.append(t)

print(res)

Submission status: Wrong Answer

Solution code:
K = int(raw_input().split(" ")[1])
print K
d = map(int, raw_input().split(" "))
s = sum(d)
c = 0
for i in d:
	if s - i > K:
		c += 1
print c

Submission status: Wrong Answer

Solution code:
import math
NK = input().split()
N = int(NK[0])
K = int(NK[1])
x = input().split()
cards = []
total = 0
NoNeed = []
for i in range(len(x)):
    cards.append(x[i])
cards.sort()
for j in range(len(cards)):
    total += int(cards[j])
    if total >= K and int(cards[j]) < K:
        NoNeed.append(min(cards))
    elif int(cards[j]) >= K:
        print(len(cards)-1)
        break
if total < K:
    for x in range(len(cards)):
        NoNeed.append(cards[x])
print(len(NoNeed))

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from itertools import combinations
n,k = map(int,input().split())
a = list(map(int, input().split()))
o=0
check = False
for i in range(n,-1,-1):
    b = list(combinations(a, i+1))
    for c in b:
        if sum(c) >= k:
            check = True
            for d in c:
                if (sum(c)-d) >=k:
                    print(sum(c)-d)
                    o +=1
        else:
            pass
o = n if not check else o
print(o)

Submission status: Wrong Answer

Solution code:
import itertools
import sys
def main():
    N, K = map(int, input().split())
    a = tuple(map(int, input().split()))

    i = 1
    while i < N:
        for x in itertools.combinations(a, i):
            if sum(x) >= K:
                print(str(N - i))
                sys.exit()
        i += 1
    print(str(N))

main()

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().strip().split())
ai = list(map(int, input().strip().split()))
 
ai.sort()
ssum = sum(ai)
cnt = 0
if ssum < K:
	print(N)
else:
	for i in range(N-1, -1, -1):
		if ai[i] >= K:
			ssum -= ai[i]
			continue
		else:
			ssum -= ai[i]
			if ssum >= K:
				cnt += 1
			else:
				ssum += ai[i]
 
	print(cnt)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
if sum(A) < K:
    print N
else:   
    B = list(sorted(A))[::-1]
    C = []
    for b in B:
        if b not in C:
            C.append(b)

    D = []
    for c in C:
        for i in xrange(B.count(c)):
            D.append(c*(i + 1))

    s = 0
    D = list(sorted(D))
    for i, d in enumerate(D):
        s += d
        if s >= K:
            istart = i + 1
            s = 0
    print N - istart

Submission status: Wrong Answer

Solution code:
a, b=map(int,input().split())
s=list(map(int,input().split()))
s.sort()
ss=list(filter(lambda x: x < b, s))
i=int(0)
k=1
if(sum(ss)<b):
	print(a)
	k=2
while(k==1):
	del ss[0]
	if(sum(ss)==b):
		i=i+1
		print(i)
		k=2
	elif(sum(ss)<=b):
		print(i)
		k=2
	i=i+1

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int, input().split()))
sm = sum(a)
if k>sm: print(n)
else:
    table = [set() for i in range(2*k)]
    table[0].add(0)
    for elm in a:
        if elm >= k : continue
        idxlist = []
        for i in range(2*k):
            if len(table[i]) != 0:
                if i+elm<2*k:
                    idxlist.append(i+elm)
        for idx in idxlist:
            table[idx].union(table[idx-elm])
            table[idx].add(elm)

    need = 0
    for elm in a:
        if elm >= k: need += 1
        else:
            flag = False
            for i in range(k,k+elm):
                if elm in table[i]:
                    need += 1
                    break
    print(n-need)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
if sum(A) <= K:
    print N
else:   
    B = list(sorted(A))[::-1]
    C = []
    for b in B:
        if b not in C:
            C.append(b)

    D = []
    for c in C:
        for i in xrange(B.count(c)):
            D.append(c*(i + 1))

    s = 0
    D = list(sorted(D))
    for i, d in enumerate(D):
        s += d
        if s >= K:
            istart = i + 1
            s = 0
    print N - istart

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
if sum(A) <= K:
    print N
else:   
    B = list(sorted(A))[::-1]
    C = []
    for b in B:
        if b not in C:
            C.append(b)

    D = []
    for c in C:
        for i in xrange(B.count(c)):
            D.append(c*(i + 1))

    s = 0
    for i, d in enumerate(D):
        s += d
        if s >= K:
            istart = i + 1
            s = 0
    print N - istart

Submission status: Wrong Answer

Solution code:
import math
NK = input().split()
N = int(NK[0])
K = int(NK[1])
x = input().split()
cards = []
total = 0
NoNeed = []
for i in range(len(x)):
    cards.append(x[i])
for j in range(len(cards)):
    total += int(cards[j])
    if total >= K and int(cards[j]) < K:
        NoNeed.append(min(cards))
    elif int(cards[j]) >= K:
        for y in range(j):
            NoNeed.append(cards[y])
if total < K:
    for x in range(len(cards)):
        NoNeed.append(cards[x])
print(len(NoNeed))

Submission status: Wrong Answer

Solution code:
from itertools import chain,combinations
def powersetoverK(iterable):
    return list(filter(lambda x: sum(map(int, x)) >= K,chain.from_iterable(combinations(iterable, r) for r in range(len(iterable)+1))))

N,K = map(int, input().split())
a = input().split()
print(N - sum([len(powersetoverK(a[:i-1]+a[i:]))== 0 and len(powersetoverK(a))>0 for i in range(1, N+1)]))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(" ")))
a = list(map(int, input().split(" ")))
s = sum(a)
c = 0

if s < k:
    print(len(a))
    exit()

for i in a:
    if s-i > k:
        c += 1

print(c)

Submission status: Wrong Answer

Solution code:
data = input().split()
N = int(data[0])
K = int(data[1])

list = []
data = input().split()
for i in range(N):
	list.append(int(data[i]))

list.sort()

sum = 0
i = 0
while(sum < K):
	sum += list[i]
	i += 1
	if(sum < K and i >= len(list)):
		print(len(list))
		exit()
i -= 1

count = 0
j = 0
while(sum >= K):
	sum -= list[j]
	count += 1
	j += 1
count -= 1

print(count)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().strip().split())
ai = list(map(int, input().strip().split()))
 
ai.sort()
ssum = sum(ai)
cnt = 0
if ssum < K:
	print(N)
else:
	for i in range(N-1, -1, -1):
		if ai[i] >= K:
			ssum -= ai[i]
			continue
		else:
			sums = ssum - ai[i]
			if sums >= K:
				cnt += 1
 
	print(cnt)

Submission status: Wrong Answer

Solution code:
import math
NK = input().split()
N = int(NK[0])
K = int(NK[1])
x = input().split()
cards = []
total = 0
NoNeed = []
for i in range(len(x)):
    cards.append(x[i])
for j in range(len(cards)):
    total += int(cards[j])
    if total >= K:
        NoNeed.append(min(cards))
if total < K:
    for x in range(len(cards)):
        NoNeed.append(cards[x])
print(len(NoNeed))

Submission status: Wrong Answer

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
for a in A:
	z = 0
	B = A[:]
	B.remove(a)
	fusoku = [K - i - 1 for i in range(a)]
	for i in range(1,len(B) + 1):
		C = list(itertools.combinations(B,i))
		for c in C:
			if sum(c) in fusoku:
				need.append(a)
				z = 1
				break
		if z == 1:
			break

print(N - len(need))

Submission status: Wrong Answer

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

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

print ans

Submission status: Wrong Answer

Solution code:
import math
NK = input().split()
N = int(NK[0])
K = int(NK[1])
x = input().split()
cards = []
total = 0
NoNeed = []
for i in range(len(x)):
    cards.append(x[i])
for j in range(len(cards)):
    total += int(cards[j])
    if total >= K:
        NoNeed.append(min(cards))
if total < K:
    for x in range(len(cards)):
        NoNeed.append(cards)
print(len(NoNeed))

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().strip().split())
ai = list(map(int, input().strip().split()))
 
ai.sort()
ssum = 0
flag = False
for i in range(N):
	ssum += ai[i]
	if ssum >= K:
		flag = True
		break
if flag:
	j = 0
	while(True):
		ssum -= ai[j]
		if ssum < K:
			print(j)
			break
		j += 1
else:
	print(N)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
if sum(A) <= K:
    print N
else:
    B = list(sorted(A))[::-1]
    nn = 0
    s = 0
    istart = 0
    for i, b in enumerate(B):
        s += b
        if s >= K:
            istart = i + 1
            s = 0
    print N - istart

Submission status: Wrong Answer

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

n_card =0
if sum(a)<k:
    print(n)
else:
    for i in range(n):
        j = 0
        s = 0
        while s<k:
            s += a[j]
            j+=1
        if s - a[i] >= k: 
            n_card += 1
        else:
            break
            
    print(n_card)

Submission status: Wrong Answer

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

n_card =0
if sum(a)<k:
    print(n)
else:
    for i in range(n):
        j = 1
        s = 0
        while s<k:
            s = sum(a[i:j])
            j+=1
        if s - a[i] >= k: 
            n_card += 1
        else:
            break
            
    print(n_card)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
a = list(map(int, input().split()))
sm = sum(a)
if k>sm: print(n)
else:
    ans = 0
    for i in range(n):
        if sm-a[i] >= k: ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    nonzeros = [1]
    for a in As:
        ndp = nonzeros[-1]
        if a <= K:
            ndp |= (nonzeros[-1] & ((1 << (K-a)) - 1)) << a
        nonzeros.append(ndp)
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = [0] * (K+1)
    dp[0] = 1
    nonzeros = [1]
    for a in As:
        ndp = []
        nonzero = 0
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t == 0:
                ndp.append(0)
            else:
                nonzero |= 1 << i
                ndp.append(1)
        nonzeros.append(nonzero)
        dp = ndp
    dp = [0] * (K+1)
    dp[0] = 1
    acc = list(accumulate(dp)) + [0]
    ans = 0
    for i in range(N, 0, -1):
        a = As[i-1]
        ndp = []
        for j in range(K+1):
            t = dp[j] if j < a else dp[j] + dp[j-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        if a < K:
            nonzero = nonzeros[i-1]
            for y in range(K+1):
                if nonzero & 1:
                    t = K-y-a-1
                    if acc[K-y-1] > acc[t if t >= 0 else -1]:
                        break
                nonzero >>= 1
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp = [0] * (K+1)
    dp[0] = 1
    nonzeros = [set([0])]
    for a in As:
        ndp = []
        nonzero = set()
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            if t == 0:
                ndp.append(0)
            else:
                nonzero.add(i)
                ndp.append(1)
        nonzeros.append(nonzero)
        dp = ndp
    
    dp = [0] * (K+1)
    dp[0] = 1
    accs = [list(accumulate(dp)) + [0]]
    for a in reversed(As):
        ndp = []
        for i in range(K+1):
            t = dp[i] if i < a else dp[i] + dp[i-a]
            ndp.append(0 if t == 0 else 1)
        dp = ndp
        accs.append(list(accumulate(dp)) + [0])
    
    ans = 0
    for i in range(1, N+1):
        a = As[i-1]
        if a >= K:
            continue
        nonzero = nonzeros[i-1]
        acc = accs[N-i]
        for y in nonzero:
            t = K-y-a-1
            if acc[K-y-1] > acc[t if t >= 0 else -1]:
                break
        else:
            ans += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    
    dp1 = [[0] * (K+1)]
    dp1[0][0] = 1
    for a in As:
        ndp = []
        pdp = dp1[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp1.append(ndp)
    
    dp2 = [[0] * (K+1)]
    dp2[0][0] = 1
    for a in reversed(As):
        ndp = []
        pdp = dp2[-1]
        for i in range(K+1):
            ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
        dp2.append(ndp)
    accs2 = [list(accumulate(dp)) + [0] for dp in dp2]
    
    ans = 0
    for i in range(1, N+1):
        a = As[i-1]
        if a >= K:
            continue
        dp = dp1[i-1]
        acc2 = accs2[N-i]
        for y in range(K+1):
            if dp[y] == 0:
                continue
            t = K-y-a-1
            if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
                break
        else:
            ans += 1
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, K = map(int, input().split())
As = list(map(int, input().split()))

dp1 = [[0] * (K+1)]
dp1[0][0] = 1
for a in As:
    ndp = []
    pdp = dp1[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp1.append(ndp)

dp2 = [[0] * (K+1)]
dp2[0][0] = 1
for a in reversed(As):
    ndp = []
    pdp = dp2[-1]
    for i in range(K+1):
        ndp.append(pdp[i] if i < a else pdp[i] + pdp[i-a])
    dp2.append(ndp)
accs2 = [list(accumulate(dp)) + [0] for dp in dp2]

ans = 0
for i in range(1, N+1):
    a = As[i-1]
    if a >= K:
        continue
    dp = dp1[i-1]
    acc2 = accs2[N-i]
    for y in range(K+1):
        if dp[y] == 0:
            continue
        t = K-y-a-1
        if acc2[K-y-1] > acc2[t if t >= 0 else -1]:
            break
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [0] + sorted(map(int, input().split()))

# iを除いた左右の部分集合でK以上の数が作れるか
rdp_shift = [N + 1] * K  # rdp_shift[j] = (右からi個を使って部分和jを作れるような最初のi)
rdp_shift[0] = 0
rdp = [0] * K  # rdp[i][j] = (a(-1),...,a(-i)の部分和でjを作れるか)
rdp[0] = 1
for i in range(1, N + 1):
    rdp2 = [0] * K
    for j in range(K):
        if rdp[j] == 1:
            rdp2[j] = 1
            continue
        # print(j, -i, j - A[-i])
        # print(i, j)
        if j - A[-i] >= 0 and rdp[j - A[-i]] == 1:
            rdp2[j] = 1
            rdp_shift[j] = i
    rdp = rdp2

# print(rdp_shift, A)
ldp = [0] * K
ldp[0] = 1
S = [0] * (K + 1)
ans = 0
for i in range(1, N + 1):
    # ここで一つ一つチェックしている！！
    # A[i]が不要かチェック
    for j in range(K):
        # print(j)
        S[j + 1] = S[j]
        if rdp_shift[j] <= N - i:
            # print(S, rdp_shift, j, N - i, A[i])
            S[j + 1] += 1
            # print(S)
            # print(S, rdp_shift[j], N - i, i, j)
    no_need = True
    for lval in range(K):
        # print(ldp, lval)
        if ldp[lval] == 0:
            continue
        # print(K - A[i] - lval)
        rval = S[K - lval] - S[max(0, K - A[i] - lval)]
        # print(S, K - lval, K - A[i] - lval, rval)
        # print(rval, no_need, A[i], lval)
        # rval > 0というのはA[i]がなければ、K以上の集合を作れない場合があるということ
        if rval > 0:
            # print(S, K - lval, K - A[i] - lval, lval, rval, i, j, A[i])
            no_need = False
            break
    if no_need:
        ans += 1

    # ldp[i][:]の計算
    ldp2 = [0] * K
    for j in range(K):
        if ldp[j] == 1 or (j >= A[i] and ldp[j - A[i]] == 1):
            ldp2[j] = 1
    ldp = ldp2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, K = map(int, input().split())
A = list(map(int, input().split()))
#A = [i for i in range(1,2)] + [i for i in range(2,1001)] * 4
A.sort()

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  
ans = 0
DP_rev = [0 for _ in range(K)] #戻すDP!!!
flag = True
for a in A:
  if not flag: break
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      flag = False
      break
  if flag:
    ans += 1
  #print(a, DP_rev)
    
print(ans)

Submission status: Time Limit Exceeded

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

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  
ans = 0
DP_rev = [0 for _ in range(K)] #戻すDP!!!
for a in A:
  flag = True
  if a >= K: break
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      flag = False
      break
  if flag:
    ans += 1
  #print(a, DP_rev)
    
print(ans)

Submission status: Time Limit Exceeded

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

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  
ans = 0
DP_rev = [0 for _ in range(K)] #戻すDP!!!
for a in A:
  flag = True
  if a >= K: break
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      #print(i,a)
      flag = False
      break
  if flag:
    ans += 1
  #print(a, DP_rev)
    
print(ans)

Submission status: Time Limit Exceeded

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

DP = [0 for k in range(K+1)] #和がkとなる部分集合の数
DP[0] = 1
for a in A:
  for k in range(K-a,-1,-1):
    DP[k+a] += DP[k]

"""
for k in range(1,2*K+1): #累積和へ変換
  DP[k] += DP[k-1]
print(DP)
"""
"""
if sum(DP[0:K]) == 2**N:
  print(N)
  sys.exit()
"""
#print(DP)  
ans = 0
DP_rev = [0 for _ in range(K)] #戻すDP!!!
for a in A:
  flag = True
  if a >= K: continue
  for i in range(K):
    DP_rev[i] = DP[i] 
    if i-a >= 0:
      DP_rev[i] -= DP_rev[i-a]
    if i >= K-a and DP_rev[i] > 0:
      #print(i,a)
      flag = False
      break
  if flag:
    ans += 1
  #print(a, DP_rev)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    if sum(a) >= k:
        for i in range(n):
            if k <= a[i]:
                continue
            dp = np.zeros((k+1), dtype=np.bool)
            dp[0] = True
            for j in range(n):
                if k <= a[j] or j == i:
                    continue
                dp[a[j]:] |= dp[:-a[j]]
            f = False
            for j in range(k-a[i], k):
                f |= dp[j]
            if not f:
                ans += 1
    else:
        ans = n
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if k <= a[i]:
            continue
        dp = np.zeros((k+1), dtype=np.bool)
        dp[0] = True
        for j in range(n):
            if k <= a[j] or j == i:
                continue
            dp[a[j]:] |= dp[:-a[j]]
        f = False
        for j in range(k-a[i], k):
            f |= dp[j]
        if not f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
N = len(A)
dp_init = lambda x:True if x == 0 else False
#Aの左からと右から加えていく場合のdpテーブルを作成
ldp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
rdp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
for i in range(N):
    for j in range(K):
        ldp[i+1][j] = (lambda:ldp[i][j] if j < A[i] else ldp[i][j] | ldp[i][j-A[i]])()
        rdp[i+1][j] = (lambda:rdp[i][j] if j < A[N-1-i] else rdp[i][j] | rdp[i][j-A[N-1-i]])()

def dpAny(n,m): #== any(ldp[n][m] & rdp[N-n-1][m-j] for j in range(i+1))
    for j in range(m+1):
        if ldp[n][j] & rdp[N-n-1][m-j]:
            return True
    return False

def NoNeed(n):
    #ldp[n]とrdp[N-1-n]でA[n]を含まない部分集合の取り得る和が求められる。
    for i in range(K-A[n],K):
        if dpAny(n,i):
            return 0
    else:
        return 1

ans = 0
for i in range(N):
    ans += NoNeed(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = [int(x) for x in input().split() if int(x) < K]
N = len(A)
dp_init = lambda x:True if x == 0 else False
#Aの左からと右から加えていく場合のdpテーブルを作成
ldp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
rdp = [[dp_init(i) for i in range(K)] for _ in range(N+1)]
for i in range(N):
    for j in range(K):
        ldp[i+1][j] = (lambda:ldp[i][j] if j < A[i] else ldp[i][j] | ldp[i][j-A[i]])()
        rdp[i+1][j] = (lambda:rdp[i][j] if j < A[N-1-i] else rdp[i][j] | rdp[i][j-A[N-1-i]])()

def dpAny(n,m): #== any(ldp[n][m] & rdp[N-n-1][m-j] for j in range(i+1))
    for j in range(m+1):
        if ldp[n][j] & rdp[N-n-1][m-j]:
            return True
    return False

def NoNeed(n):
    #ldp[n]とrdp[N-1-n]でA[n]を含まない部分集合の取り得る和が求められる。
    dp = [dpAny(n,i) for i in range(K-A[n],K)]
    return 1 if not any(dp) else 0

ans = 0
for i in range(N):
    ans += NoNeed(i)
print(ans)