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



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
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~g:m=min(m,v+l)
print(m)

Submission status: Wrong Answer

Solution code:
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(len(div)):
        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]
  return ret

# 縦の分割の仕方はpow(2,h-1)
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)
  ans=min(ans,a+len(div)-2)
print(ans)

Submission status: Wrong Answer

Solution code:
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)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        #    cnt=10010010
        #    break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
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 = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Wrong Answer

Solution code:
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 += 1
        flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Wrong Answer

Solution code:
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 S_t[j][bh[k+1]-1] > K:
          j += 1
        flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Wrong Answer

Solution code:
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 S_t[j][H-1] > K:
          j += 1
        flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
# 2次元累積和
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])
#print(acum)


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)
    #print(hlist)
    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")
            # kを超えてはいけないが、一個右で縦に割るとｋを超える必要がある（貪欲にやるので）
            elif white_choco_count(x1, y1, x2, y2) <= k < white_choco_count(x1, y1, x2+1, y2):
                count += 1
                # 次のブロックにいくのでx1更新(ただしy1の更新はx2がｗまでおわったあとにしたいのでbreak使うとうまくいく）
                x1 = x2
                break
            y1 = y2

    #print(count)
    ans = min(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
# 2次元累積和
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])
#print(acum)


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)
    #print(hlist)
    x1 = 0
    for x2 in range(x1, w):
        y1 = 0
        for y2 in hlist:
            if white_choco_count(x1, y1, x2, y2) > k:
                count += float("inf")
            # kを超えてはいけないが、一個右で縦に割るとｋを超える必要がある（貪欲にやるので）
            if white_choco_count(x1, y1, x2, y2) <= k < white_choco_count(x1, y1, x2+1, y2):
                count += 1
                # 次のブロックにいくのでx1更新(ただしy1の更新はx2がｗまでおわったあとにしたいのでbreak使うとうまくいく）
                x1 = x2
                break
            y1 = y2

    #print(count)
    ans = min(ans, count)
print(ans)

Submission status: Wrong Answer

Solution code:
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)]
    
    print(H,W,S)
    
    white = 0
    for line in S:
        white += sum(line)
 
    if white <= K:
        print(0)
        exit()
 
    Pdb().set_trace()
    # 横線の決め方を全探索
    ans = 10**5
    
    #yに横線Patternごとの列合計を作成
    #入力例１のPattern[bin(2)]場合、y=[[1,1,1,0,0], [1,0,1,1,2]]
    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]
                #print("横Pattern{} 縦列まで　{} カウント数{} 縦線の数{}".format(i, j, count[i], x))
                #横Patten毎にｊ列までのホワイトチョコ合計数をカウント、
                #カウント＞Kとなったら、縦線数を＋１、その列値でカウント数を初期化
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j]
                    break
            #x縦線の数 + ly横線の数がAnsより大きくなったらBreak
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6
        #x縦線の数 + ly横線の数がAnsより小さくなったらAnsを更新
        ans = min(ans, x + ly)
 
    print(ans)

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
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]+=(s[k][j]=="1")
            if counter[area]+ncounter[area]>K:
                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)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=H+W-2
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    for w in range(W):
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                if cum>K:
                    go=False
                cum+=S[h][w]
            c[g]+=cum
            if cum+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[c[i] for i in range(glen)]
        else:
            for i in range(glen):
                group[i]+=c[i]
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=10**18
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    res=glen-1
    go=True
    for w in range(W):
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                if cum>K:
                    go=False
                cum+=S[h][w]
            c[g]+=cum
            if cum+group[g]>K:
                ok=False
        if not go:
            break
        if not ok:
            res+=1
            group=[c[i] for i in range(glen)]
        else:
            for i in range(glen):
                group[i]+=c[i]
    if not go:
        continue
    ans=min(ans,res)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for i in range(H)]
ans=10**18
for bit in range(2**(H-1)):
    divH=[0]
    for j in range(H-1):
        if(bit>>j&1):
            divH.append(j+1)
    divH.append(H)
    glen=len(divH)-1
    group=[0]*(glen)
    divW=[]
    for w in range(W):
        go=True
        ok=True
        c=[0]*(glen)
        for g in range(glen):
            cum=0
            for h in range(divH[g],divH[g+1]):
                if cum>K:
                    go=False
                cum+=S[h][w]
            c[g]+=cum
            if cum+group[g]>K or not go:
                ok=False
        if not go:
            break
        if not ok:
            divW.append(w)
            group=[c[i] for i in range(glen)]
        else:
            for i in range(glen):
                group[i]+=c[i]
    if not go:
        continue
    ans=min(ans,len(divW)+len(divH)-2)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,K = map(int, input().split())
g = [[0]*w for _ in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        g[i][j] = s[j]
ans=1001001001
for i in range(1<<(h-1)):
    seg = [0]*h
    segnow = 0
    for j in range(h-1):
        if i & 1 << j:
            segnow += 1
        seg[j+1] = segnow

    segnow += 1
    cnt = [0 for _ in range(segnow)]
    l = [list() for _ in range(segnow)]
    r = [list() for _ in range(segnow)]
    flag = True
    for j in range(w):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    l[seg[k]].append(j)
                    cnt[seg[k]] -= K - now[seg[k]]+1
        if max(now)>K:
            flag =False
    if not flag:
        continue
    cnt = [0 for _ in range(segnow)]               
    for j in reversed(range(w)):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    r[seg[k]].append(j+1)
                    cnt[seg[k]] -= K- now[seg[k]]+1

    t = set()
    for j in range(segnow):
        nj = len(r[j])
        for k in range(nj):
            t.add((r[j][nj-k-1],l[j][k]))
    t=list(t)
    t.sort(key=lambda x:x[1])
    div=0
    now =-1
    for j in range(len(t)):
        if t[j][0]>now:
            div += 1
            now = t[j][1]
    if flag:
        ans = min(ans,segnow-1+div)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,K = map(int, input().split())
g = [[0]*w for _ in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        g[i][j] = s[j]
ans=1001001001
for i in range(1<<(h-1)):
    seg = [0]*h
    segnow = 0
    for j in range(h-1):
        if i & 1 << j:
            segnow += 1
        seg[j+1] = segnow

    segnow += 1
    cnt = [0 for _ in range(segnow)]
    l = [list() for _ in range(segnow)]
    r = [list() for _ in range(segnow)]
    flag = True
    for j in range(w):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    l[seg[k]].append(j)
                    cnt[seg[k]] -= K - now[seg[k]]+1
        if max(now)>K:
            flag =False
    if not flag:
        continue
    cnt = [0 for _ in range(segnow)]               
    for j in reversed(range(w)):
        now = [0]*segnow
        for k in range(h):
            if g[k][j] == '1':
                cnt[seg[k]] += 1
                now[seg[k]] += 1
                if cnt[seg[k]] > K:
                    r[seg[k]].append(j+1)
                    cnt[seg[k]] -= K- now[seg[k]]+1

    for j in range(segnow):
        r[j].sort()

    t = list()
    for j in range(segnow):
        for k in range(len(r[j])):
            t.append([r[j][k],l[j][k]])
    t.sort(key=lambda x:x[1])
    div=0
    now = -1

    for j in range(len(t)):
        if t[j][0]>now:
            div += 1
            now = t[j][1]
    ans = min(ans,segnow-1+div)
print(ans)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1や W=1の場合は普通に貪欲で。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res


if H != 1 and W != 1:
    # 全区切りで割った場合が最大
    ans = (H-1) + (W-1)
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0
        # 横直線方向で割る場合は、その箇所のindexを保持
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)

        cnt_blocks = cnt_split_h + 1
        cnt_whites = [0] * (cnt_blocks)
        ex_cnt_whites = [0] * (cnt_blocks)
        ex_x = 0
        for x in range(W):

            # 一列だけにしてもKを超えるブロックがあるので、この横直線の分割はできない
            if not can_split_h:
                break

            for y in range(H):
                if S[y][x] == "1":
                    if cnt_split_h > 0:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            # それぞれKを超えていないか確認
            is_over = is_over_K(cnt_whites, cnt_blocks)

            
            if not is_over:
                # Kを超えないので、さらにxを追加して見ていく
                # xまでで各ブロックでホワイトチョコがいくつあるか保持（次のxでKを超えた場合に、差分を利用するので）
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                # Kを超えるのでxの左の縦直線でわる
                cnt_split_w += 1
                # xの左の縦直線で割った場合のホワイトチョコの個数を求める（現在のxのみの個数）
                for i in range(cnt_blocks):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = 0
                # 一列だけにしてもKを超えるなら、その横直線の分割はできない
                if is_over_K(cnt_whites, cnt_blocks):
                    can_split_h = False
                    break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)

# H=1, W=1の場合忘れとった...
elif H == 1:
    ans = 0
    cnt = 0
    for i in range(W):
        if S[0][i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1
else:
    ans = 0
    cnt = 0
    for i in range(H):
        if S[i][0] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1

print(ans)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1や W=1の場合は普通に貪欲で。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res


if H != 1 and W != 1:
    ans = (H-1)*(W-1)
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0
        # 横直線方向で割る場合は、その箇所のindexを保持
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)


        cnt_whites = [0] * (cnt_split_h + 1)
        ex_cnt_whites = [0] * (cnt_split_h + 1)
        ex_x = 0
        for x in range(W):

            # 一列だけにしてもKを超えるブロックがあるので、この横直線の分割はできない
            if not can_split_h:
                break

            for y in range(H):
                if S[y][x] == "1":
                    """
                    S[y][x]がどのブロックに属するか

                    """
                    if cnt_split_h > 0:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            # それぞれKを超えていないか確認
            is_over = is_over_K(cnt_whites, cnt_split_h+1)

            
            if not is_over:
                # Kを超えないので、さらにxを追加して見ていく
                # xまでで各ブロックでホワイトチョコがいくつあるか保持（次のxでKを超えた場合に、差分を利用するので）
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                # Kを超えるのでxの左の縦直線でわる
                cnt_split_w += 1
                # xの左の縦直線で割った場合のホワイトチョコの個数を求める（現在のxのみの個数）
                for i in range(cnt_split_h+1):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = 0
                # 一列だけにしてもKを超えるなら、その横直線の分割はできない
                if is_over_K(cnt_whites, cnt_split_h+1):
                    can_split_h = False
                    break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)
# H=1, W=1の場合忘れとった...
elif H == 1:
    ans = 0
    cnt = 0
    for i in range(W):
        if S[0][i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1
else:
    ans = 0
    cnt = 0
    for i in range(H):
        if S[i][0] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1

print(ans)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1の場合は普通に。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res

ans = (H-1)*(W-1)
if H != 1:
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0
        # 横直線方向で割る場合は、その箇所のindexを保持
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)


        cnt_whites = [0] * (cnt_split_h + 1)
        ex_cnt_whites = [0] * (cnt_split_h + 1)
        ex_x = 0
        for x in range(W):

            # 一列だけにしてもKを超えるブロックがあるので、この横直線の分割はできない
            if not can_split_h:
                break

            for y in range(H):
                if S[y][x] == "1":
                    """
                    S[y][x]がどのブロックに属するか

                    """
                    if cnt_split_h > 0:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            # それぞれKを超えていないか確認
            is_over = is_over_K(cnt_whites, cnt_split_h+1)

            
            if not is_over:
                # Kを超えないので、さらにxを追加して見ていく
                # xまでで各ブロックでホワイトチョコがいくつあるか保持（次のxでKを超えた場合に、差分を利用するので）
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                # Kを超えるのでxの左の縦直線でわる
                cnt_split_w += 1
                # xの左の縦直線で割った場合のホワイトチョコの個数を求める（現在のxのみの個数）
                for i in range(cnt_split_h+1):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = 0
                # 一列だけにしてもKを超えるなら、その横直線の分割はできない
                if is_over_K(cnt_whites, cnt_split_h+1):
                    can_split_h = False
                    break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)
# H=1の場合忘れとった...
else:
    cnt = 0
    for i in range(W):
        if S[0][i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1
print(ans)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left

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

"""
H <= 10までなので、横直線方向の割り方を全探索できそう
縦直線方向の割り方は貪欲か。
横直線の割方が決まったら、次は縦に割っていくが、ブロックの横幅を1にしても、ブロックないのホワイトチョコがKを超える場合もありうるので、その場合は、その横直線の割り方で条件を満たすことはできない


H=1の場合は普通に。
"""


def is_over_K(lst, block_num):
    res = False
    for i in range(block_num):
        if lst[i] > K:
            res = True
            break
    return res

ans = (H-1)*(W-1)
if H != 1:
    for bit in range(1 << (H-1)):
        can_split_h = True
        cnt_split_h = bin(bit).count("1")
        cnt_split_w = 0
        # 横直線方向で割る場合は、その箇所のindexを保持
        if cnt_split_h >= 1:
            idx_split_h = []
            for i in range(H-1):
                if bit & (1 << i):
                    idx_split_h.append(i)
        

        cnt_whites = [0] * (cnt_split_h + 1)
        ex_cnt_whites = [0] * (cnt_split_h + 1)
        ex_x = 0
        for x in range(W):

            # 一列だけにしてもKを超えるブロックがあるので、この横直線の分割はできない
            if not can_split_h:
                break

            for y in range(H):
                if S[y][x] == "1":
                    """
                    S[y][x]がどのブロックに属するか

                    """
                    if cnt_split_h > 0:
                        block_num = bisect_left(idx_split_h, y)
                    else:
                        block_num = 0

                    cnt_whites[block_num] += 1
            
            # それぞれKを超えていないか確認
            is_over = is_over_K(cnt_whites, cnt_split_h+1)

            
            if not is_over:
                # Kを超えないので、さらにxを追加して見ていく
                # xまでで各ブロックでホワイトチョコがいくつあるか保持（次のxでKを超えた場合に、差分を利用するので）
                for i in range(cnt_split_h+1):
                    ex_cnt_whites[i] = cnt_whites[i]
            else:
                # Kを超えるのでxの左の縦直線でわる
                cnt_split_w += 1
                # xの左の縦直線で割った場合のホワイトチョコの個数を求める（現在のxのみの個数）
                for i in range(cnt_split_h+1):
                    cnt_whites[i] -= ex_cnt_whites[i]
                    ex_cnt_whites[i] = 0
                # 一列だけにしてもKを超えるなら、その横直線の分割はできない
                if is_over_K(cnt_whites, cnt_split_h+1):
                    can_split_h = False
                    break
        
        if can_split_h:
            ans = min(ans, cnt_split_h + cnt_split_w)

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for _ in range(h)]
ans = (h-1)+(w-1)
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)