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: Accepted

Solution code:
h,w,k = map (int,input().split())
s = [0] * h
aans =10000000
for i in range(h):
    s[i] = [int(i) for i in str(input())]
for i in range(2 ** (h - 1)):
    ans = 0

    kugiri = [0] * (h - 1)
    for j in range(h - 1):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            kugiri[j] = 1

    box = [0] * (sum(kugiri) + 1)
    ans += sum(kugiri)
    for j in range(w): #横に見てる
        
        box[0] += s[0][j]
        num = 0
        for l in range(1,h): #縦に足し合わせる
            num += kugiri[l-1]

            box[num] = s[l][j] + box[num]

        for l in range(len(box)):
            if box[l] > k and j != 0:
                box = [0 for _ in range(sum(kugiri) + 1)]
                num = 0
                box[0] += s[0][j]
                for m in range(1, h):
                    num += kugiri[m - 1]
                    box[num] = s[m][j] + box[num]
                ans += 1
                break
            elif box[l] > k and j == 0:
                ans += 10000000000

    aans =min(aans,ans)


print(aans)

Submission status: Accepted

Solution code:
'''

'''

INF = float('inf')

def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S = [''.join(S[row][col] for row in range(H)) for col in range(W)]
    ans = INF
    for b in range(0, 2**H, 2):
        sections = [(0, H)]
        for shift in range(1, H):
            if (1<<shift) & b:
                sections.append((sections.pop()[0], shift))
                sections.append((shift, H))
        t_ans = len(sections) - 1
        count = {(l, r): 0 for l, r in sections}
        for col in range(W):
            if any(count[(l, r)] + S[col][l:r].count('1') > K for l, r in sections):
                for key in count.keys():
                    count[key] = 0
                t_ans += 1
            for l, r in sections:
                count[(l, r)] += S[col][l:r].count('1')
            if max(count.values()) > K:
                t_ans = INF
                break
        ans = min(ans, t_ans)
    print(ans)


main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())

s=[input() for _ in range(h)]

#hが短いのでhはbit全探索

count=10**9
#print(s)
for i in range(2**(h-1)):
    cnt=bin(i).count("1")

    #yには何行目で割るかが配列ではいる
    y=[]
    for j in range(h-1):
        if (i>>j) &1:
            y.append(j)
    y.append(h-1)
    ruiseki=[0]*(cnt+1)
    #print("y>>>>",y)
    test=0
    flag2=0
    for xx in range(w):
        yyy=0
        flag=0
        for index,yy in enumerate(y):
            while yyy<=yy:
                if s[yyy][xx]=="1":
                    ruiseki[index]+=1
                yyy+=1
        #print(max(ruiseki))
        if max(ruiseki)>k:
            #print("reset")
            cnt+=1
            yyy=0
            ruiseki=[0]*(bin(i).count("1")+1)
            for index,yy in enumerate(y):
                while yyy<=yy:
                    if s[yyy][xx]=="1":
                        ruiseki[index]+=1
                    yyy+=1
            if max(ruiseki)>k:
                #print("kore ha dame")
                flag2=1
                break
        #print(xx,ruiseki)
        #print("count:",cnt)
    if flag2==0:
        count=min(count,cnt)
print(count)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 10 ** 9
    for bit in range(1 << (H-1)):
        canSolve = True
        order = [0] * (H + 1)
        tmp_ans = 0
        for i in range(H):
            if bit & 1 << i:
                order[i+1] = order[i] + 1
                tmp_ans += 1
            else:
                order[i+1] = order[i]
        sum_block = [0] * (H + 1)
        for w in range(W):
            one_block = [0] * (H + 1)
            overK = False
            for h in range(H):
                h_index = order[h]
                one_block[h_index] += S[h][w]
                sum_block[h_index] += S[h][w]
                if one_block[h_index] > K:
                    canSolve = False
                if sum_block[h_index] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                tmp_ans += 1
                sum_block = one_block
            if tmp_ans >= ans:
                canSolve = False
                break
        if canSolve:
            ans = tmp_ans
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  
# 二次元累積和でチョコレートの数を管理
# 直前に選んだチョコのY座標をp,X座標をqとすると、
# チョコレートの数をO(1)で求められる
# 最初に空行を入れているので1-indexで。

for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  
# Hが10と少ないので、切る場所9箇所をすべて試しても2^9 = 512通り
# すべてに対して、Wのどこを切るかを求める。
# 二分探索なら　O(2^(H-1) * (log W * H)) = 約51200
# 線形探索でも　O(2^(H-1) * WH) = 5,120,000

def isOk(x,lastq,cond,K,H,W):
  # xで切ったとき、iで分割されたすべての領域の数がK以下になればOK
  lastp = 0 # Hを最後に切った場所
  for j in range(H-1):
    if (cond >> j) & 1: # j+1で切る
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  # 最後に切った場所から、最後まで
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") # カットした回数
  lastq = 0 # 最後にカットした場所
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cut_num = 10000
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

Submission status: Accepted

Solution code:
import math

h,w,k = map(int,input().split())
s = [str(input()) for i in range(h)]
ans = h * w

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]

    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                key = 0
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        keykey = 1
        for n in range(zerocnt+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    if key:ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
ans=10**18
s=[input() for _ in range(h)]
for i in range(2**(h-1)):
    div=[0]
    for j in range(h-1):
        if (i>>j)&1:
            div.append(j)
    div.append(h-1)
    n=len(div)
    divcnt=[0]*(n-1)
    j=-1
    prev=-1
    cnt=n-2
    ok=True
    while 1:
        l=1
        j+=1
        if j==w:
            break
        for m in range(h):
            if m<=div[l]:
                #print(l,j,m)
                if divcnt[l-1]+int(s[m][j])>k:
                    j-=1
                    #print(prev)
                    if j==prev:
                        #print(divcnt)
                        ok=False
                    else:
                        prev=j
                        cnt+=1
                        #print(cnt)
                        divcnt=[0]*(n-1)
                    break
                else:
                    divcnt[l-1]+=int(s[m][j])
                if m==div[l]:
                    if l<n-1:
                        l+=1
                    else:
                      break
        if not ok:
            break
    if ok:
        ans=min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                for wii in range(ni + 1):
                    if wn[wii] > K:
                        tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

h, w, k = map(int, readline().split())
s = np.array([list(map(int, readline().rstrip().decode())) for _ in range(h)], np.int64)
ans = h + w
for i in range(2 ** (h - 1)):
    wp = np.zeros((h, w), np.int64)
    wq = np.zeros((h, ), np.int64)
    wp[0] = s[0]
    cnt = 0
    for j in range(h - 1):
        if i >> j & 1:
            cnt += 1
        wp[cnt] += s[j + 1]
    if cnt >= ans or np.count_nonzero(wp > k):
        continue
    for j in range(w):
        wq += wp[:, j]
        if np.count_nonzero(wq > k):
            cnt += 1
            wq = wp[:, j]
    if ans > cnt:
        ans = cnt
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from itertools import accumulate
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def border(x):
    # xを二進数で与えた時、ビットの立っている位置のリストを1-indexで返す
    c = 0
    ans = []
    while x > 0:
        c += 1
        if x & 1:
            ans.append(c)
        x >>= 1
    return ans


def main():

    H, W, K = map(int, input().split())
    S = [[0]*W for _ in range(H)]
    for h in range(H):
        S[h][:] = [int(c) for c in input()]
    acc = [[0]+list(accumulate(S[h])) for h in range(H)]

    min_kaisu = +INF
    for h in range(1 << (H-1)):
        # hは分割方法を与える
        # hで与えられる分割方法は、どのような分割なのかを得る。
        startend = border(h)
        flag = False

        division = [0]
        # x番目でW方向に分割すると仮定する
        for x in range(1, W+1):
            # xの位置で分割したとき、左の領域のホワイトチョコレートの数
            # まずは行ごとに求める
            white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
            # 領域ごとに加算するし、最大値を撮る
            white_sum = [sum(white[s:e])
                         for s, e in zip([0]+startend, startend+[H])]
            # print(bin(h), division, x, white_sum)
            white_max = max(white_sum)
            # Kよりも大きくなるなら、事前に分割するべきであった。
            if white_max > K:
                division.append(x-1)
                # 分割してもなおK以下を達成できないケースを除外する
                white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
                white_sum = [sum(white[s:e])
                             for s, e in zip([0]+startend, startend+[H])]
                white_max = max(white_sum)
                if white_max > K:
                    flag = True
                    break
        if flag:
            continue
        # hによる分割も考慮する
        division_tot = len(division)-1 + bit_sum(h)
        min_kaisu = min(division_tot, min_kaisu)
    print(min_kaisu)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現時点の集計でKを超えている値がないかをチェック
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列でok番号に値が入っていた、つまり成り立つ列があった場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    #値が全てK以下だった場合はok変数に列番号を記録
    ans=min(ans,cnt)
       
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現在の集計でKを超えている値がないかをチェック
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列でok番号に値が入っていた、つまり成り立つ列があった場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    #値が全てK以下だった場合はok変数に列番号を記録
    ans=min(ans,cnt)
       
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現在の値がKを超えていないか
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列でok番号に値が入っていた、つまり成り立つ列があった場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    #値が全てK以下だった場合はok変数に列番号を記録
    ans=min(ans,cnt)
       
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
#print H,W,K
#print S

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num
    #print "GROUP :: ",GROUP

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現在の値がKを超えていないか
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                #print "NG!",w
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    #print "IMPOSSIBLE!"
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列で成り立たっていた場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w
    #print "w,ok,cnt,VALUE :: ",w,ok,cnt,VALUE
    ans=min(ans,cnt)
       
print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
#print H,W,K
#print S

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num
    #print "GROUP :: ",GROUP

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    for w in range(W):
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現在の値がKを超えていないか
        for v in VALUE.values():
            if v<=K:
                pass
            else:
                #print "NG!",w
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    #print "IMPOSSIBLE!"
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                else:      #以前の列で成り立たっていた場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w
    #print "w,ok,cnt,VALUE :: ",w,ok,cnt,VALUE
    ans=min(ans,cnt)
       
print ans

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split(sep=" "))
S = [list(map(int,list(input()))) for i in range(0,H,1)]
minimum = H+W
for sepH in range(0,2**(H-1),1):
    bitcounter = 0
    tmp_sepH = sepH
    while tmp_sepH > 0:
        if tmp_sepH & 1 == 1:
            bitcounter+=1
        tmp_sepH = tmp_sepH//2
    A = [[0 for i in range(0,W,1)] for j in range(0,bitcounter+1,1)]
    index=[[]for i in range(0,bitcounter+1,1)]
    countInd = 0
    for i in range(0,H,1):
        index[countInd].append(i)
        if (sepH >> i) & 1:
            countInd +=1
   
    for j in range(0,bitcounter+1,1):
        for i in range(0,W,1):
            for k in range(0,len(index[j]),1):
                if S[index[j][k]][i] == 1:
                    A[j][i]+=1
    countA=[0 for i in range(0,bitcounter+1,1)]
    sepCounter = 0
    dame = False
    for i in range(0,W,1):
        for j in range(0,bitcounter+1,1):
            if A[j][i] > K:
                dame = True
        for j in range(0,bitcounter+1,1):
            countA[j]+=A[j][i]
            if countA[j] > K:
                sepCounter+=1
                for j in range(0,bitcounter+1,1):
                    countA[j] = A[j][i]
                break

    if bitcounter+sepCounter < minimum and (not dame):
        minimum = bitcounter +sepCounter

print(minimum)

Submission status: Accepted

Solution code:
import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  # 1e17
mod = 998244353


def two(x):
    return "0" * (h - 1 - len(bin(x)[2:])) + bin(x)[2:]


h, w, k = map(int, input().split())
S = []
ans = inf
for i in range(h):
    S.append(input().strip())
for way_cut in range(1 << (h - 1)):
    way_cut = two(way_cut)
    number_cut_horizontal = way_cut.count("1")
    number_cut_vertical = 0
    CUT = [-1]
    for i in range(len(way_cut)):
        if way_cut[i] == '1':
            CUT.append(i)
    CUT.append(len(way_cut))
    SUM = [0] * (w)
    PRE = [0] * (w)
    for col in range(w):
        for i in range(1, len(CUT)):
            for between in range(CUT[i - 1] + 1, CUT[i] + 1):
                SUM[i] += 1 if S[between][col] == "1" else 0
        isok = True
        for i in range(1, len(CUT)):
            if PRE[i] + SUM[i] > k:
                isok = False
        if not isok:
            number_cut_vertical += 1
            PRE = copy(SUM)
            SUM = [0]*(w)  # leave out
            # recheck
            for i in range(1, len(CUT)):
                if PRE[i] > k:
                    number_cut_vertical = inf
                    break
        else:
            for i in range(1, len(CUT)):
                PRE[i] += SUM[i]
                SUM[i] = 0
    ans = min(ans, number_cut_vertical + number_cut_horizontal)
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
cho=[input()for i in range(h)]

size=[[0]*h for i in range(1<<h)]
ans=[bin(x).count("1") for x in range(1<<h)]
for stage in range(w):
    new=[[0]*h for i in range(1<<h)]
    for column in range(h):
        if int(cho[column][stage]):
            for bit in range(1<<h):
                length=(((1<<column)-1) & bit).bit_length()
                new[bit][length]+=1
    for bit in range(1<<h):
        frag=True#Trueのままならnewを足し算
        for column in range(h):
            if new[bit][column]+size[bit][column]>k:
                if new[bit][column]>k:#一列の時点でkを超えていたらもう無理
                    ans[bit]+=1010
                frag=False
                ans[bit]+=1
                size[bit]=new[bit]
                break
        if frag:
            for column in range(h):
                size[bit][column]+=new[bit][column]
print(min(ans))

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = float('inf')
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
rsum = [[0] * (W + 1)]
for _ in range(H):
    rsum.append([0])
    tot = 0
    for c, v in enumerate(map(int, input())):
        tot += v
        rsum[-1].append(tot + rsum[-2][c + 1])
ans = 10 ** 10
for i in range(1 << H):
    hcuts = [0]
    for j in range(H - 1):
        if i & (1 << j):
            hcuts.append(j + 1)
    hcuts.append(H)
    vcuts = [0]
    ok = True
    for c in range(1, W + 1):
        for b in range(2):
            max_w = 0
            for h in range(1, len(hcuts)):
                max_w = max(
                    max_w,
                    rsum[hcuts[h]][c]
                    - rsum[hcuts[h - 1]][c]
                    - rsum[hcuts[h]][vcuts[-1]]
                    + rsum[hcuts[h - 1]][vcuts[-1]],
                )
            if max_w > K:
                if b:
                    ok = False
                    break
                vcuts.append(c - 1)
        if not ok:
            break
    if not ok:
        continue
    vcuts.append(W)
    ans = min(ans, len(hcuts) - 2 + len(vcuts) - 2)
print(ans)

Submission status: Accepted

Solution code:
#E
H,W,K = map(int,input().split())
S = [list(str(input())) for _ in range(H)]
inf = float("inf")

ans = inf
T = 2**(H-1)
for i in range(T):
    b = bin(i)
    b = b.lstrip("0b")
    blist = list(b)
    lb = len(b)
    clist = blist[::-1]
    while lb < H-1:
        clist.append("0")
        lb+=1
    
    r = clist.count("1")
    count = r
    nw = [0]*(r+1)
    for w in range(W):
        nind = 0
        for h in range(H):
            if h > 0:
                if clist[h-1] == "1":
                    nind+=1

            if S[h][w] == "1":
                nw[nind]+=1
        
        if w == 0:
            pass
        else:
            for k in nw:
                if k > K:
                    count+=1
                    nw = [0]*(r+1)
                    
                    nind = 0
                    for h in range(H):
                        if h > 0:
                            if clist[h-1] == "1":
                                nind+=1

                        if S[h][w] == "1":
                            nw[nind]+=1
                    
                    if max(nw) > K:
                        count = inf
                    
                    break
    
    ans = min(ans,count)
    
print(ans)