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):
r=range
h,*s=open(0)
m=9e9
h,w,k=map(int,h.split())
for i in r(1<<h-1):
 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)

Solution (Python):
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):z=i>>j&1;t+=[j+1]*z;l+=z
 t+=h,
 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)

Solution (Python):
r=range;_,*s=open(0);m=9e9
h,w,k=map(int,_.split())
for i in r(1<<h-1):
 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 not g:m=min(m,v+l)
print(m)

Solution (Python):
r=range;_,*s=open(0)
h,w,k=map(int,_.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):z=i>>j&1;t+=[-~j]*z;l+=z
 t+=h,
 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 not g:m=min(m,v+l)
print(m)

Solution (Python):
r=range;_,*s=open(0)
h,w,k=map(int,_.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):
  if i>>j&1:t+=j+1,;l+=1
 t+=h,
 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 not g:m=min(m,v+l)
print(m)

Solution (Python):
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for l in range(H)]
posibility = set()

for i in range(1<<H-1):
    SW = []
    tmp = S[0]
    counter = 0
    
    for k in range(H-1):
        if i>>k & 1:
            SW.append(tmp)
            tmp = S[k+1]
        else:
            tmp = [tmp[l]+S[k+1][l] for l in range(W)]
    SW.append(tmp)
    counter += len(SW)-1
    max_counter = 0

    for k in range(len(SW)):
        max_counter = max(max(SW[k]),max_counter)
    if max_counter >K:
        continue

    tmp_w = [SW[row][0] for row in range(len(SW))]
    
    for w in range(W-1):
        test = [tmp_w[row]+SW[row][w+1] for row in range(len(SW))]
        if max(test)>K:
            tmp_w = [SW[row][w+1] for row in range(len(SW))]
            counter += 1
        else:
            tmp_w = test

    posibility.add(counter)
print(min(posibility))

Solution (Python):
h,w,k=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(h)]

def func(div):
  ret=0
  n_grp=len(div)
  grp=[0]*n_grp
  div.append(h)
  for c in range(w):
    for r in range(h):
      for i in range(n_grp):
        if div[i]<=r<div[i+1]:
          grp[i]+=s[r][c]
    if max(grp)>k:
      ret+=1
      grp=[0]*n_grp
      for r in range(h):
        for i in range(len(div)):
          if div[i]<=r<div[i+1]:
            grp[i]+=s[r][c]
      if max(grp)>k:
        return -1
  return ret


ans=h*w
for i in range(pow(2,h-1)):
  div=[0]
  for j in range(h-1):
    if ((i>>j) & 1):
      div.append(j+1)
  a=func(div)
  
  if a>-1:
    ans=min(ans,a+len(div)-2)
print(ans)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

INF = 1 << 60
H, W, K = nm()
grid = []
for i in range(H):
    row = ns()
    assert len(row) == W
    grid.append(row)


def min_vsplits(ranges):
    vsplits = 0
    block_count = [0] * len(ranges)
    for c in range(W):
        line_count = [0] * len(ranges)
        for i, (start, end) in enumerate(ranges):
            for r in range(start, end):
                if grid[r][c] == "1":
                    line_count[i] += 1
                    block_count[i] += 1
        if max(line_count) > K:
            return INF  
        if max(block_count) > K:
            vsplits += 1
            for i in range(len(block_count)):
                block_count[i] = line_count[i]
    return vsplits


def solve():
    S = 1 << (H - 1)
    min_splits = (H - 1) * (W - 1)  
    for splits in range(S):
        ranges = []
        start = 0
        stop = 1
        while splits:
            if splits & 1:
                ranges.append((start, stop))
                start = stop
            splits >>= 1
            stop += 1
        ranges.append((start, H))
        hsplits = len(ranges) - 1
        vsplits = min_vsplits(ranges)
        s = hsplits + vsplits
        if min_splits > s:
            min_splits = s
            
            
            
            
    return min_splits


print(solve())

Solution (Python):
import sys






h,w,k=map(int,input().split())
s = [list(map(int, input())) for _ in range(h)]
res=0
ans=10**9
for i in range(2**(h-1)):
    p=1
    partation=[-1]*(h-1)

    for j in range(h-1):
        if i &(1<<j):
            partation[j]=1
            p+=1
    g=[0]*p
    res=0
    l=r=0
    f=False
    while r<w:
        m=0
        for j in range(h):
            g[m]+=s[j][r]
            if g[m]>k:
                res+=1
                g=[0]*p
                if l==r:
                  f=True
                l=r
                break
            if j<h-1 and partation[j]==1:
                m+=1
        else:
            r+=1
        if f:
          break
    else:
      res+=p-1
      if res<ans:
          ans=res
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=[[0 for i in [0]*W] for j in [0]*H]
DO=[[0 for i in [0]*W] for j in [0]*H]
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
CO[H-1]=DO[H-1]
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 for k in range(H-1):
  if ((s >> k) & 1):
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]
   E+=1
  else:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]+CO[H-k-1][i]
 lst=[0]*H
 for h in range(W):
  c=max(CO[x][h] for x in range(H))
  d=max(lst[y]+CO[y][h] for y in range(H))
  if c>K:
   E=1000000
   break
  elif d>K:
   D+=1
   lst=[0]*H
  for z in range(H):
   lst[z]+=CO[z][h]
 F=min(F,D+E)
print(F)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)


ans = 100100100
for i in range(tdiv):
    lis=[]
    
    
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    
    for j in range(h-1):
        if (i>>j&1):
            
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            
            
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    
    
    clis=[0 for ii in range(cnt+1)]
    
    tmpcnt=cnt
    for ind in range(w):
        
        
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    
    ans = min(ans,cnt)
print(ans)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)


ans = 100100100
for i in range(tdiv):
    lis=[]
    
    
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    
    for j in range(h-1):
        if (i>>j&1):
            
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            
            
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    
    
    clis=[0 for ii in range(cnt+1)]
    
    tmpcnt=cnt
    for ind in range(w):
        
        
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    
    ans = min(ans,cnt)
print(ans)

Solution (Python):




H,W,K = map(int, input().split())
S = [[int(i) for i in list(input())] for i in range(H)]


whites_col = [[0 for _ in range(W)] for _ in range(H)]
for w in range(W):
    for h in range(H):
        if h == 0:
            whites_col[h][w] = S[h][w]
        else:
            whites_col[h][w] = whites_col[h-1][w] + S[h][w]

"""
マス目で考えると、縦Hマスある場合はH+1本の横線がある。
その横線の番号を渡して、その間にある数をとってくる
"""
def calc(w, a,b):
    if a == 0:
        return whites_col[b-1][w]
    else:
        return whites_col[b-1][w] - whites_col[a-1][w]

ans = (H-1)*(W-1)
for bit in  range(1 << (H-1)):
    
    cnt_split = bin(bit).count("1")

    divs = [0]
    for i in range(H-1):
        if bit & (1 << i):
            divs.append(i+1)
    divs.append(H)

    curr = [0] * (len(divs)-1)
    prev = [0] * (len(divs)-1)
    over_K_in_curr = False
    for w in range(W):
        for i,(a,b) in enumerate(zip(divs, divs[1:])):
            curr[i] = calc(w, a, b)

        over_K_in_curr = False
        if max(curr) > K:
            over_K_in_curr = True
            break
        
        for i in range(len(divs)-1):
            prev[i] += curr[i]

        if max(prev) > K:
            cnt_split += 1
            prev = curr[:]

    if not over_K_in_curr:
        ans = min(ans, cnt_split)

print(ans)

Solution (Python):
import itertools

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])

ans = 2000

for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    
    lst = [[s for s in S[0]]]
    
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)

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


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  
        id[j] = g
        if (i >> j & 1):  
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)

from itertools import product, accumulate, combinations, product




def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(accumulate(list(map(int, list(input()))))))
    for h in range(1, H):
        for w in range(W):
            S[h][w] += S[h-1][w]

    ret = float('inf')

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)

from itertools import product, accumulate, combinations, product




def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(accumulate(list(map(int, list(input()))), lambda x,y:x+y)))
    for h in range(1, H):
        for w in range(W):
            S[h][w] += S[h-1][w]

    ret = float('inf')

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)

from itertools import product

import numpy as np


def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    ret = float('inf')
    for w in range(1, W):
        S[:,w] += S[:,w-1]
    for h in range(1, H):
        S[h,:] += S[h-1,:]
    S = S.tolist()
    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()

Solution (Python):
import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
for i in range(W):
  for j in range(1,H):
    S_t[i][j] += S_t[i][j-1]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if bh[k] == 0:
        su = S_t[j][bh[k+1]-1]
      else:
        su = S_t[j][bh[k+1]-1]-S_t[j][max(0,bh[k]-1)]
      if white[k] + su > K:
        if su > K:
          j = W
          cnt = H*W+1
          flag = False
        else:
          flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Solution (Python):
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]

acum = [[0]*(w+1) for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        acum[i+1][j+1] = acum[i][j+1] + acum[i+1][j] - acum[i][j] + int(s[i][j])



def white_choco_count(x1, y1, x2, y2):
    return acum[y2][x2] - acum[y2][x1] - acum[y1][x2] + acum[y1][x1]


ans = float("inf")
for rows in range(2**(h-1)):
    count = 0
    hlist = []
    for i in range(h-1):
        if rows >> i & 1 == 1:
            count += 1  
            hlist.append(i+1)
    hlist.append(h)
    
    x1 = 0
    for x2 in range(w):
        y1 = 0
        for y2 in hlist:
            if white_choco_count(x1, y1, x2, y2) > k:
                count += float("inf")
            
            elif white_choco_count(x1, y1, x2, y2) <= k < white_choco_count(x1, y1, x2+1, y2):
                count += 1
                
                x1 = x2
                break
            y1 = y2
    
    y1 = 0
    for y2 in hlist:
        if white_choco_count(x1, y1, w, y2) > k:
            count += float("inf")
        y1 = y2
    
    ans = min(ans, count)
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
C = [list(input()) for _ in range(h)]

ans = 10 ** 20
for s in range(2 ** (h - 1)):
    yoko = bin(s).count("1")
    white = [0] * (yoko + 2)
    cnt = 0
    
    cnt += yoko
    outflag = 0
    for j in range(w):
        now = 0
        for i in range(h):
            if outflag:
                break
            white[now] += int(C[i][j])
            if white[now] > k:
                
                
                
                cnt += 1
                
                
                white = [0] * (yoko + 2)
                now = 0
                
                for t in range(i + 1):
                    white[now] += int(C[t][j])
                    if white[now] > k:
                        outflag = 1
                        break
                    if (s >> t) & 1 == 1:
                        now += 1
                continue
            if (s >> i) & 1 == 1:
                now += 1
        if outflag:
            break
    if outflag:
        outflag = 0
        continue
    ans = min(cnt, ans)
print(ans)

Solution (Python):
import sys


input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007


def ii(v, n):
	v += 2 ** 15
	ret = bin(v)[-n:]
	return ret

def v_sum(a,b):
	return [av+bv for av,bv in zip(a,b)]

def get_n(rr, mm, k, limit):
	ret = sum([int(c) for c in rr])
	o = mm[0]
	pp = []
	for index_i, is_cut in enumerate(rr):
		if is_cut == '1':
			pp.append(o)
			o = mm[index_i+1]
		else:
			o = v_sum(o, mm[index_i+1])
			
		if max(o) > k:
			return mod, None
			
	pp.append(o)
	
	ll = [pp[j][0] for j in range(len(pp))]
	for v in ll:
		if v > k:
			return mod, None
	
	cc = [0]*(len(mm[0]))
	for i in range(1, len(mm[0])):
		for il, v in enumerate(ll):
			if ll[il] + pp[il][i] > k:
				ret += 1
				if ret >= limit:
					return limit+1, None
				ll = [pp[j][i] for j in range(len(pp))]
				cc[i] = 1
				break
			else:
				ll[il] += pp[il][i]
	return ret, cc

def main():
	h, w, k = tin()
	mm=[]
	for _ in range(h):
		s = input()
		s = [int(c) for c in s]
		
		mm.append(s)
		
	n = (h-1)*(w-1) + 1
	for i in range(2 ** (h-1)):
		rr = ii(i, h-1)
		tt, cut_info = get_n(rr, mm, k, n)
		if tt < n:
			n = tt
		
	print(n)
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            cum[i][j]=cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+int(S[i-1][j-1])
    ans = 2000
    for p in product([0,1],repeat=H-1):
        line = [0]
        p = list(p)
        cnt = sum(p)
        for i in range(1,H):
            if p[i-1]==1:
                line.append(i)
        line.append(H)
        w_s = 0
        w_e = 1
        b = False
        while w_e <= W:
            for i in range(len(line)-1):
                h_s = line[i]
                h_e = line[i+1]
                white = cum[h_e][w_e]+cum[h_s][w_s]-cum[h_e][w_s]-cum[h_s][w_e]
                if white > K:
                    if w_e == w_s+1:
                        b = True
                        break
                    else:
                        w_s = w_e-1
                        cnt += 1
                        break
            if b==True:
                break
            w_e += 1
        else:
            ans = min(ans,cnt)
    return ans
print(solve())

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))

def resolve():
    H,W,K=pin()
    choco=[list(input()) for _ in range(H)]
    
    ans=H+W 
    
    for h in range(1<<(H-1)):
        tempans=0

        see=[]

        shiro=[0]
        for i in range(H):
            see.append(tempans)
            if (1<<i)&h:
                tempans+=1 
                shiro.append(0)
            
        
        
        
        j=0
        while(j<W):
            f=1
            for n,s in enumerate(see):
                shiro[s]+=int(choco[n][j])
                if shiro[s]>K:
                    if j==0:
                        f=0
                        break
                    tempans+=1
                    shiro=[0]*len(shiro)
                    j-=1
                    break   
            if f==0:
                tempans=H*W
                break
            j+=1
            
            
        
        ans=min(ans,tempans)
    print(ans)

resolve()

Solution (Python):
from itertools import product, combinations_with_replacement
H, W, K = map(int, input().split())
S = tuple(tuple(map(int, list(input()))) for _ in range(H))

choko = [[0]*W for _ in range(H)]

ans = 10**18

for divide in product(range(2), repeat=H - 1):
    cut = sum(divide)
    row = [0]
    for d in divide:
        if d:
            row.append(row[-1] + 1)
        else:
            row.append(row[-1])

    r = row[-1] + 1
    for i in range(r):
        for j in range(W):
            choko[i][j] = 0
    for i in range(H):
        for j in range(W):
            choko[row[i]][j] += S[i][j]

    if any(choko[i][0] > K for i in range(r)):
        continue

    now = [0] * r
    for j in range(W):
        if any(now[i] + choko[i][j] > K for i in range(r)):
            cut += 1
            now = [choko[i][j] for i in range(r)]
        else:
            for i in range(r):
                now[i] += choko[i][j]

    ans = min(ans, cut)

print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]
    
    white = 0
    for line in S:
        white += sum(line)
 
    if white <= K:
        print(0)
        exit()
 
    
    ans = 10**5
    
    
    
    for pattern in range(2**(H-1)):
        
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]
 
        
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break
 
                count[i] += y[i][j]
                
                
                
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j]
                    break
            
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6
        
        ans = min(ans, x + ly)
 
    print(ans)
 
 
main()

Solution (Python):
from itertools import product
H, W, K = map(int, input().split())
G = [list(map(int, list(input()))) for _ in range(H)]

ans = float("inf")

for pattern in product([0, 1], repeat = H - 1):
    div = [0] + [i for i, p in enumerate(pattern, 1) if p == 1] + [H]
    rows = []
    for i in range(len(div) - 1):
        row = []
        for j in range(W):
            tmp = 0
            for k in range(div[i], div[i + 1]):
                tmp += G[k][j]
            row.append(tmp)
        rows.append(row)
        
    flag = True
    for row in rows:
        if [r for r in row if r > K]:
            flag = False
            break
    if not flag:
        continue

    tmp_ans = 0
    cnt = [0] * len(rows)
    w = 0

    while w < W:
        for r in range(len(rows)):
            cnt[r] += rows[r][w]
        if [c for c in cnt if c > K]:
            cnt = [0] * len(rows)
            tmp_ans += 1
            w -= 1
        w += 1
    
    tmp_ans += pattern.count(1)
    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(range(2), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h,w,K=map(int,input().split())
s=[]
for i in range(h):
    s.append(input())

ans=float("inf")
for i in range(2**(h-1)):
    cut=[]
    linecount=0
    for j in range(h-1):
        if (i>>j)%2==1:
            cut.append(j)
    counter=[0]*(len(cut)+1)
    for j in range(w):
        ncounter=[0]*(len(cut)+1)
        area=0
        flag=False
        for k in range(h):
            ncounter[area]+=int(s[k][j])
            if counter[area]+ncounter[area]>K:
                if ncounter[area]>K:
                    linecount=float("inf")
                flag=True
            if k in cut:
                area+=1
        if flag:
            counter=ncounter[:]
            linecount+=1
        else:
            for l in range(len(cut)+1):
                counter[l]+=ncounter[l]
    ans=min(ans,linecount+len(cut))
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
s=[list(map(int,list(input()))) for _ in range(h)]
def func(catyoko):
  cattate=0
  past=[0]*10
  for wi in range(w):
    now=[0]*10
    for i in range(1,len(catyoko)):
      for j in range(catyoko[i-1],catyoko[i]):
        now[i-1]+=s[j][wi]
    if max([past[i]+now[i] for i in range(10)])>k:
      if max(now)>k:
        return -10
      else:
        cattate+=1
      past=[nowi for nowi in now]
    else:
      for i in range(10):
        past[i]+=now[i]
  return cattate+len(catyoko)-2



ans=h+w
for i in range(2**(h-1)):
  catyoko=[0]
  for j in range(h-1):
    if ((i>>j) & 1):
      catyoko.append(j+1)
  catyoko.append(h)
  a=func(catyoko)
  
  if a>=0:
    ans=min(ans,a)
print(ans)