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:
import sys
readline = sys.stdin.buffer.readline

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)

#ビット全探索
def bit_list(dig): #引数に何桁かを入れる
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst
#帰ってくるのは[[0,0,1],[0,1,0],[0,1,1],[1,0,0]...[1,1,1]]のようなリスト

blst = bit_list(h-1)
ans = 10**9
for i in range(len(blst)):
    res = []
    lst1 = [0]*w

    for k in range(w): #分割数はn-1なので、最初の1行目は手動で
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": #分割しない
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)
    flag = 0
    #横分割しなかった部分について、縦分割することで必ず条件を満たせる必要がある。
    for j in res:
        if any(k > g for k in j):
            flag = 1
            break
    if flag:
        continue

    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        if any(l > g for l in count):
            count = now_count
            w_cut += 1


    ans = min(ans,blst[i].count("1")+w_cut)

print(ans)

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [[int(i) for i in list(input())] for _ in range(h)]
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    c = 0
    for ci in [sum(i) for i in zip(*s)]:
        if ci > k:
            cnt[0] = 100000
            break
        c += ci
        if c > k:
            cnt[0] += 1
            c = ci
    minc = cnt[0]
    for i in range(1, 2**(h - 1)):
        div = [j + 1 for j in range(h) if i & 2**j]
        ss = []
        l = 0
        for d in div:
            ss.append(s[l:d])
            l = d
        ss.append(s[l:])
        c = [0] * len(ss)
        t = [[sum(i) for i in zip(*si)] for si in ss]
        for j in range(w):
            if cnt[i] >= minc:
                break
            if max(ti[j] for ti in t) > k:
                cnt[i] = 100000
                break
            for tt, ti in enumerate(t):
                c[tt] += ti[j]
            if max(c) > k:
                cnt[i] += 1
                c = [ti[j] for ti in t]
    print(min(cnt))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [[int(i) for i in list(input())] for _ in range(h)]
    cnt = [bin(i).count("1") for i in range(2**(h - 1))]
    c = 0
    for ci in [sum(i) for i in zip(*s)]:
        if ci > k:
            cnt[0] = 100000
            break
        c += ci
        if c > k:
            cnt[0] += 1
            c = ci
    for i in range(1, 2**(h - 1)):
        div = [j + 1 for j in range(h) if i & 2**j]
        ss = []
        l = 0
        for d in div:
            ss.append(s[l:d])
            l = d
        ss.append(s[l:])
        c = [0] * len(ss)
        t = [[sum(i) for i in zip(*si)] for si in ss]
        for j in range(w):
            if max(ti[j] for ti in t) > k:
                cnt[i] = 100000
                break
            for tt, ti in enumerate(t):
                c[tt] += ti[j]
            if max(c) > k:
                cnt[i] += 1
                c = [ti[j] for ti in t]
    print(min(cnt))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 10**9+7

for i in range(1<<(h-1)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]

    for j in range(1,h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    
    cnt = len(group) - 1
    g_cnt = [0] * len(group)

    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        
        if any([c > k for c in g_cnt]):
            cnt += 1
            for g_id in range(len(group)):
                #縦に切る（グループ全てそこから再開なので全部新規に入れる）
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
    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]=='1'for j in r(b,t[j])),t[j]
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l)
print(m)

Submission status: Accepted

Solution code:
h, w, k = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(h)]
ans = 10**9+7

for i in range(1<<(h-1)):
    group  = [[0] * w]
    g_id = 0
    group[g_id] = [s + b for s, b in zip(S[0], group[0])]

    for j in range(1, h):
        if (i >> (j-1)) & 1:
            g_id += 1
            group.append([0]*w)
        group[g_id] = [s + b for s, b in zip(S[j], group[g_id])]


    #畳み込んだ時点ですでにその列の白チョコの個数がk個より多かったら論外
    if not all([all([i<=k for i in b]) for b in group]):
        continue
    
    cnt = len(group) - 1
    g_cnts = [0] * len(group)

    for jj in range(w):
        for g_id in range(len(group)):
            g_cnts[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnts]):
            cnt += 1
            for g_id in range(len(group)):
                g_cnts[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
  h,*s=open(0)
  h,w,k=map(int,h.split())
  s=[list(map(int,t[:w]))for t in s]
  m=9e9
  for i in range(1<<h-1):
    t=[]
    b=v=l=0
    for j in range(h):
      if i>>j&1:
        t+=map(sum,zip(*s[b:j+1])),
        b=j+1
        l+=1
    t+=map(sum,zip(*s[b:])),
    l+=1
    c=[0]*l
    for i in range(w):
      f=g=0
      u=[]
      for j,d in enumerate(t):
        d=d.__next__()
        u+=d,
        if d>k:
          g=1
          break
        c[j]+=d
        f|=c[j]>k
      else:
        if f:
          c=u
          v+=1
      if g:break
    else:
      if v+l-1<m:m=v+l-1
  print(m)
main()

Submission status: Accepted

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

def divide(pattern):
    lenP = len(pattern)
    divided = [0]*lenP
    count = lenP - 1
    for i in range(lenP):
        if K < pattern[i][0]:
            return H+W
    for i in range(1,W):
        for j in range(lenP):
            if K < pattern[j][i] - divided[j]:
                for l in range(lenP):
                    divided[l] = pattern[l][i-1]
                count += 1
                break
    return count

ans = H+W
for i in range(2**H):
    pattern = []
    line = [0] * W
    for j in range(H):
        for k in range(W):
            line[k] += S[j][k]
        if 2**j & i:
            pattern.append(line)
            line = [0] * W
    pattern.append(line)
    ans = min(divide(pattern),ans)
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7
    H,W,K = LMIIS()
    from itertools import accumulate
    S = [list(accumulate(map(int,input()))) for _ in range(H)]
    


    def divide(pattern):
        lenP = len(pattern)
        divided = [0]*lenP
        count = lenP - 1
        for i in range(lenP):
            if K < pattern[i][0]:
                return H+W
        for i in range(1,W):
            # print('divided=',divided)
            for j in range(lenP):
                if K < pattern[j][i] - divided[j]:
                    for l in range(lenP):
                        divided[l] = pattern[l][i-1]
                    count += 1
                    break
        # print('count=',count)
        return count
                    

            
        



    ans = H+W

    for i in range(2**H):
        pattern = []
        line = [0] * W
        for j in range(H):
            for k in range(W):
                line[k] += S[j][k]
            if 2**j & i:
                pattern.append(line)
                line = [0] * W
        pattern.append(line)
        # print(pattern)
        ans = min(divide(pattern),ans)
    print(ans)
    return
        
    

                

                
                

    

    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    H,W,K = map(int,input().split())
    S = [input()for _ in range(H)]
    ans = 10**9
    for i in range(2**(H-1)):
        aa = 0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                aa+=1
        c = aa
        b = [0]*(c+1)
        OK = True
        for j in range(W):
            k = 0
            for h in range(H):
                if S[h][j] == "1":b[k] += 1
                if (i>>h)&1==1:k+=1
            
            ok = True
            for p in b:
                if p > K:ok = False
            if not ok:
                aa += 1
                b = [0]*(c+1)
                
                k = 0
                for h in range(H):
                    if S[h][j]=="1":b[k] += 1
                    if (i>>h)&1==1:k+=1
                ok = True
                for p in b:
                    if p > K:ok = False
                if not ok:OK = False;break                
        if OK:ans = min(ans,aa)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = 10**9+7

for i in range(1<<(h-1)):
    box = [[0] * w]
    bcnt = 0 #縦のindex

    box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

    #横に適当に線を入れる(=その分のboxを増やす)
    #線が入らなかったらその区画にそのまま値を入れる
    #区画ごとの畳み込み
    for j in range(1, h):
        if (i >> (j-1)) & 1:
            bcnt += 1
            box.append([0] * w)
        box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]

    #
    if not all([all([i<=k for i in b]) for b in box]):
        continue

    
    cutcnt = len(box) - 1 #すでに縦にに切っている分の個数
    cnt = [0] * len(box)    #区画ごとのcntのbox
    #縦ごとにグループに白チョコの個数を追加していく
    for m in range(w):
        for n in range(len(box)):
            cnt[n] += box[n][m] #n番目のグループにbox n番目m列目の個数を追加する
        if any([c > k for c in cnt]):  #グループ内白チョコの個数がkを超えているグループが1つでもあったら縦線を1つ追加する
            cutcnt += 1
            #個数がオーバーしたので改めて今の列を新しいグループの最初の列としてこれから白チョコを追加していく
            for n in range(len(box)):
                cnt[n] = box[n][m]
    ans = min(ans, cutcnt)

print(ans)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

MAX = 10000

def makeMap(H, bits):
    M = [0]*H

    m = 0
    for i in range(H):
        M[i] = m

        if bits & 1:
            m += 1

        bits >>= 1

    return M


def getCounts(H,S,M,w):
    C = [0]*(M[-1]+1)

    for h in range(H):
        if S[h][w] == '1':
            C[M[h]] += 1

    return C


def f(H,W,K,S,bits):
    M = makeMap(H, bits)
    N = M[-1] + 1
    X = [0]*N
    ans = 0
    
#    print("M", M)

    for w in range(W):
        C = getCounts(H,S,M,w)
        for i in range(N):
            if C[i] > K:
                return MAX

            X[i] += C[i]
            if X[i] > K:
                ans += 1
                X = C
                break
#        print("X", X, ans)

#    print("ans", ans, ans + N - 1)
    return ans + N - 1
            
    
H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

# print(S)

ans = MAX

for bits in range(2**(H-1)):
    ans = min(ans, f(H,W,K,S,bits))

print(ans)

Submission status: Accepted

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()
answer = h+w-2
for i in range(max([2**(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    max_board = [0]*(count+1)
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        max_board[k] += 1
      if q == h-1:
        if max(max_board) > kkk:
          flag = False
        break
      if board[q] == 1:
        k += 1
  if not flag:
    continue
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for u in range(count+1):
      if key[u] <= kkk:
        continue
      ans += 1
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Accepted

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

ans = 10 ** 9
# Hが10なので横の割り方は決め打ち、縦は貪欲にKを見る。最小の数が答え。

for i in range(2 ** (h - 1)):
  # box: 割った後の各かたまりの白チョコ数を入れる箱
  box = [[0] * w]
  # bcnt: 横に割ったかたまりの番地を数える数
  bcnt = 0
  box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

  for j in range(1, h):
    if (i >> (j-1)) & 1:
      bcnt += 1
      box.append([0] * w)
    box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]
  
  # kよりも大きな区間が一つでもあればNG
  if not all([all([i <= k for i in b]) for b in box]):
    continue

  # cutcnt: 分割回数。最小値がansとなる。
  cutcnt = len(box) - 1
  # cnt: そのかたまりでのホワイトチョコの数を数える箱。毎回更新する。（直近分しか保持しない）
  cnt = [0] * len(box)
  for m in range(w):
    for n in range(len(box)):
      cnt[n] += box[n][m]
    # 一つでもkを超えたら縦に割る。
    if any([c > k for c in cnt]):
      cutcnt += 1
      for n in range(len(box)):
        cnt[n] = box[n][m]
  ans = min(ans, cutcnt)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
h, w, k = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]

ans = 10 ** 9
# Hが10なので横の割り方は決め打ち、縦は貪欲にKを見る。最小の数が答え。

for i in range(2 ** (h - 1)):
  # 割った後の各かたまりの白チョコ数を入れる箱
  box = [[0] * w]
  # bcnt: 横に割ったかたまりの番地を数える数
  bcnt = 0
  box[bcnt] = [s + b for s, b in zip(S[0], box[bcnt])]

  for j in range(1, h):
    if (i >> (j-1)) & 1:
      bcnt += 1
      box.append([0] * w)
    box[bcnt] = [s + b for s, b in zip(S[j], box[bcnt])]
  
  # kよりも大きな区間が一つでもあればNG
  if not all([all([i <= k for i in b]) for b in box]):
    continue

  cutcnt = len(box) - 1
  cnt = [0] * len(box)
  for m in range(w):
    for n in range(len(box)):
      cnt[n] += box[n][m]
    if any([c > k for c in cnt]):
      cutcnt += 1
      for n in range(len(box)):
        cnt[n] = box[n][m]
  ans = min(ans, cutcnt)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def isOk(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    while left < W:
        right = left
        while right < W and isOk(L, left, right + 1):
            right += 1

        if left == right:
            cnt = 10**18
            break

        cnt += 1
        left = right

    ans = min(ans, cnt - 1)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())

S = []
for _ in range(H):
    S.append(input())

ans = H * W

for c in range(2**(H-1)):
    num_lines = 0

    g = {}
    tmp = c
    g_index = 0
    for h in range(H):
        g[h] = g_index 
        num_groups = g_index 
        if tmp & 1 == 1:
            g_index += 1
        tmp >>= 1

    num_groups += 1
    num_lines = num_groups - 1 
    g_sum = [0] * num_groups

    for w in range(W):
        tmp = g_sum[:]

        ok = True
        ok2 = True
        for h in range(H):
            tmp[g[h]] += int(S[h][w])
        
            if tmp[g[h]] > K :
                # modoru
                ok = False
                if g_sum[g[h]] == 0:
                    ok2 = False

        if ok :
            g_sum = tmp
        else:
            if ok2:
                g_sum = [tmp[gi] - g_sum[gi] for gi in range(num_groups)]
                num_lines += 1
            else:
                break

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

Submission status: Accepted

Solution code:

def main():
    from itertools import product
    import numpy as np

    H,W,K = map(int, input().split())
    S = (np.array([list(map(int,list(input()))) for _ in range(H)]).T).tolist()

    if sum(sum(s) for s in S)<=K:
        print(0)
    else:
        answer = (H-1) * (W-1)
        for X in product([False,True], repeat=H-1):
            ans = np.sum(X)
            if ans >= answer:
                continue
            M = [[0]]
            for i, x in enumerate(X):
                if x:
                    M.append([])
                M[-1].append(i+1)
            D = [0]*len(M)
            for s in S:
                for k, m in enumerate(M):
                    D[k] += sum(s[i] for i in m)
                if any(d > K  for d in D):
                    ans += 1
                    if ans >= answer:
                        break
                    for k, m in enumerate(M):
                        D[k] = sum(s[i] for i in m)
                    
                    if any(d > K for d in D):
                        ans = answer + 1
                        break

            answer = min(answer,ans)

        print(answer)

main()

Submission status: Accepted

Solution code:
import math
import time
from collections import deque
from collections import defaultdict
from copy import deepcopy
import heapq

mod = 10 ** 9 + 7
t = time.time()



def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret


def conbination(n, r, mod):
    if n < r:
        return 0

    if r == 0 or n == 0:
        return 1

    ret = 1
    for i in range(n-r+1, n+1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r+1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    #print(f"conbination {n}, {r} = {ret}")
    return ret

def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def main():
    H, W, K = iip()

    chocos = []
    for i in range(H):
        chocos.append(input())


    result = 9999
    for i in range(2**(H-1)):
        hbin = bin(i)[2:].zfill(H-1)

        lines = []
        cur = []
        for i in range(H):
            cur.append(i)
            if i <= H-2 and hbin[i] == "1":
                lines.append(cur)
                cur = []
        lines.append(cur)
        cnum = cracknum(lines, W, K, chocos) + hbin.count("1")
        result = min(result, cnum)

    print(result)

def cracknum(lines, W, K, chocos):
    volumes = [0 for i in lines]
    result = 0
    for x in range(W):
        crack = False
        for line, y_list in enumerate(lines):
            for y in y_list:
                if chocos[y][x] == "1":
                    volumes[line] += 1
                    #print(y, x)
                    #print(volumes)
                    if volumes[line] > K:
                        crack = True
                        #print("crack")
                        break
            if crack:
                break

        if crack:
            result += 1
            volumes = [0 for i in lines]
            for line, y_list in enumerate(lines):
                for y in y_list:
                    if chocos[y][x] == "1":
                        volumes[line] += 1
                        if volumes[line] > K:
                            return 9999
    #print(result)
    return result





main()

Submission status: Accepted

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

minimum = (h - 1) * (w - 1)
for div_h in range(1 << (h - 1)):
  h_index = [0] * h
  cur_index = 0
  mask = 1 << (h - 2)
  for i in range(1, h):
    if div_h & mask:
      cur_index += 1
    h_index[i] = cur_index
    mask >>= 1
  white_choco = [0] * (cur_index + 1)
  divide = 0
  j = 0
  flag = False
  while j < w:
    for i in range(h):
      white_choco[h_index[i]] += s[i][j]
    if max(white_choco) > k:
      if flag:
        break
      flag = True
      white_choco = [0] * (cur_index + 1)
      divide += 1
    else:
      j += 1
      flag = False
  else:
    minimum = min(minimum, divide + cur_index)
print(minimum)

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s.append(list(map(int, list(input()))))
s = np.array(s)

def count(li):
    if np.max(li) > k:
        return -1
    tmp = np.zeros(len(li), dtype=int)
    cnt = len(li)-1
    for i in range(w):
        tmp += li[:, i]
        if np.max(tmp) > k:
            cnt += 1
            if cnt >= ans:
                return -1
            tmp = li[:, i]
    return cnt

ans = 1000000
for i in range(2**(h-1)):
    r = 0
    l = []
    for j in range(h-1):
        if (i>>j)&1:
            l.append(np.sum(s[r:j+1, :], axis=0))
            r = j+1
    l.append(np.sum(s[r:, :], axis=0))
    if ans <= len(l)-1:
        continue
    cnt = count(np.vstack(l))
    if cnt>=0:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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

def nl(a, b):
    return [[0]*b for _ in range(a)]

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

ans = float('inf')
for bit in range(1<<(H-1)):
    id_of = [0]*H
    g = 0
    
    for i in range(H):
        id_of[i] = g
        if bit >> i & 1:
            g += 1
    
    g += 1
    count = g - 1

    # グループごとに統合
    group_sum = nl(H, W)
    for i in range(H):
        for j in range(W):
            group_sum[id_of[i]][j] += S[i][j]

    # 縦方向に分割
    now = [0]*g
    for j in range(W):
        if not add(j):
            count += 1
            now = [0]*g
            if not add(j):
                count = float('inf')
                break
    
    ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())
    white = np.array([[n for n in map(int, S)] for S in args[1:]])

    ret = h*w
    for b in range(2**(h-1)):
        h_cuts = list(i+1 for i in range(h-1) if (b >> i) & 1 == 1)
        count = len(h_cuts)
        if ret < count:
            continue

        A = np.array(list(x.sum(axis=0) for x in np.vsplit(white, h_cuts)))
        if (k < A).any():
            continue

        S = np.zeros((1, len(A)), dtype=int)
        for x in range(w):
            S += A[:, x]
            if (k < S).any():
                S = A[:, x]
                count += 1
                if ret < count:
                    break

        ret = min(ret, count)

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

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

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

  print(ans)
  
main()

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=h+w-2
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    if flag:
        continue
    ans=min(ans,now+y)
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

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


def f(i1, j1, i2, j2):
    return cs[i1][j1] - cs[i1][j2] - cs[i2][j1] + cs[i2][j2]


ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1:
            border.append(i + 1)
            cand += 1
    border.append(h)

    # 貪欲に縦の線に沿って折る
    j0 = 0
    for j in range(w):
        for i in range(len(border) - 1):
            if f(border[i + 1], j + 1, border[i], j0) > k:
                cand += 1
                j0 = j
                break

    # 最後に残ったピースたちがk以下かチェック
    is_possible = True
    for i in range(len(border) - 1):
        if f(border[i + 1], w, border[i], j0) > k:
            is_possible = False
            break

    if is_possible:
        ans = min(ans, cand)
print(ans)

Submission status: Accepted

Solution code:
import itertools
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
#print(S)
l=[]
id=[0]*H
tables=[[0 for _ in range(W)] for _ in range(H)]
gnum=0
ans=0
mi=float("inf")
impossibleflag=0
for k in range(pow(2,H-1)):
    for i in range(H):
        id[i]=gnum
        if (k>>i)&1:    #kが2^iを持つかどうか
            gnum=gnum+1 #持っていればそこが琴線でありそこで分ける
    gnum=gnum+1         #0~gnumのグループ番号があるので、グループ数はgnum+1
    #print(id)
    tables = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            tables[id[i]][j]=tables[id[i]][j]+int(S[i][j])
    ans=ans+gnum-1  #とりあえず素のgroup数-1こ線を引かないといけない
    #print(ans)
    #print(tables)
    groupedwchoko=[0 for _ in range(gnum)]  #横線で分割したグループを左から貪欲するのに使うやつ
    for i in range(W):
        for j in range(gnum):
            groupedwchoko[j]=groupedwchoko[j]+tables[j][i]  #各グループにて(0<=j<=gnum-1)、wchokoの数をtables[j][i]を足していく
            #print(tables[j][i])
            if groupedwchoko[j]>K:      #もし、どれか一つでも結果がKを越えれば
                ans=ans+1               #そこと一つ前部分の間で線を引くことに
                groupedwchoko = [0 for _ in range(gnum)]
                for l in range(gnum):
                    groupedwchoko[l]=tables[l][i]   #各グループにて(0<=l<=gnum-1)、wchokoの数はtables[l][i]で初期化される
                    if tables[l][i]>K:              #初期化時点でKを超えるのは
                        ans=float("inf")            #どう頑張ってもムリということである
                break
        #print(groupedwchoko)
    #print(ans)
    if mi>ans:
        mi=ans
    gnum=0
    ans=0

print(mi)