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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
 
 
def main():
    n,k = LI()
    a = sorted(LI(), key=lambda x: -x)
    s = [set() for _ in range(k)]
    rs = set()
    for i in range(n):
        ai = a[i]
        if ai >= k:
            rs.add(i)
            continue
        for j in range(k-1,0,-1):
            sj = s[j]
            if sj:
                if j+ai < k:
                    s[j+ai] |= sj
                    s[j+ai].add(i)
                else:
                    rs |= sj
                    rs.add(i)
        s[ai].add(i)
 
    return n-len(rs)
 
 
print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,k = LI()
    a = sorted(LI())
    sa = sum(a)
    if sa < k:
        return n
    if sa - a[0] < k:
        return 0

    mi = 0
    ma = n-1

    def f(m):
        am = a[m]
        if am >= k:
            return True

        t = [False] * (k-am)
        t[0] = True
        tl = len(t)
        for i in range(n):
            if i==m:
                continue
            ai = a[i]
            for j in range(tl-1,-1,-1):
                if not t[j]:
                    continue
                if k <= j+ai:
                    continue
                if j+ai >= tl:
                    return True

                t[j+ai] = True

        return False

    while mi < ma:
        m = (mi+ma) // 2
        if f(m):
            ma = m
        else:
            mi = m+1

    return mi


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n,k = LI()
    a = sorted(LI(), key=lambda x: -x)
    s = [set() for _ in range(k)]
    rs = set()
    for i in range(n):
        ai = a[i]
        if ai >= k:
            rs.add(i)
            continue
        for j in range(k-1,0,-1):
            sj = s[j]
            if sj:
                if j+ai < k:
                    s[j+ai] |= sj
                    s[j+ai].add(i)
                else:
                    rs |= sj
                    rs.add(i)
        s[ai].add(i)

    return n-len(rs)


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
[n, k] = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]

a.sort()

if sum(a) < k:
  print(n)
  sys.exit()

s = 0
for i in range(len(a)):
  s += a[i]
  if s >= k:
    break

aa = [x for x in a if x < a[i]]
bb = [x for x in a if x < k]

cc = []
for i in range(len(aa)):
  c = bb[:i] + bb[i+1:]
  t = k - bb[i]
  c.reverse()
  #print(c)
  flg = 0
  j = 0
  s = 0
  f = [0 for x in range(len(c))]
  while True:
    f[j] = 1
    #print(c)
    #print(f)
    s += c[j]
    if s >= t and s < k:
      flg = 1
      #print(c)
      #print(f)
      break
    if s >= k:
      f[j] = 0
      s -= c[j]
    j += 1
    if j == len(c):
      ii = -1
      for jj in range(len(c) - 1):
        if f[jj] == 1:
          ii = jj
      if ii == -1:
        break
      else:
        for l in range(ii, len(c)):
          f[l] = 0
      j = ii + 1
      s = sum([c[l] * f[l] for l in range(len(c))])
  if flg== 0:
    cc.append(bb[i])
#print(cc)
print(len(cc))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
a.sort()
used=[False]*n
idx=n-1
cnt=0
while True:
    if idx-cnt<0:
        break
    tmp=sum(a[idx-cnt:idx+1])
    if tmp<k:
        cnt+=1
        continue
    for i in xrange(idx-cnt,idx+1):
        used[i]=True
    tmp-=a[idx-cnt]
    now=idx-cnt-1
    f=0
    while now>=0:
        if tmp+a[now]>=k:
            used[now]=True
            now-=1
        else:
            pre=now
            tmp1=a[now]
            if tmp+sum(a[0:now+1])<k:
                f=1
                break
            while now>=0 and tmp+tmp1<k:
                now-=1
                tmp1+=a[now]
            for j in xrange(now,pre+1):
                used[j]=True
            now=pre-1
    idx-=1
    cnt=0
ans=0
for i in xrange(n):
    if not used[i]:
        ans+=1
print ans

Submission status: Time Limit Exceeded

Solution code:
temp=input().split()
N=int(temp[0])
K=int(temp[1])
a=[int(i) for i in input().split()]
a.sort()
ans=N
#print(a)
for i in range(len(a)):
	if K<=a[i]:
		ans=i
		a=a[0:i]
		break
if ans==0:
	print(0)
else:
	a.reverse()
	setpoint=set()
	setpoint.add(0)
	setpoint.add(a[0])
	point=[0,a[0]]
	contents=[[0],[a[0]]]
	overpoint=[]
	overcontents=[]
	Len=2
	#print(ans)
	#print(a)
	for i in a[1:]:
		nextpoint=[]
		for j in range(len(point)):
			if K<=i+point[j]:
				overpoint+=[i+point[j]]
				overcontents+=[[i]+contents[j]]
				break#try
			else:
				setpoint.add(i+point[j])
				if Len!=len(setpoint):
					nextpoint+=[i+point[j]]
					contents+=[[i]+contents[j]]
		point.extend(nextpoint)
	needList=[]
	Length=len(overpoint)
	for i in range(Length):
		check=overpoint[i]-K
		for j in overcontents[i]:
			if check<j:
				needList+=[j]
	needList=set(needList)
	#print(needList)
	for i in needList:
		ans-=a.count(i)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
temp=input().split()
N=int(temp[0])
K=int(temp[1])
a=[int(i) for i in input().split()]
a.sort()
ans=N
#print(a)
for i in range(len(a)):
	if K<=a[i]:
		ans=i
		a=a[0:i]
		break
if ans==0:
	print(0)
else:
	a.reverse()
	point=[0,a[0]]
	contents=[[0],[a[0]]]
	overpoint=[]
	overcontents=[]
	#print(ans)
	#print(a)
	for i in a[1:]:
		for j in range(len(point)):
			if i+point[j] not in point:
				if K<=i+point[j]:
					overpoint+=[i+point[j]]
					overcontents+=[[i]+contents[j]]
					break#try
				else:
					point+=[i+point[j]]
					contents+=[[i]+contents[j]]
	needList=[]
	Length=len(overpoint)
	for i in range(Length):
		check=overpoint[i]-K
		for j in overcontents[i]:
			if check<j:
				needList+=[j]
	needList=set(needList)
	#print(needList)
	for i in needList:
		ans-=a.count(i)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(x) for x in raw_input().split()]
a = [int(x) for x in raw_input().split()]

p = [0] * (k + 1)
dp1 = [p]

for ai in a:
    c = p[:]
    for j in xrange(k + 1):
        if j >= ai:
            c[j] = max(p[j], p[j - ai] + ai)
    dp1.append(c)
    p = c

p = [0] * (k + 1)
dp2 = [p]

for ai in reversed(a):
    c = p[:]
    for j in xrange(k + 1):
        if j >= ai:
            c[j] = max(p[j], p[j - ai] + ai)
    dp2.append(c)
    p = c

ans = n
for i in xrange(n):
    r1 = dp1[i]
    r2 = dp2[n - 1 - i]
    for j in xrange(k):
        if r1[j] + r2[k - 1 - r1[j]] + a[i] >= k:
            ans -= 1
            break

print(ans)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

flag = [False]*N
dp = defaultdict(set)
dp[0] = set()

for i,a in enumerate(A):
  ndp = dp.copy()

  flipped = set()

  for s, used in dp.items():
    t = s+a - K
    if t >= 0:
      flag[i] = True
      for u in used:
        if t < A[u] and not flag[u]:
          flipped.add(u)
          flag[u] = True
    else:
      ndp[s+a] |= used
      ndp[s+a].add(i)

  if flipped:
    for v in ndp.values():
      v -= flipped

  dp = ndp

print(N - sum(flag))

Submission status: Time Limit Exceeded

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

small = 0
while small < n and a[small] < k:
    small += 1
n = small


cnt = 0
for c in range(n):
    able = [False for i in range(k)]
    able[0] = True
    for i in range(n):
        if c==i:
            continue
        for j in range(k-a[i]-1, -1, -1):
            if able[j]:
                able[j+a[i]] = True
    if not any(able[k-a[c]:k]):
        cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

flag = [False]*N
dp = defaultdict(set)
dp[0] = set()

for i,a in enumerate(A):
  ndp = dp.copy()

  flipped = set()

  for s, used in dp.items():
    t = s+a - K
    if t >= 0:
      flag[i] = True
      for u in used:
        if t < A[u] and not flag[u]:
          flipped.add(u)
          flag[u] = True
    else:
      ndp[s+a] |= used
      ndp[s+a].add(i)

  if flipped:
    for v in ndp.values():
      v -= flipped

  dp = ndp

print(N - sum(flag))

Submission status: Time Limit Exceeded

Solution code:
temp=input().split()
N=int(temp[0])
K=int(temp[1])
a=[int(i) for i in input().split()]
a.sort()
ans=N
#print(a)
for i in range(len(a)):
	if K<=a[i]:
		ans=i
		a=a[0:i]
		break
if ans==0:
	print(0)
else:
	point=[0,a[0]]
	contents=[[0],[a[0]]]
	overpoint=[]
	overcontents=[]
	#print(ans)
	#print(a)
	for i in a[1:]:
		for j in range(len(point)):
			if i+point[j] not in point:
				if K<=i+point[j]:
					overpoint+=[i+point[j]]
					overcontents+=[[i]+contents[j]]
				else:
					point+=[i+point[j]]
					contents+=[[i]+contents[j]]
	needList=[]
	Length=len(overpoint)
	for i in range(Length):
		check=overpoint[i]-K
		for j in overcontents[i]:
			if check<j:
				needList+=[j]
	needList=set(needList)
	#print(needList)
	for i in needList:
		ans-=a.count(i)
	print(ans)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

flag = [True]*N
dp = defaultdict(set)
dp[0] = set()

for i,a in enumerate(A):
  ndp = dp.copy()
  for s, used in dp.items():
    t = s+a - K
    if t >= 0:
      flag[i] = False
      for u in used:
        if t < A[u]:
          flag[u] = False
    else:
      ndp[s+a] |= used
      ndp[s+a].add(i)

  dp = ndp

print(sum(flag))

Submission status: Time Limit Exceeded

Solution code:
def read_ints():
    return [int(c) for c in input().strip().split()]

n, k = read_ints()
xs = read_ints()


def calc_avail(vals):
    avail = [[v == 0 for v in range(5001)] for i in range(n + 1)]
    for i, x in enumerate(vals):
        for fr in range(5001):
            avail[i+1][fr] |= avail[i][fr]
            to = fr + x
            if 0 <= to <= 5000:
                avail[i+1][to] |= avail[i][fr]
    return avail

left_avail = calc_avail(xs)
right_avail = calc_avail(reversed(xs))

ans = n
for i, x in enumerate(xs):
    if x >= k:
        ans -= 1
        continue
    lp, rp = 0, 5000
    while 0 <= lp <= 5000 and 0 <= rp <= 5000:
        if not left_avail[i][lp]:
            lp += 1
        elif not right_avail[n - i - 1][rp]:
            rp -= 1
        elif lp + rp < k - x:
            lp += 1
        elif lp + rp >= k:
            rp -= 1
        else:
            ans -= 1
            break

print(ans)

Submission status: Memory Limit Exceeded

Solution code:
n, k = map(int, raw_input().split())
a = map(int, raw_input().split())

dpl = [[0] * (k + 1) for _ in xrange(n)]
dpr = [[0] * (k + 1) for _ in xrange(n)]
for i in xrange(n):
    dpl[i][0] = 1
    dpr[i][0] = 1
dpl[0][min(k, a[0])] = 1
dpr[n - 1][min(k, a[n - 1])] = 1

for i in xrange(1, n):
    if a[i] > k:
        dpl[i][k] = 1
    for j in xrange(k + 1):
        if j - a[i] < 0:
            dpl[i][j] = min(1, dpl[i][j] + dpl[i - 1][j])
        else:
            dpl[i][j] = min(1, dpl[i - 1][j] + dpl[i - 1][j - a[i]])
for i in xrange(n):
    for j in xrange(k):
        dpl[i][j + 1] += dpl[i][j]

for i in xrange(n - 2, -1, -1):
    if a[i] > k:
        dpr[i][k] = 1
    for j in xrange(k + 1):
        if j - a[i] < 0:
            dpr[i][j] = min(1, dpr[i][j] + dpr[i + 1][j])
        else:
            dpr[i][j] = min(1, dpr[i + 1][j] + dpr[i + 1][j - a[i]])
for i in xrange(n - 1, -1, -1):
    for j in xrange(k):
        dpr[i][j + 1] += dpr[i][j]

ans = 0
for i in xrange(1, n - 1):
    ok = False
    if a[i] >= k: continue
    for j in xrange(k):
        if (j != 0) and (dpl[i - 1][j]  - dpl[i - 1][j - 1] == 0): continue
        lnum = j
        if lnum + a[i] >=k:
            ok=True
            break
        if dpr[i + 1][k - lnum -1] - dpr[i + 1][k - 1 - a[i] - lnum] > 0:
            ok =True
            break
    if ok: continue
    ans += 1
if a[0] < k:
    if dpr[1][k - 1] - dpr[1][k - a[0] - 1] == 0:
        ans += 1
if a[n - 1] < k:
    if dpl[n - 2][k - 1] - dpl[n - 2][k - a[n - 1] - 1] == 0:
        ans += 1
print ans

Submission status: Accepted

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

a.sort(reverse=True)
mask = (1<<k)-1
dp = 1
min_n = 10**10
for i in a:
    if(i >= k):
        min_n = i
        continue
    dp |= (dp<<i)
    if(dp > mask):
        min_n = i
        dp &= mask
         
ans = 0
for i in a:
    ans += (i < min_n)

print(ans)

Submission status: Accepted

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

a.sort(reverse=True)
dp = [False] * (k)
dp[0] = True
min_n = 10**10
for i in a:
    for j in range(k-1,-1,-1):
        if(dp[j]):
            if(j+i >= k):
                min_n = i
            else:
                dp[j+i] = True

ans = 0
for i in a:
    ans += (i < min_n)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

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

a.sort(reverse=True)

K = 2*k+1
mask = (1<<K)-1

dpl = [1]
dp = 1
for i in a:
    dp |= (dp<<i)&mask
    dpl.append(dp)

#print(dpl)
for i in range(n):
    x = dpl[n-1-i]<<a[n-1-i]
    mask = ((1<<a[n-1-i])-1)<<(k)
    #print(bin(x)[::-1])
    #print(bin(mask)[::-1])
    if x&mask:
        print(i)
        break
else: print(n)

Submission status: Accepted

Solution code:
n, k = map(int,input().split())
a = [k+1 if x > k else x for x in map(int,input().split())]
a.sort()
lef = [1]*n
rig = [1]*n
mask = (1 << (k+1)) - 1
for i in range(n-1):
  lef[i+1] = lef[i] | (lef[i] << a[i]) & mask
  rig[-i-2] = rig[-i-1] | (rig[-i-1] << a[-i-1]) & mask
ok = -1
ng = n
while ng - ok > 1:
  mid = (ng + ok) // 2
  if a[mid] >= k:
      ng = mid
      continue
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
b=list(map(int,input().split()))
b.sort()
a=[]
for i in range(N):
    if b[i]<K:
        a.append(b[i])
N=len(a)
ans=0
#print(bin((1<<K)>>1))
C=[1]
n=1
for i in range(N):
    n=n|n<<a[i]
    n%=(1<<K)
    C.append(n)
#print(C)
    #print(bin(n))
if N<=10:
    for i in range(N):
        n=C[i]
        for j in range(i+1,N):
            n=n|n<<a[j]
            n%=(1<<K)
        if n < (1<<K)>>a[i]:
            ans+=1
        else:
            break
    print(ans)
else:
    a+=[10**9]
    H=N
    L=0
    
    while abs(H-L)>4:
        Mid=(H+L)//2
        #print(H,Mid,L)
        n=1
        for i in range(N):
            if i==Mid:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[Mid]:    
            H=Mid
        else:
            L=Mid
    #print(H,L)        
    for j in range(max(0,L-5),N):
        n=1
        for i in range(N):
            if i==j:
                continue
            else:
                n=n|n<<a[i]
                n%=(1<<K)
        if n >= (1<<K)>>a[j]: 
            print(j)
            exit()
    print(N)

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:
from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    bitsets = [1<<(K-1)]
    bitset = 1<<(K-1)
    for B in Bs:
        bitset |= bitset>>B
        bitsets.append(bitset)
    bitsetRevs = [1<<(K-1)]
    bitset = 1<<(K-1)
    for B in reversed(Bs):
        bitset |= bitset>>B
        bitsetRevs.append(bitset)
    bitsetRevs.reverse()

    def isOK(x):
        B = Bs[x]
        numRevs = [0] * K
        bitset = bitsetRevs[x+1]
        for s in range(K):
            if bitset & (1<<(K-1-s)):
                numRevs[s] = 1
        accNumRevs = list(accumulate([0]+numRevs))
        bitset = bitsets[x]
        for s in range(K):
            if bitset & (1<<(K-1-s)):
                if accNumRevs[K-s] - accNumRevs[max(0, K-s-B)] > 0:
                    return True
        return False

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

    print(ok)


solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    def isOK(x):
        bitset = 1<<(K-1)
        for i, B in enumerate(Bs):
            if i == x: continue
            bitset |= bitset>>B
        return bitset & ((1<<Bs[x])-1)

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

    print(ok)


solve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
#dpm = [+1) for _ in range(N+1)]
dpm = [0]*(N+1)
dpm[0] = 1<<(K-1)
for i, a in enumerate(A):
    dpm[i+1] = dpm[i] | (dpm[i] >> a)

r = 0
dp2 = 1
for i, a in enumerate(A[::-1]):
    for j in range(a):
        if dp2 & dpm[N-i-1]:
            break
        dpm[N-i-1] >>= 1
    else:
        r += 1
    dp2 |= dp2<<a
    dp2 &= (1<<K)-1
print(r)

Submission status: Accepted

Solution code:

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

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

q = 0

a.sort()
a.reverse()
nmax = 0

for i in range(N):

    q += 1
    
    if nmax + a[i] >= K:
        ans -= q
        q = 0

    else:
        nmax = nmax + a[i]

print (ans)

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:
from operator import or_
from functools import reduce
import sys
readline = sys.stdin.readline

def check(a, l, r):
    if (reduce(or_, [r*(1<<k) for k in range(K) if l & (1<<k)])&filt).bit_length() + a > K:
        return True
    else:
        return False

N, K = map(int, readline().split())
A = list(map(int, readline().split()))
A = [a for a in A if a < K]
A.sort()
filt = (1<<K) - 1
M = len(A)
A = [None]+A
dpl = [0]*(M+2)
dpr = [0]*(M+2)
dpl[0] = 1
dpr[M+1] = 1

for i in range(1, M+1):
    dpl[i] = dpl[i-1]*(1<<A[i])&filt |dpl[i-1]

for i in range(M, 0, -1):
    dpr[i] = dpr[i+1]*(1<<A[i])&filt |dpr[i+1]
    
ok = M+1
ng = 0
while abs(ok - ng) > 1:
    med = (ok+ng)//2
    if check(A[med], dpl[med-1], dpr[med+1]):
        ok = med
    else:
        ng = med
print(ng)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
A = [0 if a >= K else a for a in A]
X = [1] * N
Y = [1] * N
m = (1<<K*8) - 1
for i in range(N-1):
    X[i+1] = (X[i] | X[i] << 8 * A[i]) & m if A[i] else X[i]
for i in range(1, N)[::-1]:
    Y[i-1] = (Y[i] | Y[i] << 8 * A[i]) & m if A[i] else Y[i]

ans = N
for i in range(N):
    if A[i] == 0 or ((X[i] * Y[i] & m) >> 8 * (K - A[i])) & ((1 << 8 * A[i]) - 1):
        ans -= 1
print(ans)

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:
N, K = map(int, input().split())
_A = list(map(int, input().split()))
ans = 0

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M):
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, right):
                isNess[j] = True

ans += sum(isNess)
print(N - ans)

Submission status: Accepted

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


def calc(x):
    if A[x] >= K:
        return True

    dp = [False] * K
    dp[0] = True

    ma = 0
    for i in range(N):
        if i == x:
            continue
        for j in range(ma, -1, -1):
            if j + A[i] >= K:
                continue

            dp[j + A[i]] |= dp[j]

        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


if not calc(N - 1):
    print(N)
    exit()

if calc(0):
    print(0)
    exit()

l, r = 0, N - 1
while r - l > 1:
    mid = (r + l) // 2
    if calc(mid):
        r = mid
    else:
        l = mid

print(r)

Submission status: Accepted

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


def calc(x):
    if A[x] >= K:
        return True
    dp = [False] * K
    dp[0] = True
    ma = 0
    for i in range(N):
        if i == x:
            continue
        for k in range(ma, -1, -1):
            if k + A[i] >= K:
                continue
            dp[k + A[i]] |= dp[k]
        ma = min(K - 1, ma + A[i])

    return sum(dp[K - A[x]:K])


l, r = 0, N - 1
if not calc(N - 1):
    print(N)
    exit()
if calc(0):
    print(0)
    exit()
while r - l > 1:
    mi = (l + r) // 2
    if calc(mi):
        r = mi
    else:
        l = mi

print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_left
N,K=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()
a=a[:bisect_left(a,K)]
d=[False]*(K)
d[0]=True
curr_max=0
ans=len(a)
for i,a in reversed(list(enumerate(a))):
  if curr_max+a>=K:
    ans=i
  c=curr_max
  for j in range(curr_max+1)[::-1]:
    if j+a<K and d[j]:
      d[j+a]=True
      c=max(c,j+a)
  curr_max=c
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
import sys
def inpl(): return [int(i) for i in input().split()]
def search(a,j):
    if D[j]:
        if D[j] == 1:
            return True
        else:
            return False
    H = defaultdict(lambda: 0)
    H[0] = True
    for i in a:
        for ni in H.copy().keys():
            if ni + i < K-j:
                H[ni+i] = True
                continue
            elif ni + i <= K-1:
                D[j] = 1
                return True
    D[j] = -1
    return False

N, K = inpl()
A = inpl()
A.sort()
A = A[:bisect.bisect_left(A,K)]
M = len(A)
D = defaultdict(lambda: 0)
if sum(A) < K:
    print(M)
    sys.exit()
if sum(A) == K:
    print(0)
    sys.exit()
lo = -1
hi = M
while hi - lo > 1:
    me = (hi+lo)//2
    B = A[:me] + A[me+1:]
    if search(B, A[me]):
        hi = me
    else:
        lo = me
print(hi)

Submission status: Accepted

Solution code:
# https://beta.atcoder.jp/contests/arc070/submissions/2980516
from bisect import bisect_left

N, K = map(int, input().split())
A = sorted(map(int, input().split()))
A = A[:bisect_left(A, K)]
dp = [False] * K
dp[0] = True
curr_max = 0
ans = len(A)
for i, a in reversed(list(enumerate(A))):
    # a[i - 1]を使ってa[i]が必要ならa[i - 1]も必要
    # a[i]より大きな値を使って判定すればいい
    if curr_max + a >= K:
        ans = i

    f = True
    for j in range(min(curr_max, K - a - 1), -1, -1):
        if dp[j]:
            dp[j + a] = True
            if f:
                curr_max = max(curr_max, j + a)
                f = False
print(ans)

Submission status: Accepted

Solution code:
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    y=A[x]
    if y>=K:
        return True
    dp=[False]*(K)
    dp[0]=True
    t=0
    for i in range(N):
        if i==x:
            continue
        s=A[i]
        for k in range(t,-1,-1):
            if k+s>=K:
                continue
            dp[k+s]=dp[k+s]|dp[k]
        t=min(t+s,K-1)
    if sum(dp[K-y:K]):
        return True
    else:
        return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Submission status: Accepted

Solution code:
import sys
N,K=map(int,input().split())
A=sorted([int(i) for i in input().split()])
sa=sum(A)
def f(x):
    y=A[x]
    if y>=K:
        return True
    L=set()
    L.add(0)
    dp=[False]*(K-y)
    dp[0]=True
    t=0
    for i in range(N):
        if i==x:
            continue
        s=A[i]
        for k in range(t,-1,-1):
            if not dp[k]:
                continue
            if k+s>=K:
                continue
            if k+s+y>=K:
                return True
            dp[k+s]=True
        t=min(t+s,K-y-1)
    return False
ma=N-1
mi=0
if not f(N-1):
    print(N)
    sys.exit()
if f(0):
    print(0)
    sys.exit()
while ma-mi>1:
    #print(ma,mi)
    a=(ma+mi)//2
    if f(a):
        ma=a
    else:
        mi=a
print(ma)

Submission status: Accepted

Solution code:
import bisect


def solve(k, aaa):
    aaa = aaa[:bisect.bisect_left(aaa, k)]

    dp = [False] * k
    dp[0] = True
    curr_max = 0
    ans = len(aaa)
    for i, a in reversed(list(enumerate(aaa))):
        if curr_max + a >= k:
            ans = i
        f = True
        for j in range(min(curr_max, k - a - 1), -1, -1):
            if dp[j]:
                dp[j + a] = True
                if f:
                    curr_max = max(curr_max, j + a)
                    f = False
    return ans


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

print(solve(k, aaa))

Submission status: Accepted

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

A = sorted([a for a in A if a < K])
N = len(A)
S = sum(A)

# あああああああああああああああああああ＼(＾o＾)／
if S < K:
    print(N)
    exit()
elif S - A[0] < N:
    print(0)
    exit()

l, r = -1, N
while r - l > 1:
    m = (l + r) // 2
    B = A[:m] + A[m + 1:]

    if S - A[m] < K - A[m]:
        l = m
        continue

    dp = [False] * (K + 1)
    dp[0] = True
    flg= False

    for i in range(N - 1):
        for j in range(K + 1)[::-1]:
            if B[i] > j:
                continue
            else:
                dp[j] = dp[j - B[i]]

            if dp[j] and K-A[m] <= j < K:
                r = m
                flg = True
                break
        if flg:
            flg = False
            break
    else:
        l = m

print(r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
 
N, K = inpl()
A = sorted(inpl())
S = []
s = 0
for a in A:
    s += a
    S.append(s)

A = A[::-1]
DP = [True]+[False for _ in range(K-1)]

OK = [False for _ in range(N)]
 
for i, a in enumerate(A):
    DP1 = [False for _ in range(K)]
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP):
        if d:
            DP1[j] = True
            if j + a >= K:
                OK[i] = True
            else:
                DP1[j+a] = True
    DP = DP1

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))