Problem p03782 (python)

Fixed submission:
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)

Buggy submission (verdict: Runtime Error):
n, k = map(int,input().split())
a = list(map(int,input().split()))
def trans(v):
  l = [0]*(k+1)
  for i in range(k+1):
    l[i] = (v&1)
    v >>= 1
  return l

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
  lc = lef[mid]
  rc = rig[mid]
  cov = ((1 << k) - 1) ^ ((1 << (k - a[mid])) - 1)
  for i in range(k+1):
    if lc & 1 and rc & cov:
      ng = mid
      break
    lc >>= 1
    cov >>= 1
  else:
    ok = mid
print(ok + 1)

Buggy submission (verdict: Runtime Error):
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[-1][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[-(i+1)][j]:
      dpb[-(i+2)][j] = True
      if j+wb < k:
        dpb[-(i+2)][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[v]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Buggy submission (verdict: Runtime Error):
_,k = map(int,input().split())
a = list(filter(lambda x:x<k,list(map(int,input().split()))))
n = len(a)
a.sort(reverse=True)
dpf = [[False]*k for _ in range(n)] 
dpb = [[False]*k for _ in range(n)] 
dpf[0][0] = True
dpb[0][0] = True
for i in range(n-1):
  wf = a[i]
  wb = a[-(i+1)]
  for j in range(k):
    if dpf[i][j]:
      dpf[i+1][j] = True
      if j+wf < k:
        dpf[i+1][j+wf] = True
    if dpb[i][j]:
      dpb[i+1][j] = True
      if j+wb < k:
        dpb[i+1][j+wb] = True
        
def check(v):
  w = a[v]
  im = [0]*(k+1)
  lf = dpf[v]
  lb = dpb[n-v-1]
  for i in range(k):
    if lb[i]:
      if k-i <= 0:
        continue
      im[max(k-w-i,0)] += 1
      im[k-i] -= 1
  if lf[0] and im[0]>0:
    return False
  for i in range(1,k):
    im[i] += im[i-1]
    if lf[i] and im[i]>0:
      return False
  return True
 
ng = -1
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  if check(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Buggy submission (verdict: Runtime Error):
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 0
  for j in range(n):
    if j == mid:
      continue
    w = a[j]
    for i in range(k,w-1,-1):
      if dp[i-w]:
        dp[i] = True
        if k-a[mid] <= i < k:
          ng = mid
          f = 1
          break
    if f:
      break
  else:
    ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()

Buggy submission (verdict: Runtime Error):
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
hi = -1
lo = n
while lo-hi>1:
  mid = (lo+hi)//2
  if a[mid] >= k:
    hi = mid
  else:
    lo = mid
ng = hi
ok = n
while ok-ng > 1:
  mid = (ok+ng)//2
  dp = [False]*(k+1)
  dp[0] = True
  f = 1
  for j in range(n):
    if j == mid:
      f = 0
      continue
    w = a[j]
    new = dp.copy()
    for i in range(k-w+1):
      new[i+w] |= dp[i]
    dp = new
  if any(dp[k-a[mid]:k]):
    ng = mid
  else:
    ok = mid
print(n-ok)