Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Time Limit Exceeded

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


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

needs = 0
dp = [[False for _ in range(k)] for _ in range(n + 1)]
dp2 = [[False for _ in range(k)] for _ in range(n + 1)]
for l in range(n + 1):
    dp[l][0], dp2[l][0] = True, True

for i in range(1, n + 1):
    for j in range(1, k):
        prev = False if j - cards[i - 1] < 0 else dp[i - 1][j - cards[i - 1]]
        dp[i][j] = dp[i - 1][j] or prev

        prev2 = False if j - cards[n - i] < 0 else dp2[i - 1][j - cards[n - i]]
        dp2[i][j] = dp2[i - 1][j] or prev2

for i, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    b = False
    for x, xb in enumerate(dp[i]):
        for y, yb in enumerate(dp2[n - i - 1]):
            if k - val <= x + y < k and xb and yb:
                b = True
                break

        if b:
            needs += 1
            break

print(n - needs)

Submission status: Time Limit Exceeded

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


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

needs = 0
for index, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    c_without_i = cards[:index] + cards[index + 1:]
    b = False

    dp = [[False for _ in range(k)] for _ in range(n)]
    for l in dp:
        l[0] = True

    for i in range(1, n):
        for j in range(1, k):
            prev = False if j - c_without_i[i - 1] < 0 else dp[i - 1][j - c_without_i[i - 1]]
            dp[i][j] = dp[i - 1][j] or prev

    for l in dp:
        for i in range(k - val, k):
            if l[i]:
                needs += 1
                b = True
                break

        if b: break
print(n - needs)

Submission status: Time Limit Exceeded

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

import array


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

needs = 0
for i, val in enumerate(cards):
    if val >= k:
        needs += 1
        continue

    c_without_i = cards[:i] + cards[i + 1:]

    dp = array.array('b', [0] * k)
    dp2 = array.array('b', [0] * k)
    b = False
    for m in c_without_i:
        if m >= k: continue
        for j, v in enumerate(dp):
            dp2[j] = v or dp2[j]
            if v is 1 and (j + m) < k:
                if k - val <= j + m:
                    needs += 1
                    b = True
                    break
                dp2[j + m] = 1

        if b:
            break

        dp2[m] = 1
        dp, dp2 = dp2, dp

print(n - needs)

Submission status: Time Limit Exceeded

Solution code:
N, K = [int(x) for x in input().split(" ")]
A = [int(x) for x in input().split(" ") if int(x) < K]
A.sort(reverse=True)

bitset = [0]*K
bitset[0] = 1

ans = 0
for a in A:
    ans += 1
    for i in range(K-a, K):
        if bitset[i] == 1:
            ans = 0
            break
    for i in reversed(range(K-a)):
        if bitset[i] == 1:
            bitset[i+a]=1
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
INF=10**10


def is_no_need(array,K,X):
    #X=除く値
    temp=array[X]
    a=array[:]
    a.pop(X)
    n=len(a)
    dp=[[False for _ in range(2*K)] for _ in range(n)]
    dp[0][0]=True
    dp[0][a[0]]=True
    for i in range(1,n):
        for j in range(K):
            if j>=a[i]:
                dp[i][j]=dp[i-1][j] or dp[i-1][j-a[i]]
            else:
                dp[i][j]=dp[i-1][j]
                
    
    for i in range(K-temp,K):
        if dp[n-1][i]:
            return False
        
    return True
    

def main():
    N,K=list(map(int,input().split()))
    #N,K=3,6
    ans=0
    a=list(map(int,input().split()))
    #a=[1,4,3]
    array=[]
    for i in a:
        if i<K:
            array.append(i)
    del a
    N=len(array)
    for X in range(N):
        if is_no_need(array,K,X):
            ans+=1
    
    print(ans)


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
N, K = map(int, input().split())
A = list(map(int, input().split()))
unnec = 0
for i in range(0,N):
    B = list(A)
    v = B[i]
    B[i] = 0
    nec = False
    for j in range(len(B),0,-1):
        for l in list(itertools.combinations(B,j)):
            s = sum(l)
            #print("%s, %d, %d" % (str(l), s, v))
            if s >= K:
                continue
            elif s + v >= K:
                nec = True
                break
        if nec == True:
            break
    if nec == False:
        unnec = unnec + 1
print(unnec)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))
a.sort()
cnt = 0
for s in range(N):
    if a[s]<K:
        a2 = copy.deepcopy(a)
        a2.pop(s)
        dp = [[False for i in range(K + 1)] for j in range(N + 1)]
        dp[0][0] = True
        for i in range(1, N):
            for j in range(K + 1):
                if dp[i - 1][j] or (j >= a2[i - 1] and dp[i - 1][j - a2[i - 1]]):
                    dp[i][j] = True
        result = False
        for j in range(K-a[s], K):
            if dp[N-1][j]:
                result = True
                break
        if result:
            cnt += 1
    else :
        cnt += N-s
        break


print(N-cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
for s in range(N):
    if a[s]<K:
        a2 = copy.deepcopy(a)
        a2.pop(s)
        dp = [[False for i in range(K + 1)] for j in range(N + 1)]
        dp[0][0] = True
        for i in range(1, N):
            for j in range(K + 1):
                if dp[i - 1][j] or (j >= a2[i - 1] and dp[i - 1][j - a2[i - 1]]):
                    dp[i][j] = True
        result = False
        for j in range(K-a[s], K):
            if dp[N-1][j]:
                result = True
                break
        if result:
            cnt += 1
    else :
        cnt +=1


print(N-cnt)

Submission status: Time Limit Exceeded

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

card_list = [int(i) for i in input().split() if int(i) < K]
card_list.sort(reverse=True)

bitset = [0]*K
bitset[0] = 1

ans = 0
for card in card_list:
    ans += 1
    for i in range(K-card, K):
        if bitset[i] == 1:
            ans = 0
            break
    for i in reversed(range(K-card)):
        if bitset[i] == 1:
            bitset[i + card] = 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#### TLE ####

n, k = map(int, input().split())
a = sorted((filter(lambda x: x < k, map(int, input().split()))))


def check(start, end, l):
    s = set()
    s.add(0)
    for i in l:
        for x in s.copy():
            if start <= i + x and i + x < end:
                return True
            if i + x < start:
                s.add(i + x)
    return False


result = 0
for i in range(len(a)):
    b = a.copy()
    b.pop(i)
    if not check(k - a[i], k, b):
        result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(filter(lambda x: x < k, map(int, input().split())))


def check(start, end, l):
    s = set()
    s.add(0)
    for i in l:
        for x in s.copy():
            if start <= i + x and i + x < end:
                return True
            s.add(i + x)
    return False


result = 0
for i in range(len(a)):
    b = a.copy()
    b.pop(i)
    if not check(k - a[i], k, b):
        result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import bisect
import sys

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
l = bisect.bisect_left(a, k)
if l == 0:
    print(0)
    sys.exit()
    
a = a[0:l]

stf = [[False for j in range(k)] for i in range(l)]
stb = [[False for j in range(k)] for i in range(l)]

stf[0][a[0]] = True
stf[0][0] = True
for i in range(1, l):
    for x in range(k):
        if x - a[i] >= 0:
            stf[i][x] = stf[i - 1][x] or stf[i - 1][x - a[i]]
        else:
            stf[i][x] = stf[i - 1][x]


stb[l - 1][a[l - 1]] = True
stb[l - 1][0] = True
for i in range(l - 2, -1, -1):
    for x in range(k):
        if x - a[i] >= 0:
            stb[i][x] = stb[i + 1][x] or stb[i + 1][x - a[i]]
        else:
            stb[i][x] = stb[i + 1][x]

cc = 0
for i in range(l):
    found = False
    for x in range(k - a[i], k):
        if i == 0:
            if stb[1][x] == True:
                found = True
                break
        elif i == l - 1:
            if stf[l - 2][x] == True:
                found = True
                break
        else:
            for y in range(x + 1):
                if stf[i - 1][y] and stb[i + 1][x - y]:
                    found = True
                    break

            if found:
                break

    if not found:
        cc += 1
    else:
        break
        
print(cc)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

n,k = map(int,input().split())
a = list(map(int, input().split()))
a = list(reversed(sorted(a)))
nec = 0
for i in range(n):
    s = 0
    for j in range(i,n):
        s += a[j]
        if s >= k:
            nec = max(nec,j+1)
            s -= a[j]

print(n-nec)

Submission status: Time Limit Exceeded

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

        # 組み合わせ全通り
        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))
                    checked.append(d)
            else:
                pass
    ans = list(set(discard)-set(hold))
    o = len(ans)
print(o)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import sys
import bisect

sys.setrecursionlimit(10000)

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
i = bisect.bisect_left(a, k)
a = a[0:i]

ct = {}
ad = []
prevnum = 0
cc = 1
for i in a:
    if prevnum != i:
        ct[prevnum] = cc

        ad.append(i)
        prevnum = i
        cc = 1
    else:
        cc += 1
else:
    ct[prevnum] = cc

a = ad

#print(a)
#print(ct)


def getSumComb(a, idx, cur, st, minsum, maxsum):
    pairs = []
    num = a[idx]
    c = ct[num]
    for i in range(0, c + 1):
        if cur + num * i < minsum:
            stc = dict(st)
            if i > 0:
                stc[num] = i
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        stc,
                                        minsum,
                                        maxsum))                 
        elif minsum <= cur + num * i < maxsum:
            stc = dict(st)            
            if i > 0:
                stc[num] = i            
            stcc = dict(stc)
            if i > 0:
                pairs.append((cur + num * i, stc))
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        stcc,
                                        minsum,
                                        maxsum))
        elif maxsum <= cur + num * i:
            break
    
    return pairs

if len(a) > 0:
    pairs = getSumComb(a, 0, 0, {}, k - a[-1], k)
else:
    pairs = []
    
pairs = sorted(pairs, key=lambda p: p[0])
pks = [pairs[i][0] for i in range(len(pairs))]
#print(pairs)

nn = 0
for num in a:
    minsum = k - num
    idx = bisect.bisect_left(pks, minsum)
    found = False
    for i in range(idx, len(pairs)):
        if pairs[i][1].get(num, 0) < ct[num]:
            found = True
            break

    if not found:
      nn += ct[num]  

print(nn)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/local/bin/python3

import sys
import bisect

sys.setrecursionlimit(10000)

(n, k) = tuple(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
a = sorted(a)
i = bisect.bisect_left(a, k)
a = a[0:i]

ct = {}
ad = []
prevnum = 0
cc = 1
for i in a:
    if prevnum != i:
        ct[prevnum] = cc

        ad.append(i)
        prevnum = i
        cc = 1
    else:
        cc += 1
else:
    ct[prevnum] = cc

a = ad

#print(a)
#print(ct)


def getSumComb(a, idx, cur, sl, minsum, maxsum):
    pairs = []
    num = a[idx]
    c = ct[num]
    for i in range(0, c + 1):
        if cur + num * i < minsum:
            slc = sl[:]            
            for j in range(i):
                slc.append(num)
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slc,
                                        minsum,
                                        maxsum))                 
        elif minsum <= cur + num * i < maxsum:
            slc = sl[:]
            for j in range(i):
                slc.append(num)
            slcc = slc[:]
            if i > 0:
                pairs.append((cur + num * i, slc))
            if idx + 1 < len(a):
                pairs.extend(getSumComb(a,
                                        idx + 1,
                                        cur + num * i,
                                        slcc,
                                        minsum,
                                        maxsum))
        elif maxsum <= cur + num * i:
            break
    
    return pairs

if len(a) > 0:
    pairs = getSumComb(a, 0, 0, [], k - a[-1], k)
else:
    pairs = []
    
pairs = sorted(pairs)

#print(pairs)

nn = 0
for num in a:
    minsum = k - num
    p = (minsum, [])
    idx = bisect.bisect_left(pairs, p)
    found = False
    for i in range(idx, len(pairs)):
        if pairs[i][1].count(num) < ct[num]:
            found = True
            break

    if not found:
      nn += ct[num]  

print(nn)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		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
		if z == 0:
			iranaiko.append(a)
print(N - len(need))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
			

print(N - len(need))

Submission status: Time Limit Exceeded

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

print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		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
		if z == 0:
			iranaiko.append(a)
print(N - len(need))

Submission status: Time Limit Exceeded

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(' ')

for kosuu in range(N + 1):
    if kosuu == 0:
        b = 1
    else:
        for kaishi in range(N - kosuu + 1):
            taisho = []
            for k in range(kaishi,kaishi + kosuu):
                taisho.append(k)
            sumTaisho = 0
            for taishoNakami in taisho:
                sumTaisho = sumTaisho + int(inputLines2StrAry[taishoNakami])
            if sumTaisho >= K:
                a.append(taisho)

dame = [0] * N
dameShikii = 0
count = 0

for target in a:
    for targetNakami in target:
        dame[targetNakami] = dame[targetNakami] + 1
    targetCount = len(target)
    dameShikii = dameShikii + targetCount
    for banme in range(targetCount):
        sumTargetNumber = 0
        for j in target:
            sumTargetNumber = sumTargetNumber + int(inputLines2StrAry[j])
        if sumTargetNumber - int(inputLines2StrAry[target[banme]]) >= K:
            dame[target[banme]] = dame[target[banme]] - 1

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a)
	else:
		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: Memory Limit Exceeded

Solution code:
import numpy as np

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

dp_left = np.zeros((N + 1, K), dtype=bool)
dp_right = np.zeros((N + 1, K), dtype=bool)
dp_left[0, 0] = 1
dp_right[N, 0] = 1

for i in range(N):
    dp_left[i + 1] = dp_left[i]
    dp_right[N - i - 1] = dp_right[N - i]
    if (a := A[i]) < K:
        dp_left[i + 1, a:] |= dp_left[i, :-a]
    if (a := A[N - i - 1]) < K:
        dp_right[N - i - 1, a:] |= dp_right[N - i, :-a]

left_true = [np.nonzero(x)[0] for x in dp_left]
del dp_left
right_true = [np.nonzero(x)[0] for x in dp_right]
del dp_right

ans = 0
for i, a in enumerate(A):
    ss = np.searchsorted(right_true[i + 1], K - left_true[i]) - 1
    if all(right_true[i + 1][ss] + left_true[i] + a < K):
        ans += 1
print(ans)

Submission status: Memory Limit Exceeded

Solution code:
import numpy as np

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

dp_left = np.zeros((N + 1, K), dtype=bool)
dp_right = np.zeros((N + 1, K), dtype=bool)
dp_left[0, 0] = 1
dp_right[N, 0] = 1

for i in range(N):
    dp_left[i + 1] = dp_left[i]
    dp_right[N - i - 1] = dp_right[N - i]
    if (a := A[i]) < K:
        dp_left[i + 1, a:] |= dp_left[i, :-a]
    if (a := A[N - i - 1]) < K:
        dp_right[N - i - 1, a:] |= dp_right[N - i, :-a]

left_true = [np.nonzero(x)[0] for x in dp_left]
right_true = [np.nonzero(x)[0] for x in dp_right]
ans = 0
for i, a in enumerate(A):
    ss = np.searchsorted(right_true[i + 1], K - left_true[i]) - 1
    if all(right_true[i + 1][ss] + left_true[i] + a < K):
        ans += 1
print(ans)

Submission status: Memory 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 = [[0]]
    for a in As:
        ndp = []
        nonzero = []
        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.append(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 nonzero:
                t = K-y-a-1
                if acc[K-y-1] > acc[t if t >= 0 else -1]:
                    break
            else:
                ans += 1
        acc = list(accumulate(dp)) + [0]
    
    print(ans)

main()

Submission status: Memory 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):
            t = pdp[i] if i < a else pdp[i] + pdp[i-a]
            ndp.append(0 if t == 0 else 1)
        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):
            t = pdp[i] if i < a else pdp[i] + pdp[i-a]
            ndp.append(0 if t == 0 else 1)
        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: Memory Limit Exceeded

Solution code:
import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = [0] + LI()


dp1 = [[0]*K for _ in range(N+1)]  # dp1[i][j] = A1~Aiを用いてjを作れるか
dp1[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(K):
        if j >= a:
            dp1[i][j] = dp1[i-1][j] | dp1[i-1][j-a]
        else:
            dp1[i][j] = dp1[i-1][j]

dp2 = [[0]*K for _ in range(N+2)]  # dp2[i][j] = Ai~ANを用いてjが作れるか
dp2[N+1][0] = 1
for i in range(N,0,-1):
    a = A[i]
    for j in range(K):
        if j >= a:
            dp2[i][j] = dp2[i+1][j] | dp2[i+1][j-a]
        else:
            dp2[i][j] = dp2[i+1][j]

from itertools import accumulate

ans = 0
for i in range(1,N+1):
    B1,B2 = dp1[i-1],dp2[i+1]
    C2 = list(accumulate(B2))
    for j in range(0,K):
        if j < K-A[i]:
            if B1[j] & (C2[K-1-j]-C2[K-A[i]-j-1] > 0):
                ans += 1
                break
        else:
            if B1[j]:
                ans += 1
                break

print(N-ans)

Submission status: Memory Limit Exceeded

Solution code:
def partial_solution(N, K, A):
    # O(K * N**2)解法
    #     「aが不必要」
    #     ＝「aを含む良い集合の数字の和は K+a 以上」
    #     ＝「a以外の数字の組み合わせで K-a ～ K-1 は作れない」
    if N == 1:
        return 0
    cnt = 0
    for i in range(N):
        # dp[n][k]: n番目（1-indexed）までの数字の和でkを作れるか否か
        dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
        dp[0][0] = 1
        for j in range(N):
            a = A[j]
            if j == i:
                for k in range(K + 1):
                    # i番目（0-indexed）のAは使わない
                    dp[j + 1][k] = dp[j][k]
            else:
                for k in range(K + 1):
                    v = dp[j][k]
                    if k >= a:
                        v = max(v, dp[j][k - a])
                    dp[j + 1][k] = v
        lb, ub = max(0, K - A[i]), K - 1
        if sum(dp[N][lb:(ub + 1)]) == 0:
            cnt += 1
    return cnt


def solution(N, K, A):
    # O(K * N)解法
    #     partial_solutionの改良。
    #    「a以外の数字の組み合わせで作れる数字」を考えるため、両方向からdpテーブルを作る。
    if N == 1:
        return 0
    # dp1[i][k]: i番目（0-indexed）以前の数字の和でkを作れるか否か
    # dp2[j][k]: j番目（0-indexed）以降の数字の和でkを作れるか否か
    # iについてのfor loopで
    #     dp[j][k] = dp1[j][k] (j < i)
    #              = dp2[j][k] (j >= i)
    # となるように更新していく
    dp = [[0 for _ in range(K)] for _ in range(N)]  # 最初はdp2で初期化
    dp[N - 1][0] = 1
    if A[N - 1] < K:
        dp[N - 1][A[N - 1]] = 1
    for j in range(N - 2, -1, -1):
        for k in range(K):
            dp[j][k] = dp[j + 1][k]
            if k >= A[j]:
                dp[j][k] = max(dp[j][k], dp[j + 1][k - A[j]])
    # 「A[i] 以外の数字の組で K-A[i] ～ K-1 は作れない」ものの数を数える
    cnt = 0
    for i in range(N):
        # 次の式を満たす(x, y)が存在しなければA[i]は不必要：
        #     K - A[i] <= x + y <= K - 1
        #         x: ～i-1の要素, y: i+1～の要素
        a = A[i]
        if i == 0:
            if max(dp[1][max(0, K - a):K]) == 0:
                cnt += 1
            # dp1の反映
            for k in range(K):
                dp[0][k] = 0
            dp[0][0] = 1
            if a < K:
                dp[0][a] = 1
        elif i == N - 1:
            if max(dp[N - 2][max(0, K - a):K]) == 0:
                cnt += 1
        else:
            # dp2の累積和
            for k in range(1, K):
                dp[i + 1][k] += dp[i + 1][k - 1]
            unnecessary = True
            for x in range(K):
                if dp[i - 1][x] == 0:
                    continue
                # K - A[i] - x <= y <= K - 1 - x なるyの存在をチェック
                if 0 < K - a - x:
                    # dp[i + 1]はdp2の累積和になってる
                    if dp[i + 1][K - 1 - x] - dp[i + 1][K - a - x - 1] > 0:
                        unnecessary = False
                        break
                elif K - a - x <= 0 <= K - 1 - x:
                    if dp[i + 1][K - 1 - x] > 0:
                        unnecessary = False
                        break
            if unnecessary:
                cnt += 1
            # dp1の反映
            for k in range(K):
                dp[i][k] = dp[i - 1][k]
                if k >= a:
                    dp[i][k] = max(dp[i][k], dp[i - 1][k - a])
    return cnt


def check():
    import random
    random.seed(0)
    for N in range(1, 102, 10):
        for K in range(1, 102, 10):
            A = random.choices(range(1, 200+1), k=N)
            print('Checking: N={}, K={}'.format(N, K))
            sol = solution(N, K, A)
            psol = partial_solution(N, K, A)
            print('Sol: {}, Partial sol:{}'.format(sol, psol))
            assert sol == psol
    print('OK')


def main():
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    print(solution(N, K, A))


if __name__ == '__main__':
    main()
    # check()