Submission #4035099

---

Source Code Expand

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

Submission Info

Judge Result