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:
from itertools import combinations

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

separators = []
for i in range(2 ** (H - 1)):
    separators.append([(i >> j) & 1 for j in range(H - 1)])
separators.sort(key=sum)

for i in range(len(separators)):
    ids = [0]
    for j in separators[i]:
        ids.append(ids[-1] + j)
    separators[i] = ids

min_ = H - 1 + W - 1
for ids in separators:
    size = ids[-1] + 1
    nums = [0] * size
    num_cuts = size - 1
    if min_ <= num_cuts:
        continue
    for row in range(H):
        nums[ids[row]] += S[row][0]
    if any(K < n for n in nums):
        continue
    ignore = False
    for col in range(1, W):
        adds = [0] * size
        for row in range(H):
            adds[ids[row]] += S[row][col]
        if any(K < nums[i] + adds[i] for i in range(size)):
            if any(K < a for a in adds):
                ignore = True
                break
            num_cuts += 1
            if min_ <= num_cuts:
                ignore = True
                break
            for i in range(size):
                nums[i] = adds[i]
        else:
            for i in range(size):
                nums[i] += adds[i]
    if not ignore:
        min_ = min(num_cuts, min_)
print(min_)

Submission status: Accepted

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

CHOCO = [[] for _ in range(1<<(H-1))]
cnt = [10**9] * (1<<(H-1))

for i in range(1<<(H-1)):
    S = 0
    ret = []
    flag = True
    for j in range(H - 1):
        S += B[j][0]
        if i & (1<<j):
            if S > K:
                flag = False
            ret.append(S)
            S = 0
    S += B[-1][0]
    if S > K:
        flag = False
    ret.append(S)
    if flag:
        CHOCO[i] = ret[:]
        cnt[i] = len(ret) - 1


for w in range(1,W):
    for i in range(1 << (H - 1)):
        if not CHOCO[i]: continue

        S = 0
        ret = []
        flag1 = True
        for j in range(H - 1):
            S += B[j][w]
            if i & (1 << j):
                if S > K:
                    flag1 = False
                ret.append(S)
                S = 0
        S += B[-1][w]
        ret.append(S)

        flag2 = True

        for j in range(len(ret)):
            if ret[j] + CHOCO[i][j] > K:
                flag2 = False

        if flag1:
            if flag2:
                for j in range(len(ret)):
                    CHOCO[i][j] += ret[j]
            else:
                CHOCO[i] = ret[:]
                cnt[i] += 1
        else:
            CHOCO[i] = []

print(min(cnt))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

h, w, K = map(int, input().split())
field = []
field_int = []
for _ in range(h):
    s = input().rstrip()
    line = [int(item) for item in s]
    field.append(line)

ans = 10**5
for i in range(2**(h-1)):
    group = [0]
    g = 0
    for j in range(h-1):
        if i & 1 << j: 
            g += 1
            group.append(g)
        else:
            group.append(g)
    line_num = bin(i).count("1") + 1
    cnt = [0] * line_num
    ret = 0
    ok = True
    for j in range(w):
        tmp = [0] * line_num
        for k in range(h):
            tmp[group[k]] += field[k][j]
        should_cut = False
        for c, t in zip(cnt, tmp):
            if t > K:
                ok = False
            if c + t > K:
                should_cut = True
        if not should_cut:
            for i, t in enumerate(tmp):
                cnt[i] += t
        else:
            ret += 1
            for i, t in enumerate(tmp):
                cnt[i] = t
    if not ok:
        continue
    ans = min(ans, ret + line_num - 1)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
setrecursionlimit(10**6)

def array2D(row, col ,val=0):
    return [[val]*col for i in range(row)]

from itertools import product
import numpy as np

def c():
    INF = 10**9+1
    ans = INF
    for v in product(range(2), repeat=h-1):
        idx = 0
        K = []
        for i,j in enumerate(v):
            if j==1:
                K.append(S[idx:i+1, :].sum(axis=0).tolist())
                idx = i+1
        K.append(S[idx:, :].sum(axis=0).tolist())

        res = sum(list(v))
        s = [0]*(len(K))
        for i in range(w):
            f = False
            for j in range(len(K)):
                if s[j] + K[j][i] > k:
                    f = True
                    if K[j][i] > k:
                        res += INF
            if f:
                res += 1
                for j in range(len(K)):
                    s[j] = K[j][i]
            else:
                for j in range(len(K)):
                    s[j] += K[j][i]

        ans = min(res, ans)
    return ans




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

S = np.array(S)
print(c())

Submission status: Accepted

Solution code:
import sys
h, w, k = [int(i) for i in sys.stdin.readline().split()]
s_ls = {}
for i in range(h):
    s_ls[i] = [int(j) for j in sys.stdin.readline().strip()]

best = h - 1 + w - 1
for i in range(1 << (h - 1)):
    flg = True
    s = bin(i)[2:].zfill(h-1)
    ls = {i for i, j in enumerate(s) if j == "1"}
    dict = {i : 0 for i in range(len(ls) + 1)}
    cnt = 0
    for _w in range(w):
        j = 0
        col_sums = {i : 0 for i in range(len(ls) + 1)}
        for _h in range(h):
            val = s_ls[_h][_w]
            col_sums[j] += val
            dict[j] += val
            if _h in ls:
                j += 1
        if max(dict.values()) > k:
            cnt += 1
            dict = col_sums
        if max(col_sums.values()) > k:
            flg = False
        if not flg:
            break
    if flg:
        best = min(best , cnt + len(ls))
print(best)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = []
for i in range(h):
    temp = list(input())
    temp = list(map(int, temp))
    s.append(temp)
ans = 2000
for i in range(2 ** (h - 1)):
    line = 0
    temp = bin(i + 2 ** (h - 1))
    group = [[0]]
    for j in range(h - 1):
        if temp[-1-j] == "0":
            group[-1].append(j + 1)
        else:
            group.append([j + 1])
            line += 1
    count = [0] * len(group)
    for j in range(w):
        for l in range(len(group)):
            for m in group[l]:
                count[l] += s[m][j]
        flag = True
        for l in count:
            if l > k:
                flag = False
                break
        if flag == False:
            line += 1
            count = [0] * len(group)
            for l in range(len(group)):
                for m in group[l]:
                    count[l] += s[m][j]
    flag = True
    for j in count:
        if j > k:
            flag = False
            break
    if flag == False:
        line = 2000
    ans = min(ans, line)
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

Submission status: Accepted

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

count=[]
for i in range(h):
  L=[0]
  for j in range(w):
    L.append(int(l[i][j])+L[-1])
  count.append(L)

b=[]
for i in range(2**(h-1)):
  b.append(format(i,'0'+str(h-1)+'b'))

ans=[]
cut=0
for i in range(len(b)):
  cutct=0
  cut=0
  f=0
  for j in range(1,w+1):
    ct=[]
    for j2 in range(h):
      ct.append(count[j2][j]-count[j2][cut])
    check=[]
    x=ct[0]
    for j3 in range(h-1):
      if b[i][j3]=='0':
        x+=ct[j3+1]
      else:
        check.append(x)
        x=ct[j3+1]
    check.append(x)
    if max(check)>k:
      if cut-j<=1:
        ctcheck=[]
        for j2 in range(h):
          ctcheck.append(count[j2][j-1]-count[j2][cut])
        check=[]
        x=ctcheck[0]
        for j3 in range(h-1):
          if b[i][j3]=='0':
            x+=ctcheck[j3+1]
          else:
            check.append(x)
            x=ctcheck[j3+1]
        check.append(x)
        if max(check)>k:
          f=1
      cut=j-1
      cutct+=1
  ct1=0
  for j4 in range(h-1):
    if b[i][j4]=='1':
      ct1+=1
  if f==0:
    ans.append(cutct+ct1)
print(min(ans))

Submission status: Accepted

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

S = [list(map(int, input())) for _ in range(h)]
#print(S)
min_v = 10**18
for i in range(2**(h-1)):
  cnt = [0]*h
  row = [0]*h
  splt_cnt = 0
  splt = [0]*(h-1)
  find = 1
  for j in range(h-1):
    if (i>>j)&1:
      splt[j] = 1
  
  for x in range(1, h):
    if splt[x-1]==0:
      row[x] = row[x-1]
    elif splt[x-1]==1:
      row[x] = row[x-1] + 1
  #print(row, splt)
  for c in range(w):
    for r in range(h):
      #print(c,r)
      cnt[row[r]] += S[r][c]
    #print(max(cnt))
    if max(cnt)>k:
      cnt = [0] * h
      splt_cnt += 1
      for r in range(h):
        cnt[row[r]] += S[r][c]
      if max(cnt)>k:
        find = 0
  
  splt_cnt += sum(splt)
  #print('split _ %i'%sum(splt))
  if splt_cnt<min_v and find:
    min_v = splt_cnt

print(min_v)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
S = [[] for _ in range(h)]
for i in range(h):
    s = str(input())
    for x in s:
        S[i].append(int(x))

ans = 10**5
dame = False

for bit in range(1<<h-1):
    h_cut_count = 0
    Cut_line = []
    for i in range(9):
        if (bit>>i)&1 == 1:
            h_cut_count += 1
            Cut_line.append(i)
    # print(Cut_line)

    before_line = -1
    Blocks = []

    for j in range(len(Cut_line)):
        if before_line == -1:
            Blocks.append(S[:Cut_line[j]+1])
            before_line = Cut_line[j]
        else:
            Blocks.append(S[before_line+1:Cut_line[j]+1])
            before_line = Cut_line[j]
    if before_line == -1:
        Blocks.append(S[:])
    else:
        Blocks.append(S[before_line+1:])
    
    Block_count = [0 for _ in range(len(Blocks))]

    v_cut_count = 0

    for i in range(w):
        for j in range(len(Blocks)):
            for column in Blocks[j]:
                if column[i] == 1:
                    Block_count[j] += 1
        if max(Block_count) > k:
            Block_count = [0 for _ in range(len(Blocks))]
            v_cut_count += 1
            for j in range(len(Blocks)):
                for column in Blocks[j]:
                    if column[i] == 1:
                        Block_count[j] += 1
            if max(Block_count) > k:
                dame = True

    if dame == False:
        cand = h_cut_count + v_cut_count
    elif dame == True:
        cand = 10**5
    ans = min(cand, ans)
    dame = False

    # print(Blocks)
    # print(cand)
    # print('-'*30)
    
    

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import itertools
H, W, K = map(int, readline().split())
S = [list(map(int, line.rstrip().decode())) for line in readlines()]
# transpose
S = tuple(itertools.chain(*zip(*S)))

INF = 10 ** 9


def solve(s):
    dp = list(S)
    for j in range(H - 1):
        if s & (1 << j):
            for n in range(0, H * W, H):
                dp[n + j + 1] += dp[n + j]
    cut = H - 1 - bin(s).count('1')
    for n in range(0, H * W, H):
        if any(dp[n + i] > K for i in range(H)):
            return INF
        if n + H == H * W:
            return cut
        if any(dp[n + i] + dp[n + i + H] > K for i in range(H)):
            cut += 1
            continue
        for i in range(H):
            dp[n + i + H] += dp[n + i]
    return cut


answer = min(solve(s) for s in range(1 << (H - 1)))
print(answer)

Submission status: Accepted

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

def judge(num):
    for i in range(2**(h-1)+1):
        jc = 0
        gr = []
        tmp = []
        for j in range(h-1):
            tmp.append(j)
            if (i >> j)&1 == 1:
                gr.append(tmp)
                tmp = []
                jc+=1
        tmp.append(h-1)
        gr.append(tmp)
        if jc > num:
            continue
        xc = 0
        tmpc = [0] * (jc+1)
        brf = False
        for j in range(w):
            di = [0]* (jc+1)
            for k in range(jc+1):
                for l in gr[k]:
                    di[k]+=mapi[l][j]
                    if di[k] > K:
                        brf = True
                        break
                if tmpc[k] + di[k] > K:
                    for m in range(jc+1):
                        tmpc[m] = 0
                    xc+=1
                    if xc + jc > num:
                        brf = True
                        break
                if brf:
                    break
            if brf:
                break
            for l in range(jc+1):
                tmpc[l] += di[l]
        if brf:
            continue
        return True
    return False

mmin = 0
mmax = (h-1)*(w-1)
if judge(mmin) == True:
    print(0)
    exit()
while True:
    mid = (mmin + mmax)//2
    if judge(mid) == True:
        mmax = mid
    else:
        mmin = mid
    if mmin +1 == mmax:
        print(mmax)
        exit()

Submission status: Accepted

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [0] * (hcut+1)
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            whites = thisline
            m = max(whites)
            cur += 1
            if cur >= ans or m > K:
                break
    else:
        ans = cur
            
print(ans)

Submission status: Accepted

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

H, W, K = map(int, input().split())
S = [input() for i in range(H)]
Col = [[] for i in range(W)]
for j in range(W):
    for i in range(H):
        Col[j].append(S[i][j])
Ans = 10**9
for lst in itertools.product([0,1], repeat=H-1):
    ran = []
    ans = sum(lst)
    l = 0
    for i, x in enumerate(lst, 1):
        if x == 1:
            ran.append((l, i))
            l = i
    ran.append((l, H))
    cnt = [0] * len(ran)
    endflg = 0
    for j in range(W):
        flg = 0
        for i, (l, r) in enumerate(ran):
            c = Col[j][l:r].count('1')
            if c > K:
                ans = 10**9
                endflg = 1
                break
            if cnt[i] + c > K:
                flg = 1
                break
        if endflg:
            break
        if flg:
            ans += 1
            for i, (l, r) in enumerate(ran):
                cnt[i] = Col[j][l:r].count('1')
        else:
            for i, (l, r) in enumerate(ran):
                cnt[i] += Col[j][l:r].count('1')
    Ans = min(Ans, ans)
print(Ans)

Submission status: Accepted

Solution code:
import sys


def main():
    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])

    # print(*cs, sep='\n')
    # print()

    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)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    t = [[0]*(w+1) for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                t[i+1][j+1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1]
#    for i in range(h+1):
#        print(t[i])
    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        F = True
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
                for l in range(1, len(buf)):
                    if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][j-1] + t[buf[l-1]][j-1] > k:
                        F = False
                        break
        if a + b < ans and F:
#            print(a, b, i, x)
            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for i in range(H)]
    ans = (H-1)*(W-1)
    for i in range(2**(H-1)):
        border = []
        tmp = 0
        for j in range(H-1):
            if (i >> j) % 2 == 1:  # jの下に線を引く
                border.append(j)
                tmp += 1

        border.append(H-1)
        num = [0]*(tmp+1)
        flag = True
        prev = 0
        for k, x in enumerate(zip(*S)):
            sep = False
            for j, y in enumerate(border):

                if j == 0:
                    prev = 0
                else:
                    prev = border[j-1]+1

                if sep:
                    num[j] = sum(x[prev:y+1])
                elif num[j] + sum(x[prev:y+1]) > K:

                    #print(k, num[j], sum(x[prev:y+1]))
                    sep = True
                    tmp += 1
                    num[j] = sum(x[prev:y+1])
                    for l in range(j):
                        if l == 0:
                            num[l] = sum(x[:border[l]+1])
                        else:
                            num[l] = sum(x[border[l-1]:border[l]+1])
                else:
                    num[j] += sum(x[prev:y+1])

                if num[j] > K:
                    flag = False
                    break

        #print(border, tmp, flag)
        if flag:
            ans = min(ans, tmp)
        else:
            continue

    print(ans)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    h, w, k = [int(s) for s in input().strip().split()]
    grid = [input().strip() for _ in range(h)]

    result = float("inf")
    for hcut in range(1 << (h - 1)):
        vcut = 0
        cnt = [0] * h
        for j in range(w):
            delta = [0] * h
            for i in range(h):
                delta[i] += grid[i][j] == "1"
                if i > 0 and not (hcut >> (i - 1)) & 1:
                    delta[i] += delta[i - 1]
            if any(x > k for x in delta):
                vcut = float("inf")
                break
            if any(a + b > k for a, b in zip(cnt, delta)):
                cnt = delta
                vcut += 1
            else:
                for idx, x in enumerate(delta):
                    cnt[idx] += x
            # print(cnt)
        result = min(result, vcut + bin(hcut).count("1"))
        # print(bin(hcut), vcut, result)
    print(result)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
h,w,kk=map(int,input().split())
G=[[0]*w for i in range(h)]
for i in range(h):
  G[i]=list(input())
for i in range(h):
  for j in range(w):
    G[i][j]=int(G[i][j])
ans=10**5
for i in range(2**(h-1)):
  s=format(i,'12b')
  A=[-1]
  for j in range(h-1):
    if s[-1-j]=="1":
      A.append(j)
  A.append(h-1)
  ans1=len(A)-2
  B=[0]*(len(A)-1)
  c=0
  i=0
  while i<w:
    j=0
    while j<len(A)-1:
      for k in range(A[j]+1,A[j+1]+1):
        B[j]+=G[k][i]
      if B[j]>kk:
        c=c+1
        B=[0]*(len(A)-1)
        j=0
        if c>1010:
          j=100
          i=10000
      else:
        j=j+1
    i=i+1
  if ans1+c<ans:
    ans=ans1+c
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
l=[[0 for i in range(w+1)]]+[[0]+[int(j) for j in input()] for i in range(h)]
a=[[0 for i in range(w+1)] for i in range(h+1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+l[i][j]
ans=h*w
def ink(h2,h1,w2,w1):
    return a[h2][w2]-a[h1][w2]-(a[h2][w1]-a[h1][w1])
for i in range(2**(h-1)):
    tl=[0]
    for j in range(h-1):
        if i>>j&1:
            tl.append(j+1)
    tl.append(h)
    t=len(tl)-2
    w1=0
    for w2 in range(1,w+1):
        for h1,h2 in zip(tl,tl[1:]):
            if ink(h2,h1,w2,w1)>k:
                if w2-1==w1:
                    t=h*w
                    break
                w1=w2-1
                t+=1
                break
    ans=min(ans,t)
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int, input().split())
fields = []
for i in range(H):
    rows = list(map(int,list(input())))
    fields.append(rows)

Acum = [[0] * (W+1) for i 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] + fields[i][j]
"""
# 実験
h1,h2,w1,w2 = 1,3,1,5 #(1,1)->(2,3)までの累積和
ans = Acum[h2][w2] - Acum[h1][w2] - Acum[h2][w1] + Acum[h1][w1]
print("aaa",ans)
for i in range(H+1):
    print(Acum[i])
"""
# 縦方向は区切り方が2**(H-1)通りを全探索
# 横方向に区切りながらすすめていく(なるべく大きくとっていく)
ans = 10**10
for i in range(2**(H-1)):
    # print("XXXXXXXXXXXXXXXXXXXXXX")
    s = bin(i)[2:]
    s_zero = s.zfill(H-1)
    # print(s_zero)
    # 横区切り線の位置
    a = [0]+[i+1 for i,s in enumerate(s_zero) if int(s) == 1]
    a += [H]
    # 縦区切り線の位置
    w_cnt = 0
    w1 = 0
    w = 1
    m = 0
    while w <= W:
        m = 0
        for j in range(1,len(a)):
            h1 = a[j-1]
            h2 = a[j]
            cnt = Acum[h2][w] - Acum[h1][w] - Acum[h2][w1] + Acum[h1][w1]
            # print(h1,w1,h2,w,cnt)
            m = max(m,cnt)
        if m > K:
            if w - 1 == w１:
                w_cnt = 10**10
                break
            w_cnt += 1
            w1 = w -1         
        w += 1
    # print(s_zero,a,sum(map(int,list(s))),w_cnt)
    ans = min(ans,sum(map(int,list(s)))+w_cnt)
print(ans)

Submission status: Accepted

Solution code:

def create_groups(H):
    F = "{:0" + str(H) + "b}"
    ret = set()
    for n in range(2 ** H):
        g = create_group(F.format(n))
        ret.add(tuple(g))
    return list(sorted(ret))


def create_group(s):
    ret = []
    n = 0
    for i in range(len(s)):
        if i == 0:
            ret.append(0)
        else:
            if s[i-1] == s[i]:
                ret.append(n)
            else:
                n += 1
                ret.append(n)
    return ret

# assert(create_group("0000") == [0,0,0,0])
# assert(create_group("0011") == [0,0,1,1])
# assert(create_group("0010") == [0,0,1,2])

# print(len(create_groups(10)))

def solve(H, W, K, fields):
    ans = H * W + 1
    for g in create_groups(H):
        M = len(set(g))
        s = [0 for _ in range(M)]
        tans = M - 1
        for w in range(W):
            for h in range(H):
                if fields[h][w] == "1":
                    s[g[h]] += 1
            if any([a > K for a in s]):
                s = [0 for _ in range(M)]
                tans += 1
                for h in range(H):
                    if fields[h][w] == "1":
                        s[g[h]] += 1
            if any([a > K for a in s]):
                tans = H * W + 1
                break
        ans = min(ans, tans)
    return ans
#
# assert(solve(3, 3, 1, ["111", "111", "111"]) == 4)
# assert(solve(1, 1, 1, ["1"]) == 0)
# assert(solve(2, 1, 1, ["1", "1"]) == 1)
# assert(solve(1, 2, 1, ["11"]) == 1)
# assert(solve(1, 2, 1, ["11"]) == 1)
# assert(solve(3, 5, 4, ["11100", "10001", "00111"]) == 2)
# assert(solve(3, 5, 8, ["11100", "10001", "00111"]) == 0)
# assert(solve(4, 10, 4, ["1110010010", "1000101110", "0011101001", "1101000111"]) == 3)

# print(slowsolve(5, 11, "33883"))
# print(solve(5, 11, "33883"))

if __name__ == "__main__":
    H, W, K = tuple(map(int, input().split(" ")))
    fields = []
    for _ in range(H):
        fields.append(input())
    print(solve(H, W, K, fields))

Submission status: Accepted

Solution code:
def main():

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

    div = [[]]
    for i in range(1, H+1):
        temp = []
        for lv in div:
            temp.append(lv + [i])
            if i < H:
                temp.append(lv)
        div = temp

    ans = float('inf')
    for lv in div:
        accum = [0 for _ in range(len(lv))]
        count = 0
        chk = []
        is_invalid = False
        for j in range(W):
            k = 0
            to_add = []
            v = 0
            for i in range(H):
                if i == lv[k]:
                    k += 1
                    to_add.append(v)
                    v = 0
                if S[i][j] == '1':
                    v += 1
            to_add.append(v)
            if any(to_add[i] > K for i in range(len(lv))):
                is_invalid = True
                break
            elif any((accum[i] + to_add[i]) > K for i in range(len(lv))):
                count += 1
                accum = to_add
                chk.append(j)
            else:
                for i in range(len(lv)):
                    accum[i] += to_add[i]
        if not is_invalid:
            ans = min(ans, count + len(lv)-1)
    return ans


if __name__ == '__main__':
    print(main())