Problem:
 Score : 500 points    Problem Statement We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.  The square (i, j) at the i -th row from the top and the j -th column from the left is dark if S_{i,j} is 0 , and white if S_{i,j} is 1 .  We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.  How many times do we need to cut the bar so that every block after the cuts has K or less white squares?      Constraints  1 \leq H \leq 10  1 \leq W \leq 1000  1 \leq K \leq H \times W  S_{i,j} is 0 or 1 .         Input Input is given from Standard Input in the following format:  H  W  K  S_{1,1}S_{1,2}...S_{1,W}  :  S_{H,1}S_{H,2}...S_{H,W}       Output Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.        Sample Input 1 3 5 4
11100
10001
00111      Sample Output 1 2  For example, cutting between the 1 -st and 2 -nd rows and between the 3 -rd and 4 -th columns - as shown in the figure to the left - works.  Note that we cannot cut the bar in the ways shown in the two figures to the right.        Sample Input 2 3 5 8
11100
10001
00111      Sample Output 2 0  No cut is needed.       Sample Input 3 4 10 4
1110010010
1000101110
0011101001
1101000111      Sample Output 3 3

Solution (Python):
h,w,k = map(int,input().split())
s = [list(map(int,input().strip())) for i in range(h)]
from copy import deepcopy

ss = deepcopy(s)
for i in range(h):
    for j in range(w-1):
        ss[i][j+1] += ss[i][j]


def gru_hol(HOL): 
    groups_a = []
    group_a = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups_a.append(group_a)
            group_a = [i+1]
        else:
            group_a.append(i+1)
    groups_a.append(group_a)
    return groups_a

def nex_hol(HOL): 
    for j in range(h-1):
        if(HOL[j] == 0):
            HOL[j] = 1
            for k in range(0,j):
                HOL[k] = 0
            break
    return HOL

def cutsum(grp,lscut,nxcut): 
    count = 0
    for i in grp:
        if(lscut != 0):
            count = count + ss[i][nxcut-1] - ss[i][lscut-1]
        else:
            count += ss[i][nxcut-1] 
    return count

def cutcheck(grp_a,lscut_a): 
    ct_a = 0
    for i in grp_a:
        ct_a += s[i][lscut_a]
    if(ct_a > k):
        return False
    else:
        return True

min_cut = h + w - 2
hol = [0]*(h-1)
for i in range(2**(h-1)):
    fl_ag = 0
    lastcut = 0
    cuts = 0 
    groups = gru_hol(hol) 
    for j in range(1,w):
        flag = 0
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == False):
                    fl_ag = 1 
                    break
                else:
                    flag = 1
        if(fl_ag == 1):
            break
        if(flag == 1):
            cuts += 1
            lastcut = j

    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

Solution (Python):
h,w,k = map(int,input().split())
s = [list(map(int,input().strip())) for i in range(h)]
from copy import deepcopy

ss = deepcopy(s)
for i in range(h):
    for j in range(w-1):
        ss[i][j+1] += ss[i][j]


def gru_hol(HOL): 
    groups_a = []
    group_a = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups_a.append(group_a)
            group_a = [i+1]
        else:
            group_a.append(i+1)
    groups_a.append(group_a)
    return groups_a

def nex_hol(HOL): 
    for j in range(h-1):
        if(HOL[j] == 0):
            HOL[j] = 1
            for k in range(0,j):
                HOL[k] = 0
            break
    return HOL

def cutsum(grp,lscut,nxcut): 
    count = 0
    for i in grp:
        if(lscut != 0):
            count = count + ss[i][nxcut-1] - ss[i][lscut-1]
        else:
            count += ss[i][nxcut-1] 
    return count

def cutcheck(grp_a,lscut_a): 
    ct_a = 0
    for i in grp_a:
        ct_a += s[i][lscut_a]
    if(ct_a > k):
        return False
    else:
        return True

min_cut = h + w - 2
hol = [0]*(h-1)
for i in range(2**(h-1)):
    fl_ag = 0
    lastcut = 0
    cuts = 0 
    groups = gru_hol(hol) 
    for j in range(1,w):
        flag = 0
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == False):
                    fl_ag = 1 
                    break
                else:
                    flag = 1
        if(fl_ag == 1):
            break
        if(flag == 1):
            cuts += 1
            lastcut = j

    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
import itertools
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    s = [list(map(int,list(input()))) for _ in [0]*h]
    '''
    sms = [[0]*w for _ in [0]*h]
    for i in range(w):
        for j in range(h):
            sms[j][i] = sms[j-1][i]+s[j][i]
        print(i)
    '''
    cmi = 10**18
    for i in range(2**(h-1)):
        pos = [0]*h
        for j in range(h-1):
            if (i >> j) & 1:
                pos[j+1] = pos[j]+1
            else:
                pos[j+1] = pos[j]
        cmii = pos[-1]
        si = [0]*h
        for jj in range(h):
            si[pos[jj]] += s[jj][0]
        if max(si) > k:
            continue
        f = True
        for j in range(1,w):
            if f:
                for ii in range(h):
                    if si[pos[ii]]+s[ii][j] > k:
                        cmii += 1
                        si = [0]*h
                        for jj in range(h):
                            si[pos[jj]] += s[jj][j]
                        if max(si) > k:
                            f = False
                        break
                    else:
                        si[pos[ii]]+=s[ii][j]
        if f and cmii < cmi:
            cmi = cmii
    print(cmi)
    return

if __name__ == '__main__':
    main()

Solution (Python):
h, w, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)


for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True
    flg = True
    cnt = [0] * len(lis)
    for i in range(w):
        cnt2 = [0] * len(lis)
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        
        
    if flg2 == True:
        ans = min(ans,val)
    
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
res = 1000000
for i in range(2 ** (h - 1)):
    l = [0]
    cnt = 0
    for j in range(h - 1):
        if (i >> j) & 1:
            l.append(j + 1)
            cnt += 1
    l.append(h)
    li = [0] * (cnt + 1)
    j = 0
    ans = cnt
    f = 0
    while j < w:
        sm = 0
        idx = 0
        for i in range(h):
            if l[idx + 1] <= i:
                if sm > k:
                    f = 1
                    break
                sm = 0
                if li[idx] > k:
                    ans += 1
                    break
                idx += 1
            if s[i][j] == '1':
                sm += 1
                li[idx] += 1
        else:
            if li[idx] > k:
                if sm > k:
                    f = 1
                    break
                ans += 1
                li = [0] * (cnt + 1)
                continue
            j += 1
            continue
        if f:
            break
        li = [0] * (cnt + 1)
    if not f:
        res = min(res, ans)
print(res)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        
        cut = group_number
        cnt = [0] * len(group)
        w = 0
        while w < W:
            now = [0] * len(group)
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = [0] * len(group)
                    break
                cnt[g] += now[g]
            if cut >= min_cut:
                break
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    h,w,k=map(int,readline().split())
    grid=[readline().strip() for _ in range(h)]

    ans=float("inf")
    for i in range(1<<(h-1)):
        div=[(i>>j)&1 for j in range(h-1)]
        l=len([0 for i in range(h-1) if div[i]])+1
        cnt=[0]*l
        tmp=0
        for j in range(w):
            now=0
            flag=False
            for i_2 in range(h):
                if grid[i_2][j]=="1":
                    cnt[now]+=1
                    if cnt[now]>k:
                        flag=True
                        break
                if i_2<h-1 and div[i_2]==1: now+=1
            if flag:
                tmp+=1
                cnt=[0]*l
                now=0
                flag=False
                for i_2 in range(h):
                    if grid[i_2][j]=="1":
                        cnt[now]+=1
                        if cnt[now]>k:
                            flag=True
                            break
                    if i_2<h-1 and div[i_2]==1: now+=1
                if flag: break
        else:
            tmp+=l-1
            ans=min(ans,tmp)

    print(ans)

if __name__=="__main__":
    main()

Solution (Python):
h, w, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)
if h == 1:
    ans = 0
    cnt = 0
    for i in range(w):
        if s[0][i] == '1':
            cnt += 1
        if cnt > z:
            ans += 1
            cnt -= z
    print(ans)
    exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True
    flg = True
    cnt = [0] * len(lis)
    for i in range(w):
        cnt2 = [0] * len(lis)
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        
        
    if flg2 == True:
        ans = min(ans,val)
    
print(ans)

Solution (Python):
h, w, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)
if h == 1:
    ans = 0
    cnt = 0
    for i in range(w):
        if s[0][i] == '1':
            cnt += 1
        if cnt > k:
            ans += 1
            cnt -= k
    print(ans)
    exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True
    flg = True
    cnt = [0] * len(lis)
    for i in range(w):
        cnt2 = [0] * len(lis)
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        
        
    if flg2 == True:
        ans = min(ans,val)
    
print(ans)

Solution (Python):
from itertools import product
import numpy as np
H, W, K = map(int, input().split())

grid = [[] for _ in range(H) ]
for i in range(H):
  grid[i] = list(map(int, input()))



def init_cnt():
  _grid = [[0] * W for _ in range(H) ]
  _grid[0][0] = grid[0][0]
  for w in range(1, W):
    _grid[0][w] = _grid[0][w-1] + grid[0][w]
  for h in range(1, H):
    cnt_w = 0
    for w in range(W):
      cnt_w += grid[h][w]
      _grid[h][w] = _grid[h-1][w] + cnt_w
  
  return _grid

_grid = init_cnt()



def cnt(x1, x2, y1, y2):
  if x1 == 0 and y1 == 0:
    return _grid[x2][y2]
  if x1 == 0:
    return _grid[x2][y2] - _grid[x2][y1 -1]
  if y1 == 0:
    return _grid[x2][y2]- _grid[x1 - 1][y2]
  return _grid[x2][y2] - _grid[x2][y1 - 1] - _grid[x1 - 1][y2] + _grid[x1 - 1][y1 - 1]


ans = 1010
for i in range(2 ** (H - 1)):
  res = 0
  lst = list(k for k, j in enumerate(range(H), 1) if i >> j & 1)
  res += len(lst)
  lst.append(H)
 
  
  y =  0
  for w in range(1, W+1):
    x = 0
    flag = False
    
    for lst_i in lst:
      if cnt(x, lst_i - 1 ,y ,w - 1) > K:
        if y + 1 < w:
          res += 1
          y = w - 1
        else:
          flag = True
        break
        
      x = lst_i 
    else:
      pass
    if flag:
      break
  else:
    ans = min(ans, res)
    
print(ans)

Solution (Python):
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
  chocolate.append(list(input()))
INF = 10**15
ans = INF

for div in range(1<<(H-1)):
  g = 0
  id = [None] * (H)

  
  for i in range(H):
    id[i] = g
    if (div>>i)&1: g += 1

  
  c = [ [0]*W for _ in range(g+1) ]
  for i,block in zip(id, chocolate):
    for j,b in enumerate(block):
      if b == "1":
        c[i][j] += 1

  
  now = [0] * (g+1)
  lines = g
  for j in range(W):
    for i in range(g+1):
      now[i] += c[i][j]

    ok = all( n<=K for n in now )
    if not ok:
      lines += 1
      now = [0] * (g+1)
      for i in range(g+1):
        now[i] += c[i][j]
      ok = all( n<=K for n in now )
      if not ok:
        
        lines = INF
        break

  ans = min(ans, lines)

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
def split(word): 
    return [char for char in word]  
      
m=[]
for i in range(h):
  m.append(input())
t=[0]*(h-1)
ans=w-1+h-1
for i in range(2**(h-1)):
  failflag=0
  s=split("{0:b}".format(i))
  s.reverse()
  for j in range(h-1-len(s)):
    s.append('0')
  s.reverse()
  a=[]
  a.append([])
  for j in range(w):
    a[0].append(int(m[0][j]))
  for j in range(1,h):
    if s[j-1]=='0':
      for l in range(w):
        a[-1][l]+=int(m[j][l])
    else:
      a.append([])
      for l in range(w):
        a[-1].append(int(m[j][l]))
  n=len(a)
  tmp=0
  p=[0]*n
  flag=0
  for j in range(w):
    for l in range(n):
      if a[l][j]>k:
        failflag=1
      if p[l]+a[l][j]>k:
        flag=1
        break
    if flag==1:
      tmp+=1
      flag=0
      for t in range(n):
        p[t]=0
    for l in range(n):
      p[l]+=a[l][j]
  if failflag==0 and n-1+tmp<ans:
    ans=n-1+tmp
print(ans)

Solution (Python):
H, W, K = map(int, input().split()) 
sl = []
for _ in range(H):
    sl.append(list(input()))


ans = 10**8
for i in range(2 ** (H-1)):
    fail_flag = False
    comb = []
    for j in range(H-1):
        if ((i >> j) & 1): 
            comb.append(j)
    comb.append(H-1)
    
    sections = []
    for k in range(0,len(comb)):
        if k == 0:
            sections.append( sl[0:comb[0]+1] )
        else:
            sections.append( sl[comb[k-1]+1:comb[k]+1] )
    

    partition_cnt = 0
    sections_w_cnts = [0]*len(sections)
    for w in range(W):
        sections_curr_w_cnts = [0]*len(sections)
        partition_flag = False
        for i, sec in enumerate(sections):
            for row in sec:
                if row[w] == '1':
                    sections_curr_w_cnts[i] += 1
                    sections_w_cnts[i] += 1
                    if sections_curr_w_cnts[i] > K:
                        fail_flag = True
                        break
                    if sections_w_cnts[i] > K:
                        partition_flag = True

            if fail_flag: break
        if fail_flag: break

        if partition_flag:
            sections_w_cnts = [v for v in sections_curr_w_cnts]
            
            partition_cnt += 1
        

    if not fail_flag:
        ans = min(len(comb)-1+partition_cnt, ans)

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w,k=map(int,input().split())
    S=[input() for _ in range(h)]
    final_ans=10**10
    for row_lis in range(1<<(h-1)):
        lst=[0]*h
        q,ans=0,0
        for r in range(h-1):
            if (row_lis>>r)&1==0:
                lst[r+1]=q
            else:
                q+=1
                lst[r+1]=q
                ans+=1
        data=[0]*h
        for j in range(w):
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    ans+=1
                    break
            else:
                continue
            data=[0]*h
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    break
            else:
                continue
            break
        else:
            final_ans=min(final_ans,ans)
    print(final_ans)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w,k=map(int,input().split())
    S=[input() for _ in range(h)]
    final_ans=10**10
    for row_lis in range(1<<(h-1)):
        lst=[0]*h
        q,ans=0,0
        for r in range(h-1):
            if (row_lis>>r)&1==0:
                lst[r+1]=q
            else:
                q+=1
                lst[r+1]=q
                ans+=1
        data=[0]*h
        for j in range(w):
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    ans+=1
                    break
            else:
                continue
            data=[0]*h
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    break
            else:
                continue
            break
        else:
            final_ans=min(final_ans,ans)
    print(final_ans)


if __name__=='__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(300000)

def solve(h, w, k, S):
    ret = float('inf')
    bits = 2 ** (h - 1)
    for b in range(bits):
        tmp = 0
        idx = 0
        groups = []
        for y in range(h):
            groups.append(idx)
            if (1 << y) & b:
                idx += 1
        m = idx + 1
        counts = [[0] * w for _ in range(m)]
        imp = False
        for y in range(h):
            g = groups[y]
            for x in range(w):
                if S[y][x] == 1:
                    counts[g][x] += 1
                    if counts[g][x] > k:
                        imp = True
                        break
        if imp:
            continue

        cuts = 0
        cum = [counts[g][0] for g in range(m)]
        for x in range(1, w):
            cut = False
            for g in range(m):
                cum[g] += counts[g][x]
                if cum[g] > k:
                    cut = True
                    break
            if cut:
                cuts += 1
                cum = [counts[g][x] for g in range(m)]
        ret = min(ret, m - 1 + cuts)
        
    print(ret)
    return

def main():
    h, w, k = map(int, input().split())
    s = []
    for i in range(h):
        tmp = str(input())
        s.append([int(j) for j in tmp])
    solve(h, w, k, s)

if __name__ == '__main__':
    main()

Solution (Python):
import sys


def da_generate(h, w, a):
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da


def da_calc(p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q - 1]
    if q == 0:
        return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

H, W, K = map(int, sys.stdin.readline().rstrip().split())
grid = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(H)]
da = da_generate(H, W, grid)

ans = 10 ** 18
for i in range(2**(H - 1)):
    res = 0
    s = [k for k, j in enumerate(range(H), 1) if i >> j & 1] 
    res += len(s)
    s.append(H)
    y = 0
    for w in range(1, W + 1): 
        x = 0
        flag = False
        for s_i in s:
            if da_calc(x, y, s_i - 1, w - 1) > K:
                if y + 1 < w:
                    res += 1
                    y = w - 1
                else:
                    flag = True
                break
            x = s_i
        else:
            pass
        if flag:
            break
    else:
        ans = min(ans, res)

print(ans)

Solution (Python):
import sys


def da_generate(h, w, a):
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da


def da_calc(p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q - 1]
    if q == 0:
        return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

H, W, K = map(int, sys.stdin.readline().rstrip().split())
grid = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(H)]
da = da_generate(H, W, grid)

ans = 10 ** 18
for i in range(2**(H - 1)):
    res = 0
    s = [k for k, j in enumerate(range(H), 1) if i >> j & 1] 
    res += len(s)
    s.append(H)
    y = 0
    for w in range(1, W + 1): 
        x = 0
        flag = False
        for s_i in s:
            if da_calc(x, y, s_i - 1, w - 1) > K:
                if y + 1 < w:
                    res += 1
                    y = w - 1
                else:
                    flag = True
                break
            x = s_i
        else:
            pass
        if flag:
            break
    else:
        ans = min(ans, res)

print(ans)

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j+(t>j);i=h
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j+(t>j);i=h
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j-(t<j);i=h
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r+=1;t=j;j-=f;i=h
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r+=1;t=j;j-=f;break
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0'
   if d[c]>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=t<j
   if d[c]>k:d=[0]*h;r+=1-h*w*~-f;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r-~c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k=map(int,h.split())
m=b=h+w
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0'
   if d[c]>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m=min(m,r-~c)
print(m)

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=t<j
   if d[c]>k:d=[0]*h;r+=1-h*w*~-f;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r-~c,
print(min(m))

Solution (Python):
x,*s=open(0)
h,w,k,*m=map(int,x.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';y=t<j
   if d[c]>k:d=[0]*h;r+=1-~-y*h*w;t=j;j-=y;break
   c+=b>>i&1;i+=1
  j+=1
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+c,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1;v=c
 m+=r+v,
print(min(m))

Solution (Python):
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+bin(b).count('1'),
print(min(m))

Solution (Python):
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=h*w*x;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+bin(b).count('1'),
print(min(m))

Solution (Python):
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print(min(m))

Solution (Python):
r=range
h,*s=open(0)
h,w,k,*m=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v-=f
  if f:c=u
 if g<1:m+=l-v,
print(min(m))

Solution (Python):
m=9e9
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v-=f
  if f:c=u
 if g<1:m=min(m,l-v)
print(m)

Solution (Python):
r=range
h,*s=open(0)
m=9e9
h,w,k=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=-1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if g<1:m=min(m,v+l)
print(m)