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:
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
if f(0):
  print(0)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

Submission status: Accepted

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

l=N
for i in range(0,N):
    if A[i]>=K:
        l=i
        break
A=A[:l]
N=l
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        check=0
        for i in range(K-A[num],K):
            check+=pow(2,i)

        for i in range(1,N):
            check=check|(check>>test[i-1])

        return check%2==1
        

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort(reverse=True)
    #大きい方から順に足していき，K未満の最大の和を作っておく．これに対して，足してK以上になるのならそれは必要．K未満なら端しておく．
    #最終的に必要なもののうち最も小さいものがわかるはず
    
    temp=0
    ans=N
    for i in range(N):
        if temp+a[i]<K:
            temp+=a[i]
        else:
            ans=min(ans,N-i-1)
            
    print(ans)
    
    


main()

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
   
    
            
    
    
    

main()

Submission status: Accepted

Solution code:
def main():
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    N,K=MI()
    a=LI()#下位の連続するn枚が不要なはず
    a.sort()
    for i in range(N):#K以上ならば必要
        if a[i]>=K:
            a=a[:i]
            break
    N=len(a)
                    
                    
    #x番目の数が必要かどうかの判定 
    #必要なものだけで構成された集合をもとに考えれば良いわけではない，不必要な分も考えなければならない             
    def ch(x):
        
        #使い回す，i番目まででjが作れるか
        dp=[0]*K
        dp[0]=1
        for i in range(N):
            if i==x:
                continue
            else:
                for j in range(K-1,a[i]-1,-1):
                    dp[j]|=dp[j-a[i]]
                
                        
        #K未満K-a[x]以上が作れれば良い    
        for j in range(K-a[x],K):
            if  dp[j]:
                return True
        return False
            
    
                        
    ng=-1
    ok=N
    while abs(ok-ng)>1:
        med=(ok+ng)//2
        
        if ch(med):
            ok=med
        else:
            ng=med
            
    print(ng+1)
    
    
 
    

main()

Submission status: Accepted

Solution code:
def d_no_need(N, K, A):
    card = sorted(A, reverse=True)
    s = 0
    ans = 0
    for a in card:
        if s + a < K:
            s += a
            ans += 1
        else:
            ans = 0
    return ans

N,K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_no_need(N, K, A))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse = True)
t = 0
res = -1
for i in range(N):
  if t + a[i] < K: t += a[i]
  else: res = i
print(N - res - 1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter
    import numpy as np
    #mod = 1000000007

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

    def check(num):
        dp = np.zeros((N+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(N):
            # まとめて遷移
            dp[i+1] |= dp[i]
            #i番目のカードはスルー
            if i != num and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        return any(dp[N, -a[num]:])

    left = -1
    right = N
    while right - left > 1:
        mid = (left+right)//2
        if check(mid):
            right = mid
        else:
            left = mid
    print(right)

    # 間に合わないよ～><
    # def dp(num):
    #     dp = [[0]*(K) for _ in range(n)]
    #     dp[0][0] = 1
    #     b = a[:num]+a[num+1:] #N-1個
    #     for i in range(n-1):
    #         for j in range(K):
    #             if b[i]<=j:
    #                 dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
    #             else:
    #                 dp[i+1][j]=dp[i][j]
    #     return any(dp[n-1][K-a[num]:])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

def check(i): #i番目のカードを使わなかった時
    dp = np.zeros(K, dtype = np.bool)
    #dp[k]はkが作れる時True
    #保持する情報はTrue/Falseのみで良いので1次元DPを上書きしていく(1回でまとめて)
    dp[0] = True
    for j in itertools.chain(a[:i], a[i+1:]): #i番目の無いカードセット
        dp[j:] = np.logical_or(dp[j:], dp[:-j]) #ある数jを使うと、j以降のもの(N-j)個と前から(N-j)個のどちらかがTrueのものは作れる
    return any(dp[K-a[i]:]) #K-a[i]~K-1のうちどれか作れるならa[i]は必要=True

left = -1
right = N
while right - left > 1:
    mid = (right + left)//2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
'''
1枚抜いてDPをN枚についてやれば良い, がこれでは間に合わない
そこで必要不要の境界を二分探索で探す
するとO(N^2K)→O(NKlogN)となって間に合う

もう1つの方法は分からない
'''

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N,K = map(int, input().split())
    a = list(map(int, input().split()))
    a = sorted(a)
    a = a[:bisect_left(a, K)]
    n = len(a)


    import numpy as np
    def dp(omit):
        dp = np.zeros((n+1, K), dtype=np.bool)
        dp[0,0] = 1
        for i in range(n):
            # まとめて遷移
            dp[i+1] |= dp[i]
            if i != omit and a[i] < K:
                dp[i+1,a[i]:] |= dp[i,:K-a[i]]
        # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
        for j in range(max(0, K-a[omit]), K):
            if dp[n,j]:
                return True
        # なければ不要
        return False


    # def dp(num):
    #     dp = [[0]*(K) for _ in range(n)]
    #     dp[0][0] = 1
    #     b = a[:num]+a[num+1:] #N-1個
    #     for i in range(n-1):
    #         for j in range(K):
    #             if b[i]<=j:
    #                 dp[i+1][j] = dp[i][j-b[i]] or dp[i][j]
    #             else:
    #                 dp[i+1][j]=dp[i][j]
    #     return any(dp[n-1][K-a[num]:])

    left = 0
    right = n-1
    while left<=right:
        mid = (left+right)//2
        if dp(mid):
            right = mid-1
        else:
            left = mid+1
    print(right+1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from array import array
    input = sys.stdin.readline

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

    dp_left = [array('b', [0] * K) for _ in range(N + 1)]
    dp_right = [array('b', [0] * K) for _ in range(N + 1)]
    dp_left[0][0] = 1
    dp_right[0][0] = 1
    for i, a in enumerate(A):
        for j in range(K):
            if dp_left[i][j]:
                dp_left[i + 1][j] = 1
                if j + a < K:
                    dp_left[i + 1][j + a] = 1
    for i, a in enumerate(reversed(A)):
        for j in range(K):
            if dp_right[i][j]:
                dp_right[i + 1][j] = 1
                if j + a < K:
                    dp_right[i + 1][j + a] = 1

    ok = N
    ng = -1
    mid = (ok+ng)//2
    while ok - ng > 1:
        a = A[mid]
        if a >= K:
            ok = mid
            mid = (ok+ng)//2
            continue
        flg = 0
        l = 0
        r = K-1
        while True:
            if dp_right[N-mid-1][r]:
                break
            r -= 1
        while True:
            if K-a <= l+r < K:
                flg = 1
                break
            elif l+r >= K:
                r -= 1
                if r < 0:
                    break
                while True:
                    if dp_right[N-mid-1][r]:
                        break
                    r -= 1
            else:
                l += 1
                if l >= K:
                    break
                while True:
                    if dp_left[mid][l]:
                        break
                    l += 1
                    if l >= K:
                        break
        if flg:
            ok = mid
        else:
            ng = mid
        mid = (ok+ng)//2
    print(ng+1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = np.zeros(k, dtype=np.int64)
dp[0] = 1
for i in range(n):
  a = A[i]
  dp[a:] += dp.copy()[:-a]

ans = 0
for i in range(n):
  a = A[i]
  for j in range(max(0, k-a), k):
    temp = dp[j::-a*2].sum()
    if j >= a:
      temp -= dp[j-a::-a*2].sum()
    if temp:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def need(m):
        s=1
        for i in range(n):
            if i==m:continue
            s|=s<<aa[i]
            s&=mask
        #print(m,bin(s),bin(s>>k-aa[m]))
        if s>>k-aa[m]:return True
        return False

    n,k=MI()
    mask=(1<<k)-1
    #print(bin(mask))
    aa=LI()
    aa.sort()
    for i in range(n):
        if aa[i]>k:
            aa=aa[:i]
            break
    n=len(aa)
    #print(aa)
    l=-1
    r=n
    while l+1<r:
        m=(l+r)//2
        #while aa[m-1]==aa[m]:m-=1
        #print(m,aa[m],need(m))
        if need(m):r=m
        else:l=m
    print(l+1)

main()

Submission status: Accepted

Solution code:
N, K, *A = map(int, open(0).read().split())

A.sort(reverse=True)

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

print(ans)

Submission status: Accepted

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros(K, dtype=np.bool)
    prev = np.zeros(K, dtype=np.bool)
    dp[0] = prev[0] = 1
    for i in range(N):
        # まとめて遷移
        if i != omit and A[i] < K:
            prev[A[i]:] |= dp[:K-A[i]]
        dp = prev.copy()
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))

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 bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

Submission status: Accepted

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

A.sort()
for i in range(N):
    if A[i] >= K:
        A = A[:i]
        break

N = len(A)

def f(n): #aiが必要か不必要か判定
    dp = [0]*K
    dp[0] = 1
    for i in range(N):
        if i == n:
            continue
        for j in range(K-1, A[i]-1, -1):
            dp[j] |= dp[j-A[i]]
            
    res = False
    for j in range(K-A[n], K):
        if dp[j]:
            res = True
            break
    return res

l = -1
r = N
while r-l > 1:
    m = (l+r)//2
    if f(m):
        r = m
    else:
        l = m
        
print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def bisection(l,r,f,left=True,discrete=True):
    eps=1 if(discrete) else 10**-8
    if((not left)^f(r)): return r if(left) else r+1
    elif(left^f(l)): return l-1 if(left) else l
    while(r-l>eps):
        h=(l+r)//2 if(discrete) else (l+r)/2
        if((not left)^f(h)): l=h
        else: r=h
    return (l+r)/2 if(not discrete) else l if(left) else r

def resolve():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    A=[min(a,k+1) for a in A]
    A.sort()
    mask=(1<<k)-1

    def check(i): # i のカードを除いて、k-a[i]<=s<k が作れるか
        if(k-A[i]<0): return True
        dp=1
        for j in range(n):
            if(i==j): continue
            dp|=(dp<<A[j])
            dp&=mask

        dp>>=(k-A[i])
        return dp>0

    print(bisection(0,n-1,check,left=False))
resolve()

Submission status: Accepted

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
# bitsが大きくなりすぎないように前処理
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 

def main():
    # neededとなるindexの最小を求める
    lo = 0 # 可能最小
    hi = n # 可能最大 + 1
    while lo != hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i + 1

    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
# bitsが大きくなりすぎないように前処理
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= res << j
        res &= mask
    return res >> (k - a[i]) 
    # k - a[i]番目以降のbitが1つでも立っていれば、a[i]はneeded

def main():
    lo = 0
    hi = n - 1
    while lo <= hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i - 1
        else:
            lo = i + 1
    
    # hi: neededとなる最小のindex
    return hi + 1
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import chain

n, k, *a = map(int, sys.stdin.read().split())
*a, = map(lambda x: min(k, x), a)
a.sort()

mask = (1 << k) - 1
def is_needed(i):
    if a[i] == k:
        return True
    res = 1
    for j in chain(a[:i], a[i+1:]):
        res |= (res << j)
        res &= mask
    return res >> (k - a[i]) 

def main():
    lo = -1
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if is_needed(i):
            hi = i
        else:
            lo = i
    
    return hi
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import itertools

def fff(x):
    dp=[0]*k
    dp[0]=1
    for u in itertools.chain(a[:x],a[x+1:]):
        h=dp[:]
        for i in range(u,k):
            h[i]=h[i]|dp[i-u]
        dp=h
    cnt=0
    for i in range(max(0,k-a[x]),k):
        cnt+=dp[i]
    if cnt==0:
        return True
    else:
        return False

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
low=0
high=n-1
while high-low>1:
    mid=(high+low)//2
    if fff(mid):    #不必要
        low=mid
    else:
        high=mid

if fff(high):
    print(high+1)
elif fff(low):
    print(low+1)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

"""
・「必要」とは～～が存在
・x を含まない、[K-x,K) 内の総和が存在
・集合を指定すると、ある値段より上側
・全体としても単調性がある
"""

N,K,*A = map(int,read().split())

A = [x if x <= K else K + 1 for x in A]
A.sort()

mask = (1 << K) - 1

def test(x):
    # x番目は必要
    if A[x] > K:
        return True
    dp = 1
    for a in itertools.chain(A[:x], A[x+1:]):
        dp |= (dp << a)
        dp &= mask
    dp >>= (K - A[x])
    return (dp > 0)

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

answer = left + 1
print(answer)

Submission status: Accepted

Solution code:
import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp1 = np.zeros((N+1, K), dtype=bool)
dp1[0][0] = 1
for i, a in enumerate(A, 1):
    dp1[i, :] = dp1[i-1, :]
    dp1[i, a:] += dp1[i-1, :-a]
dp2 = np.zeros((N+1, K), dtype=bool)
dp2[N][0] = 1
for i, a in zip(range(N-1, -1, -1), A[::-1]):
    dp2[i, :] = dp2[i+1, :]
    dp2[i, a:] += dp2[i+1, :-a]
ans = 0
for a, d1, d2 in zip(A, dp1[:-1], dp2[1:]):
    if a >= K:
        continue
    d2_ = np.zeros(K+a, dtype=np.int32)
    d2_[a:] = d2
    d2_cum = np.cumsum(d2_)
    d2_diff = d2_cum[a:] - d2_cum[:-a]
    d = d2_diff[::-1] * d1
    if (d == 0).all():
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

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

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()

Submission status: Accepted

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

'''
notes:
1-->we include elems that are less than k  
2-->if some x is necessary all elems grtr than x are also necessary 
Base for some x to be necessary:: 
     atleast one of the sums in range [sm-x,sm) must be possible 
     excluding x  
now at any instance after traversing x elements 
we make sure that we have max posible sm <k 
now 
if x+sm <k 
    we cannot include this anyway 
otherwise
    we can make a set with {sm,x} now x is important 
BOOYAH (:
'''

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(map(int, input().split()))
l.sort(reverse=True)
# print(l)
a = 0
maisu = 0
end_maisu = 0
ans = 0
for i in range(n):
    maisu += 1
    a += l[i]
    if a >= k:
        a -= l[i]
        ans += 1
        end_maisu = maisu
        maisu -= 1
end_maisu -= 1
if end_maisu < 0:
    end_maisu = 0
# print(end_maisu - 1)
print(n - ans - end_maisu)

Submission status: Accepted

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] = np.logical_or(dp[i+1], dp[i])
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] = np.logical_or(dp[i+1,A[i]:], dp[i,:K-A[i]])
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))

Submission status: Accepted

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N, K = MAP()
A = LIST()

def check(omit):
    # 部分和DP
    dp = np.zeros((N+1, K), dtype=np.bool)
    dp[0,0] = 1
    for i in range(N):
        # まとめて遷移
        dp[i+1] |= dp[i]
        if i != omit and A[i] < K:
            dp[i+1,A[i]:] |= dp[i,:K-A[i]]
    # 今回の値A[omit]を足してKに到達できるような部分和があれば、これは必要
    for j in range(max(0, K-A[omit]), K):
        if dp[N,j]:
            return True
    # なければ不要
    return False

A.sort()
print(bisearch_min(-1, N, check))

Submission status: Accepted

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

A.sort()
# print(A)
A_set = list(set(A))

A_set = [int(i) for i in A_set]
A_set.sort()

#print(A_set)

le = -1
ri = len(A_set)
mid = (le + ri) // 2

while ri - le > 1:
    need = 0
    # print(le,ri,mid)

    DP = [0 for i in range(k)]
    DP[0] = 1
    jogai = 0
    for i in range(n):
        #print(DP)
        if jogai == 0 and A[i] == A_set[mid]:
            jogai = 1
        else:
            for p in range(k-1, A[i]-1, -1):
                DP[p] = int(DP[p-A[i]] or DP[p])
            # print(j)
    
            #print(DP)
        for p in range(max(0, k-A_set[mid]), k):
            if DP[p] == 1:
                need = 1
                break
        if need == 1:
            break
    
    if need == 1:
        ri = mid
    else:
        le = mid
    mid = (le + ri) // 2


ans = 0

if le != -1:
    jougen = A_set[le]
    for i in range(n):
        if A[i] <= jougen:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
s=r=0
for x in sorted(a)[::-1]:
	if s+x<k:
		s+=x
		r+=1
	else:
		r=0
print(r)

"""
Σ_[i=m,n]>kのときa(m)以降は凡て必要
(∵ a(i)が必要->a(i+1)が必要)
k-=Σ_[i=m+1,n]として操作を続ける
Σ_[i=1,r]<kとなったときa(r)までが不必要
"""

Submission status: Accepted

Solution code:
n,k,*a=map(int,open(0).read().split())
s=r=0
for x in sorted(a)[::-1]:
	if s+x<k:s+=x;r+=1
	else:r=0
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LS()
    if a == b:
        print("H")
    else:
        print("D")
    return

#B
def B():
    w, a, b = LI()
    a, b = min(a, b), max(a, b)
    if w + a >= b:
        print(0)
        return
    print(b-a-w)
    return

#C
def C():
    n = II()
    x = 0
    for i in range(1, 10 ** 5):
        x += i
        if n <= x:
            print(i)
            return
    return

#D
def D():
    n, k = LI()
    a = LI()
    a.sort()
    ok = n
    ng = -1
    def f(x):
        dp = [False] * (k)
        dp[0] = True
        kx = k - a[x]
        for i in range(n):
            if i == x: continue
            ai = a[i]
            for j in range(k - 1, ai - 1, -1):
                if dp[j - ai]:
                    dp[j] = True
                    if kx <= j:
                        return True
        for j in range(max(0, k - a[x]), k):
            if dp[j]:
                return True
        return False
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ng + 1)
    return

#Solve
if __name__ == '__main__':
    D()