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

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)  


def det(t):
  a = A[t]
  if a >= K:
    return False
  DP_rev = [0 for _ in range(K)] #戻すDP!!!
  ans = True
  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:
      ans = False
      break
  del DP_rev
  return ans

lt = 0
rt = N-1
if not det(lt):
  print(0)
  sys.exit()
if det(rt):
  print(rt+1)
  sys.exit()

while rt - lt > 1:
  ct = (lt + rt) // 2
  if det(ct):
    lt = ct
  else:
    rt = ct
print(rt)

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    
    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(N):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                # print(j - A[i])
                rdp2[j] = 1
                rdp_shift[j] = i
                # print(rdp_shift)
        rdp = rdp2
    # print(rdp_shift)
    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # ここで一つ一つチェックしている！！
        # A[i]が不要かチェック
        for j in range(K):
            S[j + 1] = S[j]
            # print(N - i, rdp_shift[j])
            if rdp_shift[j] <= N - i:
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            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)
            if rval > 0:
                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)
    # print(S)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
ans = n
s, cnt = 0, 0
for i in a:
    cnt += 1
    if s + i < k:
        s += i
    else:
        ans = n - cnt
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, k = tin()
	#s = input()	
	al = lin()
	al.sort(reverse = True)
	ss=sum(al)
	arrive=[0]*k
	arrive[0]=1
	useful_set=set()
	for v in al:
		ss -= v
		u_max=0
		if v >=k:
			useful_set.add(v)
			continue
		for i, _ in enumerate(arrive):
			p = k-i-1
			is_on = arrive[p]
			if is_on==1 and p+v >= k:
				useful_set.add(v)
				u_max=k
			elif is_on==1:
				arrive[p+v] = 1
				u_max=max(u_max, p+v)
		if u_max + ss >= k:
			useful_set.add(v)
	ret=0
	for v in al:
		if v not in useful_set:
			ret += 1
	return ret
			
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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 = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [0]*K  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K-1,-1,-1):
            if j >= b:
                dp[j] |= dp[j-b]
            else:
                dp[j] = dp[j]
    if sum(dp[j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

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 = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K):
            if j >= b:
                dp[i%2][j] = dp[1-i%2][j] | dp[1-i%2][j-b]
            else:
                dp[i%2][j] = dp[1-i%2][j]
    if sum(dp[(N-1) % 2][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, K = map(int, input().split())
A = list(sorted(map(int, input().split())))

def check(x):
    if A[x] >= K:
        return True
    dp = [False] * (K + 1)
    dp[0] = True
    for j, a in enumerate(A):
        if j == x:
            continue
        for i in range(K, 0, -1):
            if i >= a:
                dp[i] |= dp[i - a]
    for i in range(K - A[x], K):
        if dp[i]:
            return True
    return False
left = -1
right = N
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
A = sorted(list(map(int,input().split())))[::-1]
S = 0
ans = 0

for a in A:
  if S+a<K:
    S+=a
    ans+=1
  else:
    ans=0

print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
def input(): return sys.stdin.readline().strip()

def main():
    N, K = map(int, input().split())
    A = [0] + list(map(int, input().split()))
    """
    （aが不要なカード）＝（A-{a}からK-a以上の最小の部分和を取った時、それがK以上）
    まで言い換えてドボン。。。
    部分和の全列挙しなくても和がKまでで打ち切っていいんだから、ここでdpの発想が出なかったのは切腹。
    まずは部分点解法を実装してみる。

    →次に二分探索でdpを行う回数を削減する。ai <= ajに対してajが不要ならばaiも不要なことが対偶を取って分かる。
    そこでAをソートしたうえで必要と不要の境目を見つければよい。

    →PypyだとO(NKlogN)は通らなかったので、O(NK)解法を実装。
    一度二分探索できる話は忘れて、A-{a}から作れる部分和は(aの左側からの部分和)+(aの右側からの部分和)と
    かけることに注意すれば、左側からとれる部分和と右側からとれる部分和を前計算しておけばよい。
    rdpのテーブルメモリが重くてMLEするので（信じられん）、rdp_shiftに1になった瞬間のiを記録することにする。
    """
    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):
        rdp2 = [0] * K
        for j in range(K):
            if rdp[j] == 1:
                rdp2[j] = 1
            elif (j >= A[-i] and rdp[j - A[-i]] == 1):
                rdp2[j] = 1
                rdp_shift[j] = i
        rdp = rdp2

    ldp = [0] * K  # ldp[i][j] = (a1,...,aiの部分和でjを作れるか)
    ldp[0] = 1
    S = [0] * (K + 1)
    ans = 0
    for i in range(1, N + 1):
        # A[i]が不要かチェック
        for j in range(K):
            S[j + 1] = S[j]
            if rdp_shift[j] <= N - i:
                S[j + 1] += 1
        no_need = True
        for lval in range(K):
            if ldp[lval] == 0: continue
            rval = S[K - lval] - S[max(0, K - A[i] - lval)]
            if rval > 0:
                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)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    A.sort()
    mask = (1 << K) - 1

    noneed = -1; need = N
    while(need-noneed>1):
        #print(noneed,need)
        i = (need+noneed)//2
        if A[i]>=K:
            is_need = True
        else:
            dp = 1
            for j in range(N):
                a = A[j]
                if a>K:
                    break
                if i == j:
                    continue
                dp |= ((dp << a) & mask)
            # print(dp,mask)

            is_need = (dp > mask>>A[i])

            # print(is_need,i)

        if is_need:
            need = i
        else:
            noneed = i

    ans = noneed + 1

    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(lambda x: min(int(x), k+1), input().split()))
a.sort()
mask = (1<<(k+1)) - 1
def sub(ii):
    dp = 1
    for i in range(n):
        if i==ii:
            continue
        dp |= (dp<<a[i]) & mask
#         for j in range(k-1, a[i]-1, -1):
#             dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

Submission status: Accepted

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

ans = 0
sum = 0
cnt = 0
for i in range(N):
  a = A[i]
  if sum+a>=K:
    ans += cnt+1
    cnt = 0
  else:
    sum += a
    cnt += 1
    
print(N-ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,K = IL()
A = IL()
A.sort(reverse=True)

ans = 0
now = 0
cnt = 0
for i in range(N):
  a = A[i]
  if now+a>=K:
    ans += cnt+1
    cnt = 0
  else:
    now += a
    cnt += 1
    
print(N-ans)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=sorted(filter(lambda x:x<K,list(map(int,input().split()))))
N=len(A)
if N==0:
  print(0)
  exit()
def judge(x):
  DP=1
  Z=(1<<K)-1
  for i in range(N):
    if i!=x:
      DP=((DP|(DP<<A[i]))&Z)
  r=0
  for i in range(K-A[x],K):
    r|=(DP&(1<<i))
  return r

if judge(0):
  print(0)
  exit()
L,R,M=1,N,0
while L!=R:
  M=(L+R)//2
  if judge(M)==0:
    L=max(L+1,M)
  else:
    R=M
print(L)

Submission status: Accepted

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
    nn=biser(list(range(N)),isunnec)+1
    print(nn)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def biser(lst,func):
    n=len(lst)
    nh=n//2
    if n==1:
        if func(lst[0]):
            return lst[0]
        else:
            return -1
    if func(lst[nh]):
        return biser(lst[nh:],func)
    else:
        return biser(lst[:nh],func)

def mkns(a,s,m):
    if a==0:
        return s
    else:
        return (((s+1)<<a)|s) & m

def main():
    N,K=map(int,sys.stdin.readline().strip().split())
    a=list(map(int,sys.stdin.readline().strip().split()))
    a.sort()
    ss=[0]*(N+1)
    pm=(1<<K)-1
    mask=lambda c:(1<<K)-(1<<c)
    nn=0
    def isunnec(i):
        if a[i]>=K:
            return False
        for j in range(i+1,N):
            if a[j]>=K:
                break
            ss[i]=(((ss[i]+1)<<a[j])|ss[i]) & pm
        # print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        if ss[i]&mask(K-a[i])==0:
            return True
        return False
    
    for i in range(N):
        if a[i]>=K:
            break
        ss[i+1]=(((ss[i]+1)<<a[i])|ss[i]) & pm
        #if isunnec(i):
        #     nn+=1
        #for j in range(i+1,N):
        #    if a[j]>=K:
        #        break
        #    ss[i]=mkns(a[j],ss[i],pm)
        ##print(bin(ss[i]), bin(mask(K-c)),ss[i]&mask(K-c))
        #if ss[i]&mask(K-a[i])==0:
        #    nn+=1
    #m=len(list(filter(lambda x:x<K, a)))
    nn=biser(list(range(N)),isunnec)+1
    #print(list(map(bin,ss)))
    print(nn)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#4 9
#1 3 5 6
#の時に1（正解は0）と出力されるがACになる

N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a=list(map(int, input().split()))
a.sort()
ans = N
t = 0
for i in range(N-1, -1, -1) :
  if t+a[i] < K:
    t += a[i]
  else:
    ans = min(ans, i)
print(ans)

Submission status: Accepted

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

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def check(x):
    dp = np.zeros(k, np.bool)
    dp[0] = True
    for e in a[:x] + a[x+1:]:
        dp[e:] |= dp[:-e]

    return dp[-a[x]:].any()


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

a.sort()

lb = -1
ub = n
while ub - lb > 1:
    m = (lb + ub) // 2
    if check(m):
        ub = m
    else:
        lb = m

print(ub)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k+1,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]]) 
  return any(dp[max(0,k-a[t]):k])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
import numpy as np
def bisearch(t):
  dp=np.full(k,False)
  dp[0]=True
  for i in range(n):
    if i==t:continue
    dp[a[i]:] = np.logical_or(dp[a[i]:], dp[:-a[i]]) 
  return any(dp[max(0,k-a[t]):])
l,r=-1,n
while r-l>1:
  x=(l+r)//2
  if bisearch(x):
    r=x
  else:
    l=x
print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline


def solve(mid):
    """のぞいてもいいカードならTrueを返す"""
    dp = 1
    mask = (1 << k) - 1
    if k <= a[mid]:
        return False
    for i, weight in enumerate(a):
        if i == mid:
            continue
        dp |= dp << min(weight, k + 10)
        dp &= mask
    return dp >> (k - a[mid]) == 0
     

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

a.sort()
ok = 0
ng = n
if not solve(ok):
    print(0)
    exit()

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid

print(ok + 1)

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,K = map(int,input().split())
A = list(map(int,input().split()))

A.sort()

ans = N
total = 0

for i in range(N):
    # 後ろ(大きい方) からみていく
    a = A[N-1-i]
    # 合計に加えても K を超えないなら, 最小の部分集合に必要
    if total + a < K:
        total += a
    # そうでない場合, 不要
    else:
        ans = min(ans, N-1-i)

print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [0]+sorted(filter(lambda x: x < k, map(int,input().split())))
n = len(a)

def search(m):

    dp = [1] + [0]*k
    for i in range(n):
        if i == m:
            continue
        for j in range(k,a[i]-1,-1):
            dp[j] |= dp[j-a[i]]
    for i in range(k-a[m],k):
        if dp[i]:
            return True
    return False
le = 0
ri = n


while ri > le+1:
    m = (ri+le)//2

    if search(m):
        ri = m
    else:
        le = m

print(le)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=1)
    dp0=[1]*N
    dp1=[1]*N
    mask=(1<<K)-1
    for i in range(N-1):
        if a[i]<K:
            dp0[i+1]=(dp0[i]|(dp0[i]<<a[i]))&mask
        else:
            dp0[i+1]=dp0[i]
        if a[N-i-1]<K:
            dp1[N-i-2]=(dp1[N-i-1]|(dp1[N-i-1]<<a[N-i-1]))&mask
        else:
            dp1[N-i-2]=dp1[N-i-1]
    ans=0
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    def solve(i):
        if a[i]<K:
            mask2=((1<<a[i])-1)<<(K-a[i])
            for j in range(dp0[i].bit_length()):
                if j>mask2.bit_length():
                    return True
                if (dp0[i]>>j)&1:
                    if dp1[i]&(mask2>>j):
                        return True
        else:
            return True
        return False
    
    res=nibutan(-1,N)
    print(N-1-res)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
acc = list(accumulate(a))

def maxsum(ls,k):
  l = len(ls)
  if l==0:
    return 0
  dp = [0 for i in range(l+1)]
  dp[0] = 1
  for i in range(1,l+1):
    dp[i] = (dp[i-1]|(dp[i-1]<<ls[i-1]))&((1<<k)-1)
  for b in range(k-1,-1,-1):
    if dp[l] & 1<<b:
      return b

for i in range(n):
  if a[i]>=k:
    a = a[:i]
    break
n = len(a)
if acc[n-1] < k:
  print(n)
  exit()
sepa=[]
for i in range(n-1):
  if acc[i]<a[i+1]:
    sepa.append(i)
m=len(sepa)
if m==0:
  print(0)
  exit()
lf = 0
r = m-1
while lf<r:
  mid = (lf+r)//2
  x=sepa[mid]
  sumx = acc[x]
  if maxsum(a[x+1:],k)+sumx >= k:
    r = mid
  else:
    lf = mid+1
if r==0:
  t=sepa[0]
  if maxsum(a[t+1:],k)+acc[t]>=k:
    print(0)
  else:
    print(sepa[r]+1)
else:
  print(sepa[r]+1)

Submission status: Accepted

Solution code:

N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Submission status: Accepted

Solution code:

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = [0] * (K + 1)
    dp[0] = 1
    for i in range(N):
        a = A[i]
        if i == n or a >= K:
            continue
        for j in range(K, a - 1, -1):
            dp[j] |= dp[j - a]
    rst = any(dp[k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, a - 1, -1):
                dp[j] |= dp[j - a]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Accepted

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


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
def card(N,K,A):
    card = sorted(A,reverse=True)
    s=0
    ans=0
    for i in card:
        if s+i<K:
            s+=i
            ans+=1
        else:
            ans=0
    return ans
print(card(n,k,a))

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    from bisect import bisect_left as bl
    mod = 10**9+7
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    dp = np.zeros(k, dtype=np.int32)
    dp[0] = 1
    m = bl(a, k)
    for i in range(m):
        aa = a[i]
        dp[aa:] = (dp[aa:]+dp[:k-aa]) % mod

    def b_search(ok, ng):
        while abs(ok-ng) > 1:
            mid = (ok+ng)//2
            if value(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def value(i):
        if i == -1:
            return True
        if i == m:
            return False
        aa = a[i]
        dp2 = np.zeros(k, dtype=np.int32)
        dp2[:aa] = dp[:aa]
        for j in range(aa, k):
            dp2[j] = (dp[j]-dp2[j-aa]) % mod
        for j in range(k-aa, k):
            if dp2[j] != 0:
                return False
        return True
    print(b_search(-1, m)+1)


main()

Submission status: Accepted

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

alpha = sorted(alpha)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+alpha[i] < K :
        t += alpha[i]
    else :
        ans = min(ans, i)

print(ans)