Problem p02733 (python)

Fixed submission:
def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

  print(ans)
  
main()

Buggy submission (verdict: Runtime Error):
def main()
  H,W,K = map(int,input().split())
  from collections import deque
  ans = 10000
  S = [list(map(int,list(input()))) for _ in range(H)]
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = [x-y for x in cum[q[a+1]] for y in cum[q[a]]]
      for j in x:
        if j>K:
          judge = True
          break
      if judge:
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      for x,a in enumerate(p):
        y = l[x]+a[w]
        if y>K:
          t_a+=1
          l = [0]*n
          for z,b in enumerate(p):
            l[z] = b[w]
          break
        else:
          l[x]=y
    ans = min(ans,t_a)

  print(ans)
  
main()

Buggy submission (verdict: Runtime Error):
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = list(cum[q[a+1]]-cum[q[a]])
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+a[w]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

Buggy submission (verdict: Runtime Error):
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(x)

  if judge:
    continue
  
  t_a = len(q)-2
  l = [0]*len(p)
  judge = False
  for w in range(W):
    for x,a in enumerate(p):
      l[x]+=a[w]
      if l[x]>K:
        t_a+=1
        l = [0]*len(p)
        for z,b in enumerate(p):
          l[z] = b[w]
        break
  ans = min(ans,t_a)
    
print(ans)