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 = [[i for i in list(map(int, list(input())))] for i in range(h)]

def solve(l):
    choco = [0 for _ in range(len(l))]
    ans = 0
    for i in range(w):
        f = True
        tmp = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    tmp[idx] += 1
        for j in range(len(l)):
            if choco[j] + tmp[j] > k:
                f = False
        if not f:
            ans += 1
            choco = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    if choco[idx] + 1 > k:
                        return 10 ** 9
                    choco[idx] += 1
    return ans + len(l) - 1


ans = 10 ** 9
for i in range(2 ** (h-1)):
    div = []
    tmp = []
    for j in range(h):
        tmp.append(j)
        if ((i >> j) & 1):
            div.append(tmp)
            tmp = []
    div.append(tmp)
    res = solve(div)
    ans = min(ans, res)
print(ans)

Submission status: Accepted

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

bitcnt = [0]*(1<<h)
for i in range(1<<(h-1)):
    bitcnt[2*i] = bitcnt[i]
    bitcnt[2*i+1] = bitcnt[i]+1

ans = float("inf")
for state in range(1<<(h-1)):
    s = [0]*h
    ans_tmp = 0
    can = True
    for i in range(w):
        cnt = 0
        tmp = [0]*h
        for j in range(h):
            tmp[cnt] += board[j][i]
            if state&(1<<j) or j==h-1:
                cnt += 1
        if any(tmp[j]>k for j in range(cnt)):
            can = False
            break
        if all(s[j]+tmp[j]<=k for j in range(cnt)):
            for j in range(cnt):
                s[j] += tmp[j]
        else:
            s = tmp
            ans_tmp += 1
    if can:
        ans = min(ans, ans_tmp+bitcnt[state])

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

    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 sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for i in range(2 ** (H - 1)):
    p = deque()
    for j in range(H - 1):
        if (i >> j) & 1:
            p.append(j + 1)
    num = len(p)
    if len(p) == 0:
        check = 0
        for j in range(W):
            temp_sum = sum([S[l][j] for l in range(H)])
            if temp_sum > K:
                num = INF
            if check + temp_sum > K:
                check = temp_sum
                num += 1
            else:
                check += temp_sum
    else:
        p.appendleft(0)
        p.append(H)
        check = [0] * (len(p) - 1)
        for j in range(W):
            for l in range(len(p) - 1):
                if p[l + 1] - p[l] == 1:
                    check[l] += S[l][j]
                else:
                    temp_sum = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    if temp_sum > K:
                        num = INF
                        break
                    check[l] += temp_sum
            for l in check:
                if l > K:
                    num += 1
                    for k in range(len(p) - 1):
                        if p[k + 1] - p[k] == 1:
                            check[k] = S[k][j]
                        else:
                            temp_sum = sum([S[t][j] for t in range(p[k], p[k + 1])])
                            if temp_sum > K:
                                num = INF
                            check[k] = temp_sum
                    break
    if num < ans:
        ans = num
print(ans)

Submission status: Accepted

Solution code:
def make_bit(i):
    if i == h - 1:
        solve(t)
        return
    make_bit(i + 1)
    t[i] = 1
    make_bit(i + 1)
    t[i] = 0

def solve(u):
    global ans
    c = sum(u)
    x = [0] * (c + 1)
    y = [0] * h
    for i in range(h - 1):
        y[i + 1] = y[i] + u[i]
    for i in range(w):
        for j in range(h):
            x[y[j]] += int(s[j][i])
        if max(x) > k:
            c += 1
            x = [0] * c
            for j in range(h):
                x[y[j]] += int(s[j][i])
        if max(x) > k:
            c = 1919810
            break
    if ans > c:
        ans = c
    return

h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [0] * (h - 1)
ans = 114514
make_bit(0)
print(ans)

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
data=[[0 for i in range(w+1)]]
for i in range(h):
    x=list(input())
    x.insert(0,0)
    for j in range(w+1):
        x[j]=int(x[j])
    data.append(x)
    
for i in range(h+1):
    for j in range(1,w+1):
        data[i][j]+=data[i][j-1]
        
for i in range(w+1):
    for j in range(1,h+1):
        data[j][i]+=data[j-1][i]
        


ans=10**10
for _ in range(2**(h-1)):
    st=choice=format(_,"0%ib"%(h-1))
    div=[0]
    sub=0
    for j in range(h-1):
        if st[j]=="1":
            div.append(j+1)
            sub+=1
    div.append(h)
    cnt=0
    nowindex=0
    for j in range(1,w+1):
        flag=True
        if nowindex==0:
            for k in range(1,len(div)):
                if data[div[k]][j]-data[div[k-1]][j]>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
                 
        else:
            for k in range(1,len(div)):
                if (data[div[k]][j]-data[div[k]][nowindex])-(data[div[k-1]][j]-data[div[k-1]][nowindex])>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
    subflag=True
    for k in range(1,len(div)):
        if (data[div[k]][w]-data[div[k]][nowindex])-(data[div[k-1]][w]-data[div[k-1]][nowindex])>K:
            subflag=False
    if subflag is True:
        ans=min(ans,sub+cnt)
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int,input().split())
B = [input() for k in range(H)]
S = [[0]*(W+1) for k in range(H)]

for k in range(H):
    for l in range(W):
        if B[k][l] == "1":
            S[k][l+1] = S[k][l] + 1
        else:
            S[k][l+1] = S[k][l]

ans = 1000000
for k in range(2**(H-1)):
    t = [0]*W
    u = []
    for d in range(H):
        if (k>>d)&1 == 1:
            for l in range(W):
                t[l] += int(B[d][l])
        else:
            for l in range(W):
                t[l] += int(B[d][l])
            u.append(t)
            t = [0]*W
    temp = len(u)-1
    d = [0]*len(u)
    for i in range(len(u)):
        d[i] = u[i][0]
        if d[i] > K:
            temp = 1000000
    for j in range(1,W):
        for i in range(len(u)):
            if u[i][j] > K:
                temp = 1000000
                break
            d[i] += u[i][j]
            if d[i] > K:
                temp += 1
                for l in range(len(u)):
                    d[l] = u[l][j]
                break
    ans = min(ans,temp)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

WHITE = '1'
BLACK = '0'

# def count(graph):


def main():
    H, W, K = MI()
    graph = [None] * H

    for i in range(H):
        graph[i] = [int(v) for v in list(S())]

    ans = 10**9
    for i in range(2 ** (H-1)):
        groups = [0]
        for j in range((H-1)):
            if ((i >> j) & 1):
                groups.append(j+1)
        groups.append(H)

        divide_count = 0
        counter = defaultdict(int)
        impossible = False
        for w in range(W):
            current_counter = defaultdict(int)
            for g in range(1, len(groups)):
                prev_div = groups[g-1]
                div = groups[g]
                total = 0
                for h in range(prev_div, div):
                    total += graph[h][w]
                current_counter[g] += total

            # 無理な場合
            if not all(v <= K for v in current_counter.values()):
                impossible = True
                break

            for k, v in current_counter.items():
                counter[k] += v
                if counter[k] > K:
                    divide_count += 1
                    counter = current_counter
                    break
            # print(groups, counter, divide_count)

        if not impossible:
            # print(groups, divide_count + len(groups) - 2)
            ans = min(ans, divide_count + len(groups) - 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def popcnt(n):
  c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
  c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
  c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
  c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
  c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
  return c

answer = 10 ** 18

for i in range(2 ** (H - 1)):
    answer_tmp = popcnt(i)
    dic = [-1] * H
    index = 0
    for j in range(H):
        dic[j] = index
        if i >> j & 1:
            index += 1
    tmp = [0] * (index + 1)
    
    flag = 0
    for k in range(W):
        for j in range(H):
            if S[j][k] == "1":
                tmp[dic[j]] += 1
        if k == 0 and max(tmp) > K:
            flag = 1
            break
        if max(tmp) > K:
            answer_tmp += 1
            for j, t in enumerate(tmp):
                tmp[j] = 0
            for j in range(H):
                if S[j][k] == "1":
                    tmp[dic[j]] += 1
            if max(tmp) > K:
                flag = 1
                break
    if flag:
        continue
    answer = min(answer, answer_tmp)

print(answer)

Submission status: Accepted

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
ans=10**18
for rows in range(2**(h-1)):
  cnt=0
  hlist=[]
  flag=format(rows,'b')[::-1]
  for i in range(len(flag)):
    if flag[i]=='1':
      cnt+=1
      hlist.append(i)
  hlist.append(h-1)
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  y1=0
  for y2 in hlist:
    if count(x1,y1,w-1,y2)>k:
      cnt+=10**18
    y1=y2+1
  ans=min(ans,cnt)
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:
def main():
    
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    num2[d[j]] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        d = []
        for j in range(h):
            d.append(count)
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        lis1.append(count+1)
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

H,W,K=map(int,input().split(' '))
arr = np.vstack([[int(i) for i in input()] for j in range(H)])
ans = H+W-2
for p in product([0,1],repeat=H-1):
    if sum(p)>ans:
        continue
    sp=np.zeros((sum(p)+1,W),int)
    row=0
    sp[0]+=arr[0]
    for j in range(H-1):
        if p[j]:
            row+=1
        sp[row]+=arr[j+1]
    if np.max(sp)>K:
        continue
    sum_arr = np.zeros(len(sp),int)
    cut_cnt = sum(p)
    for c in range(W):
        sum_arr += sp[:,c]
        if max(sum_arr)>K:
            cut_cnt+=1
            sum_arr=sp[:,c]
            if cut_cnt > ans:
                break
    ans = min(cut_cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
ans=10**18
for rows in range(2**(h-1)):
  hlist=[]
  flag=format(rows,'b')[::-1]
  for i in range(len(flag)):
    if flag[i]=='1':
      hlist.append(i)
  hlist.append(h-1)
  cnt=len(hlist)-1
  x1=0
  for x2 in range(w-1):
    y1=0
    for y2 in hlist:
      if count(x1,y1,x2,y2)>k:
        cnt+=10**18
      if count(x1,y1,x2,y2)<=k and count(x1,y1,x2+1,y2)>k:
        cnt+=1
        x1=x2+1
        break
      y1=y2+1
  y1=0
  for y2 in hlist:
    if count(x1,y1,w-1,y2)>k:
      cnt+=10**18
    y1=y2+1
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools, copy

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

ans = float("inf")
for n_horizontal_cut in range(H):
    for horizontal_cut_idx in list(itertools.combinations(list(range(1,H)), n_horizontal_cut)):
        horizontal_cut_idx = [0] + list(horizontal_cut_idx) + [H]
        n_vertical_cut = 0
        n_white_choco = [0] * (n_horizontal_cut+1)
        for w in range(W):
            tmp_idx = 0
            tmp_n_white_choco = copy.copy(n_white_choco)
            for h in range(H):
                if h >= horizontal_cut_idx[tmp_idx+1]:
                    tmp_idx += 1
                if S[h][w] == 1:
                    n_white_choco[tmp_idx] += 1
            if max(n_white_choco) > K:
                n_vertical_cut += 1
                n_white_choco = [n_white_choco[i] - tmp_n_white_choco[i] for i in range(n_horizontal_cut+1)]
                if max(n_white_choco) > K: # 1列の区間でホワイトチョコ数がオーバーする場合
                    break
        else:
            ans = min(ans, n_horizontal_cut + n_vertical_cut)

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, chain

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


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if ans > 0 and n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
chocolate = ['0' + input() for _ in range(h)]

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for y in range(h-1):
        if (pattern >> y) & 1:
            dived.append(y + 1)

    dived.append(h)
    slash_count = len(dived) - 1

    prev_x = 0
    for nx in range(1, w + 1):
        prev_y = 0
        possible = True
        for ny in dived:
            white = white_count[ny][nx] - white_count[prev_y][nx] - (white_count[ny][prev_x] - white_count[prev_y][prev_x])
            prev_y = ny
            if white <= k:
                continue
            else:
                slash_count += 1
                slash = nx - 1
                if prev_x == slash:
                    possible = False
                prev_x = slash
                break

        if not possible:
            break

    else:
        ans.append(slash_count)

print(min(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:
            # print("break")
            break
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        # print("w=",w,tmp)
        if max(tmp) > K:
            cnt += 1
  
            sum_lst = [lst[i][w] for i in range(L)]
            # print(sum_lst)
        else:
            sum_lst = tmp
    else: 
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

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


def solve():
    H, W, K = map(int, rl().split())
    S = [[] for _ in range(H)]
    for i in range(H):
        S[i] = list(map(int, list(input())))
    
    ans = 10 ** 6
    for s in range(1 << (H - 1)):
        pop_cnt = 0
        for i in range(H - 1):
            if s >> i & 1:
                pop_cnt += 1
        
        tmp = pop_cnt
        b = [0] * (tmp + 1)
        flg = True
        for i in range(W):
            j = 0
            for k in range(H):
                if S[k][i]:
                    b[j] += 1
                if s >> k & 1:
                    j += 1
            
            flg = True
            for bi in b:
                if K < bi:
                    flg = False
            
            if not flg:
                tmp += 1
                b = [0] * (pop_cnt + 1)
                j = 0
                for k in range(H):
                    if S[k][i]:
                        b[j] += 1
                    if s >> k & 1:
                        j += 1
                
                flg = True
                for bi in b:
                    if K < bi:
                        flg = False
        
        if flg:
            ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve(L):
    global H, W, K
    N = len(L)
    SL = [[0] * (W + 1) for _ in range(N)]
    for i in range(N):
        for j in range(W):
            SL[i][j + 1] = SL[i][j] + L[i][j]

    offset = [0] * N
    base = 0
    cnt = 0
    j = 0
    while j < W:
        if any([SL[x][j + 1] - offset[x] > K for x in range(N)]):
            if base == j:
                return -1
            else:
                base = j
                offset = [SL[x][j] for x in range(N)]
                cnt += 1
        else:
            j += 1
    return cnt


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

S = [list(map(int, list(input()))) for _ in range(H)]

ans = H + W
for bit in range(pow(2, H - 1)):
    bit <<= 1
    L = [[0] * W for _ in range(H)]
    k = 0
    for i in range(H):
        if (bit >> i) & 1:
            k += 1
        for j in range(W):
            if S[i][j]:
                L[k][j] += 1
    horizontal = solve(L)
    if horizontal >= 0:
        vertical = bin(bit).count('1')
        ans = min(ans, horizontal + vertical)

print(ans)

Submission status: Accepted

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

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]

    cw=0
    memo=0
    chk=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[memo][l]+=s[ch][cw]

            if sumlst[memo][l]>k:
                memo+=1
                chk+=1
                break

            if split[ch]:
                l+=1
        else:
            chk=0
            cw+=1
            continue

        if chk>1:
            break
    else:
        cnt=min(cnt,curcnt+memo)

print(cnt)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

res = 999999999999999999

H, W, K = [int(i) for i in input().split()]
arr = []
for h in range(H):
  arr.append([int(v) for v in input()])

arr = np.vstack(arr)

for p in itertools.product([0, 1], repeat = H-1):
  if sum(p) > res:
    continue
  sp = np.zeros((sum(p)+1, W), int)
  row = 0
  sp[0] += arr[0]
  for j in range(H-1):
    if p[j]:
      row += 1
    sp[row] += arr[j+1]
  if np.max(sp) > K:
    continue
  
  sum_arr = np.zeros(len(sp), int)
  cut_cnt = sum(p)
  for c in range(W):
    sum_arr += sp[:, c]
    if max(sum_arr) > K:
      sum_arr = sp[:, c]
      cut_cnt += 1
      if cut_cnt > res:
        break
  if cut_cnt < res:
    res = cut_cnt
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product

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

i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)

C = [[int(s[i]) for s in S] for i in range(W)]

total = sum(sum(c) for c in C)

if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = 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 c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)

print(answer)

Submission status: Accepted

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

mat=[]
for i in range(H):
  array=[int(x) for x in input()]
  mat.append(array)
#print(mat)

answer=10**9
for i in range(2**(H-1)):
  bitarray=[]
  ii=i
  for j in range(H-1):
    bitarray.append(ii&1)
    ii>>=1
    
  #print(bitarray)
  segment_list=[]
  segment=[0]
  for k in range(len(bitarray)):
    if bitarray[k]==0:
      segment.append(k+1)
    else:
      segment_list.append(segment)
      segment=[k+1]
    
  segment_list.append(segment)
  divide_yoko=len(segment_list)-1
  #print(segment_list,divide_yoko)  
  
  white_list_segment=[0]*len(segment_list)
  sep_list=[]
  for j in range(W):
    white_list_segment_line=[0]*len(segment_list)
    for k in range(len(segment_list)):
      seg=segment_list[k]
      for s in seg:
        white_list_segment_line[k]+=mat[s][j]
        
    isLineOver=False
    if max(white_list_segment_line)>K:
      isLineOver=True
      break
    
    isOver=False
    for k in range(len(segment_list)):
      if white_list_segment[k]+white_list_segment_line[k]>K:
        isOver=True
        break

    if isOver:
      sep_list.append(j-1)
      for k in range(len(segment_list)):
        white_list_segment[k]=white_list_segment_line[k]
    else:
      for k in range(len(segment_list)):
        white_list_segment[k]+=white_list_segment_line[k]
  
  if not isLineOver:
    answer=min(answer,len(segment_list)-1+len(sep_list))
  #print(len(segment_list)-1+len(sep_list),segment_list,sep_list)
  
print(answer)

Submission status: Accepted

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

ans = float("inf")
for state in range(2 ** (H - 1)):
    flag = True

    # 横棒のカウント
    yoko = 0
    for i in range(H - 1):
        if (state >> i) & 1:
            yoko += 1

    res = yoko

    # ホワイトチョコレートの個数
    cntHW = [0] * (yoko + 1)
    for j in range(W):
        # 今のグループ
        now = 0
        # 列を探索
        cntH = [0] * (yoko + 1)
        for i in range(H):
            if S[i][j] == 1:
                cntH[now] += 1

            if (state >> i) & 1: # 区切り
                now += 1
        
        for cH in cntH:
            if cH > K:
                flag = False

        # 個数の最大値
        MAX = max(cH + cHW for cH,cHW in zip(cntH,cntHW))
        if MAX > K:
            res += 1
            cntHW = cntH[::]
        else:
            for i in range(yoko + 1):
                cntHW[i] += cntH[i]

    if flag:
        ans = min(ans, res)

print(ans)