Problem:


Score : 600 points

Problem Statement

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

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

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

Otherwise, card i is NOT unnecessary.

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

Constraints

All input values are integers.

1≤N≤5000

1≤K≤5000

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

Partial Score

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

Input

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

N K
a_1 a_2 ... a_N

Output

Print the number of the unnecessary cards.

Sample Input 1

3 6
1 4 3

Sample Output 1

1

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

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

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

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

Sample Input 2

5 400
3 1 4 1 5

Sample Output 2

5

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

Sample Input 3

6 20
10 4 3 10 25 2

Sample Output 3

3



Sample input:
3 6
1 4 3


Sample output:
1

Submission status: Time Limit Exceeded

Solution code:
import sys

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1

def check(mi):
    x = a[mi-1]
    if x >= k:
        return True
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    if sum(dp[k-x:k]):
        return True
    else:
        return False

if check(1):
    print(0)
    sys.exit()

if not check(n):
    print(n)
    sys.exit()

while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if check(mi):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    x = a[mi-1]
    if x >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        y = a[i]
        for j in range(k, -1, -1):
            if j >= y:
                dp[j] = dp[j] | dp[j-y]

    #print(dp)
    if sum(dp[k-x:k]):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    x = a[mi-1]
    if x >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[k-x:k]):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if a[mi-1] >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    if a[mi-1] >= k:
        ba = mi
        continue
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    #print(mi)
    dp = [False] * (k+1)
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    if sum(dp[max(0, k - a[mi-1]):k]):
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    #print(mi)
    dp = [False for _ in range(k+1)]
    dp[0] = True
    for i in range(n):
        if i == mi-1:
            continue
        for j in range(k, -1, -1):
            if j >= a[i]:
                dp[j] = dp[j] | dp[j-a[i]]

    #print(dp)
    needed = False
    for j in range(max(0, k - a[mi-1]), k):
        if dp[j] == True:
            needed = True
            break

    if needed:
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]
#print(a)
fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    #print(mi)
    dp = [[False for _ in range(k+1)] for _ in range(n+1)]
    dp[0][0] = True
    for i in range(n):
        for j in range(k+1):
            if i == mi-1:
                dp[i+1][j] = dp[i][j]
            elif j >= a[i]:
                dp[i+1][j] = dp[i][j] | dp[i][j-a[i]]
            else:
                dp[i+1][j] = dp[i][j]

    #print(dp)
    needed = False
    for j in range(max(0, k - a[mi-1]), k):
        if dp[-1][j] == True:
            needed = True
            break

    if needed:
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = [min(i, k) for i in sorted(list(map(int, input().split())))]

fr = 0
ba = n+1
while ba-fr > 1:
    mi = (ba+fr+1) // 2
    bitset = 1
    for i in range(n):
        if i == mi-1:
            continue
        bitset |= (bitset << a[i])
    needed = False
    j = max(0, k - a[mi-1])
    bitset >>= j
    while j < k:
        if (bitset&1) == 1:
            needed = True
            break
        bitset >>= 1
        j += 1

    if needed:
        ba = mi
    else:
        fr = mi

print(fr)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
migi = [[0]*k for i in range(n)]
hidari = [[0]*k for i in range(n)]
dp2 = [float("inf")]*n
matome = set()
matome.add(0)
hidari[0][0] = 1
for i in range(1,n):
  for j in list(matome):
    hidari[i][j] = 1
    if j + a[i-1] < k:
      matome.add(j + a[i-1])
      hidari[i][j + a[i-1]] = 1
matome = set()
matome.add(0)
migi[n-1][0] = 1
for i in range(n-2,-1,-1):
  for j in list(matome):
    migi[i][j] = 1
    if j + a[i+1] < k:
      matome.add(j + a[i+1])
      migi[i][j + a[i+1]] = 1
for i in range(n):
  m =[]
  h =[]
  for j in range(k):
    if migi[i][j]:
      m.append(j)
    if hidari[i][j]:
      h.append(j)
  now = len(h)-1
  for j in m:
    while True:
      if h[now] + j+a[i] >= k:
        dp2[i] = min(dp2[i],h[now]+j+a[i])
        if now == 0:
          break
        if h[now-1] + j+a[i] >= k:
          now -=1
        else:
          break
      else:
        break
ans = 0
for i in range(n):
  if dp2[i] - a[i] >= k:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
n,k = map(int,input().split())
a = list(map(int,input().split()))
migi = []
hidari = []
dp2 = [float("inf")]*n
matome = set()
matome.add(0)
hidari.append(deepcopy(matome))
for i in range(1,n):
  for j in list(matome):
    if j + a[i-1] < k:
      matome.add(j + a[i-1])
  hidari.append(deepcopy(matome))
matome = set()
matome.add(0)
migi.append(deepcopy(matome))
for i in range(n-2,-1,-1):
  for j in list(matome):
    if j + a[i+1] < k:
      matome.add(j + a[i+1])
  migi.append(deepcopy(matome))
migi = migi[::-1]
for i in range(n):
  m = list(migi[i])
  h = list(hidari[i])
  m.sort()
  h.sort()
  now = len(h)-1
  for j in m:
    while True:
      if h[now] + j+a[i] >= k:
        dp2[i] = min(dp2[i],h[now]+j+a[i])
        if now == 0:
          break
        if h[now-1] + j+a[i] >= k:
          now -=1
        else:
          break
      else:
        break
ans = 0
for i in range(n):
  if dp2[i] - a[i] >= k:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
dp = [set() for i in range(n)]
dp2 = [float("inf")]*n
matome = set()
matome.add(0)
for i in range(n):
  for j in list(matome):
    if j + a[i] >= k:
      dp2[i] = min(dp2[i],j+a[i])
    else:
      dp[i].add(j+a[i])
      matome.add(j+a[i])
  for j in range(i):
    for l in list(dp[j]):
      if l + a[i] >= k:
        dp2[j] = min(dp2[j],l+a[i])
      else:
        dp[j].add(l+a[i])
        matome.add(l+a[i])   
ans = 0
for i in range(n):
  if dp2[i] - a[i] >= k:
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


n,k = li()
a = li()
a = [ai for ai in a if ai <= k]
a.sort()


left = 0
right = len(a)+1

while right - left > 1:
    mid = (right+left) // 2
    ai = a[mid-1]
    ai_pass = True

    a_wo_ai = a[:mid-1] + a[mid:]
    
    dp = [[0 for _ in range(k)] for _ in range(len(a_wo_ai)+1)]
    dp[0][0] = 1
    
    
    for i, aj in enumerate(a_wo_ai):        
        for sm in range(k):
            dp[i+1][sm] += dp[i][sm]
            if sm-aj >= 0:
                dp[i+1][sm] += dp[i][sm-aj]
                
    if sum(dp[len(a_wo_ai)][k-ai:]) == 0:
        left = mid
    else:
        right = mid
        
            
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

n,k = li()
a = li()
a = [ai for ai in a if ai <= k]
a.sort()

left = 0
right = len(a)+1

while right - left > 1:
    mid = (right+left) // 2
    ai = a[mid-1]
    ai_pass = True

    a_wo_ai = [aj for aj in a]
    a_wo_ai.remove(ai)
    
    dp = [[0 for _ in range(k)] for _ in range(len(a_wo_ai)+1)]
    dp[0][0] = 1
    
    
    for i, aj in enumerate(a_wo_ai):        
        for sm in range(k):
            dp[i+1][sm] += dp[i][sm]
            if sm-aj >= 0:
                dp[i+1][sm] += dp[i][sm-aj]
                
    if sum(dp[len(a_wo_ai)][k-ai:]) == 0:
        left = mid
    else:
        right = mid
        
            
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()
a = [ai for ai in a if ai <= k]
a.sort()

cnt = Counter(a)
ans = 0

left = 0
right = len(a)+1

while right - left > 1:
    mid = (right+left) // 2
    ai = a[mid-1]
    ai_pass = True

    a_wo_ai = [aj for aj in a]
    a_wo_ai.remove(ai)
    
    dp = [[0 for _ in range(k)] for _ in range(len(a_wo_ai)+1)]
    dp[0][0] = 1
    
    
    for i, aj in enumerate(a_wo_ai):        
        for sm in range(k):
            dp[i+1][sm] += dp[i][sm]
            if sm-aj >= 0:
                dp[i+1][sm] += dp[i][sm-aj]
                
    if sum(dp[len(a_wo_ai)][k-ai:]) == 0:
        left = mid
    else:
        right = mid
        
            
print(left)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from collections import Counter

n,k = li()
a = li()
a = [ai for ai in a if ai <= k]
a.sort()

cnt = Counter(a)
ans = 0

for ai in a:
    ai_pass = True

    a_wo_ai = [aj for aj in a]
    a_wo_ai.remove(ai)
    
    dp = [[0 for _ in range(k)] for _ in range(len(a_wo_ai)+1)]
    dp[0][0] = 1
    
    
    for i, aj in enumerate(a_wo_ai):        
        for sm in range(k):
            dp[i+1][sm] += dp[i][sm]
            if sm-aj >= 0:
                dp[i+1][sm] += dp[i][sm-aj]
                
    if sum(dp[len(a_wo_ai)][k-ai:]) == 0:
        ans += 1
            

        
print(ans)

Submission status: Time Limit Exceeded

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

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

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

			#dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(K - 1, 0, -1):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				#if dp[k] == True:
					#dp2[k] = True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp[k] = True

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

			#print(dp)
			#dp = dp2

		return False


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


	print(bi_search(0, N - 1))

Submission status: Time Limit Exceeded

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

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

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

			dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[k] == True:
					dp2[k] = True
					if K - a[i] <= k:
						return True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp2[k] = True
						if K - a[i] <= k:
							return True

			#print(dp)
			dp = dp2

		return False


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


	print(bi_search(0, N - 1))

Submission status: Time Limit Exceeded

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

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

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

			dp2 = [False] * K
			#if b[j] < K:
				#dp[b[j]] = True
			for k in range(1, K):
				#if b[j] == K:
				#	return True
				#elif dp[j - 1][k] == True:
				if dp[k] == True:
					dp2[k] = True
				
				#elif k > b[j]:
				
				if k >= b[j]:
					#if dp[j - 1][k - b[j]] == True:
					if dp[k - b[j]] == True:
						#dp[j][k] = True
						dp2[k] = True

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

			#print(dp)
			dp = dp2

		return False


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


	print(bi_search(0, N - 1))

Submission status: Time Limit Exceeded

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

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

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

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

		return False


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


	print(bi_search(0, N - 1))

Submission status: Time Limit Exceeded

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

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

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

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

		return False


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


	print(bi_search(0, N - 1))

Submission status: Time Limit Exceeded

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

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


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

    # if n > 400: return 0

    def check(ai):
        aa = a[:]
        aa.remove(ai)
        # dp = [False] * k
        dp = [False] * (2*k)
        dp[0] = dp[k] = True

        for i in xrange(n-1):
            ofs0 = (i % 2) * k
            ofs1 = ((i+1)%2) * k
            for j in xrange(k):
                if dp[ofs0+j] and aa[i] + j < k:
                    dp[ofs1+aa[i]+j] = True

        if (n-1)%2 == 0:
            return any(dp[k-ai:k])
        else:
            return any(dp[2*k-ai:])

    au = list(set(a))
    au.sort(reverse=True)

    mi = -1
    ma = len(au)

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

    a.sort()
    if ma == len(au): return 0
    return bisect.bisect_right(a, au[ma])

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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


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

    # if n > 400: return 0

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

        for i in xrange(n-1):
            ofs0 = (i % 2) * k
            ofs1 = ((i+1)%2) * k
            for j in xrange(k):
                if dp[ofs0+j] and aa[i] + j < k:
                    dp[ofs1+aa[i]+j] = True

        if (n-1)%2 == 0:
            return any(dp[k-a[ind]:k])
        else:
            return any(dp[2*k-a[ind]:])

    mi = -1
    ma = n

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

    return n-ma

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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


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

    # if n > 400: return 0

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

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

        if (n-1)%2 == 0:
            return any(dp[k-a[ind]:k])
        else:
            return any(dp[2*k-a[ind]:])

    mi = -1
    ma = n

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

    return n-ma

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


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

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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


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

    # if n > 400: return 0

    def check(ind):
        aa = a[:]
        aa.pop(ind)
        # dp = [False] * k
        dp = [[False] * k for _ in xrange(2)]
        dp[0][0] = dp[1][0] = True

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

        return any(dp[(n-1)%2][k-a[ind]:])

    mi = -1
    ma = n

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

    return n-ma

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


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

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

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

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

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

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