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 = [input() for _ in range(H)]
ans = 10**9
for bit in range((1 << (H-1))):
    vidx = []
    gok = True
    g = 0
    gid = [0] * H
    for i in range(H-1):
        if (bit >> i) & 1:
            g += 1
        gid[i+1] = g
    g += 1
    gnum = [0]*g
    vertical = 0
    for w in range(W):
        ok = True
        one = [0]*g
        for h in range(H):
            one[gid[h]] += int(S[h][w])
            gnum[gid[h]] += int(S[h][w])
            if one[gid[h]] > K:
                gok = False
            if gnum[gid[h]] > K:
                ok = False
        if not ok:
            vertical += 1
            vidx.append(w)
            gnum = one

    # if bit == 2:
    #    print('aaaaa')
    #    print(gid)
    #    print(vidx)
    #    print(bin(bit), g-1, vertical)
    #    print('aaaaa')
    if gok:
        if ans > g-1 + vertical:
            ans = g-1 + vertical
            # print(bin(bit), g-1, vertical)
            # print(vidx)
            # print(ans)
        # ans = min(ans, g-1 + vertical)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    field = [[] for i in range(h)]
    for i in range(h):
        field[i] = [int(s) for s in input()]
    import numpy as np
    field = np.array(field, dtype=int)
    inf = 10 **4
    ans = inf
    for i in range(2**(h-1)):
        prev = 0
        damy = []
        tmp_ans = format(i, 'b').count('1')
        for j in range(h-1):
            if (i >> j)&1:
                damy.append(field[prev:j+1].sum(axis=0))
                prev = j+1
        damy.append(field[prev:].sum(axis=0))
        damy = np.array(damy,dtype=int).T
        if (damy > k).any():
            continue

        prev = 0
        cnt_w = np.zeros(tmp_ans+1, dtype=int)
        for l in range(w):
            cnt_w += damy[l]
            if (cnt_w > k).any():
                cnt_w = damy[l]
                tmp_ans += 1
            
        ans = min(ans, tmp_ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = int(1e15)
    for i in range(1 << (H - 1)):
        cut = 0
        pc = 1
        whites = [[0 for _ in range(W)] for _ in range(H)]
        for j in range(H - 1):
            for w in range(W):
                whites[cut][w] += S[j][w] == '1'
            if i >> j & 1:
                cut += 1
                pc += 1
        for w in range(W):
            whites[cut][w] += S[-1][w] == '1'
        flag = True
        for line in whites:
            for cnt in line:
                if cnt > K:
                    flag = False
        if not flag:
            continue
        cnt = [0 for _ in range(pc)]
        for w in range(W):
            flag = True
            for j in range(pc):
                if cnt[j] + whites[j][w] > K:
                    flag = False
            if not flag:
                cnt = [0 for _ in range(pc)]
                cut += 1
            for j in range(pc):
                cnt[j] += whites[j][w]
        ans = min(ans, cut)
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    H,W,K=map(int,input().split())
    mas=[input().strip("\n") for i in range(H)]
    mincut=H*W
    for bit in range(2**(H-1)):
        sep=[]
        for s in range(H-1):
            if (bit>>s)&1:
                sep.append(s)
        cutcnt=len(sep)
        cnt=[0]*(len(sep)+1)
        for j in range(W):
            ci=0
            cntt=cnt[:]
            for i in range(H):
                if mas[i][j]=="1":
                    cnt[ci]+=1
                if i in sep:
                    ci+=1
            if max(cnt)>K:
                for i in range(len(sep)+1):
                    cnt[i]-=cntt[i]
                cutcnt+=1
        if max(cnt)>K:
            cutcnt=10000000000
        if cutcnt<mincut:
            mincut=cutcnt
    print(mincut)
                
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:

INF = 1<<60
def resolve():
    def judge(j):
        for i in range(group):
            cnt_Wchoco[i] += div_G[i][j]
            if cnt_Wchoco[i] > K:
                return False
        return True

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

    ans = INF
    for bit in range(1<<(H-1)):
        group = 0 # 分かれたブロック数
        row = [0]*H
        for i in range(H):
            # 分割ライン
            row[i] = group
            if bit>>i & 1:
                group += 1
        group += 1 # 1つ折ったら2つに分かれるのでプラス1, 折らなかったら1つ

        # 分割したブロックを列方向で見る
        div_G = [[0] * W for _ in range(group)]
        for i in range(H):
            for j in range(W):
                div_G[row[i]][j] += G[i][j]

        num = group-1
        cnt_Wchoco = [0]*group
        for j in range(W):
            if not judge(j):
                num += 1
                cnt_Wchoco = [0] * group
                if not judge(j):
                    num = INF
                    break
        ans = min(ans, num)

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from itertools import accumulate as acc

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

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    flag = True
    while x < W:
        w_split_num += 1
        r = solve(l, x, K)
        if x == r:
            flag = False
            break
        x = r
    if flag:
        split_num = w_split_num + h_split_num
        min_num = min(split_num, min_num)

print(min_num)

Submission status: Accepted

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

INF = 10000

ans = INF
for bit in range(1 << (h - 1)):

    # 横線でグループ化
    id = [0] * h
    group_idx = 0
    for i in range(h):
        id[i] = group_idx
        if (bit >> i) & 1:
            group_idx += 1

    group_num = group_idx + 1
    cnt = [[0] * w for _ in range(group_num)]
    for i in range(h):
        for j in range(w):
            cnt[id[i]][j] += int(s[i][j])

    # グループ化した際に、1列でkを超えてるならこの縦の区切り方はそもそも無理
    flag = True
    for g in range(group_num):
        for j in range(w):
            if cnt[g][j] > k:
                flag = False
    if not flag:
        continue

    divnum = group_num - 1
    now = [0] * group_num
    cur = 0
    while cur < w:
        for g in range(group_num):
            now[g] += cnt[g][cur]
            if now[g] > k:
                divnum += 1
                now = [0] * group_num
                cur -= 1
                break
        cur += 1
    ans = min(ans, divnum)

print(ans)

Submission status: Accepted

Solution code:
# E - Dividing Chocolate
import sys
sys.setrecursionlimit(10000)

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

def check(border, num):
    global H,W,K,S
    now = [0]*(num+1)
    add = 0
    for j in range(W):
        tmp = [0]*(num+1)
        for i in range(H):
            now[border[i]] += int(S[i][j])
            tmp[border[i]] += int(S[i][j])
        if max(now)>K:
            add += 1
            now = tmp
        if max(tmp)>K:
            return 10000
    return num+add

def rec(border, num, i):
    global H,W,K,S,ans
    if i<H:
        border[i] = num
        rec(border, num, i+1)
        border[i] = num+1
        rec(border, num+1, i+1)
    else:
        ans = min(ans, check(border, num))

rec([0]*H, 0, 1)
print(ans)

Submission status: Accepted

Solution code:
def main():
    #import numpy as np
    import sys, math
    from itertools import permutations, combinations
    from collections import defaultdict, Counter, deque
    from math import factorial#, gcd
    from bisect import bisect_left #bisect_left(list, value)
    sys.setrecursionlimit(10**7)
    enu = enumerate
    MOD = 10**9+7
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

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

    from copy import deepcopy
    cS = [[0]*(W+1) for _ in range(H+1)]
    # cS = deepcopy(S)

    for h in range(1, H+1):
        for w in range(W):
            cS[h][w+1] = cS[h][w] + S[h-1][w]
    for w in range(1, W+1):
        for h in range(H):
            cS[h+1][w] = cS[h][w] + cS[h+1][w]
    # pl(cS)

    mcut = 10**9
    for i in range(2**(H-1)):
        yoko = []
        for j in range(H):
            if ((i >> j) & 1):
                yoko.append(j+1)
        yoko = [0] + yoko + [H]
        # yoko.append(H)
        # print(yoko)
        
        cut = len(yoko)-2
        lastcut = 0 # index-w
        w = 1
        cannot = False
        while w < W+1:
            if cannot:
                w = W + 100
                break
            for ind, y in enu(yoko):
                if ind == 0:
                    continue
                v1 = cS[y][w]
                v2 = cS[yoko[ind-1]][w]
                v3 = cS[yoko[ind-1]][lastcut]
                v4 = cS[y][lastcut]
                val = v1 - v2 + v3 - v4
                # print('  v1, v2', v1, v2)
                if K < val:
                    cut += 1
                    if lastcut == w-1:
                        cannot = True
                    lastcut = w-1
                    break
            else:
                w += 1
            # print(' val', val)
        if not(cannot) and cut < mcut:
            # print('yoko', yoko)
            mcut = cut

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

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    # if h == 1:
    #     tmp = max(0, mat[0].count("1") - 1)
    #     print(tmp // k)
    #     exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = max(0, mat[0].count("1") - 1)
        print(tmp // k)
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  # print(c)
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  ok=True
  for a in range(w):
    for b in range(len(c)):
      if c[b][a]>K:
        ok=False
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  if ok:
    ans=min(ans,t_cnt+t_cnt1)
if ans==10**18:
  print(0)
else:
  print(ans)

Submission status: Accepted

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

ans = 100000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for j in range(W):
        for k in range(H):
            if div[group[k]] + S[k][j] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j]
                    if div[group[l]] > K:
                        cnt = 100000
                break
            else:
                div[group[k]] += S[k][j]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import pprint
input = lambda: sys.stdin.readline().rstrip()

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

Stsum = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        Stsum[i + 1][j + 1] = Stsum[i + 1][j] + S[i][j]
for j in range(W):
    for i in range(H):
        Stsum[i + 1][j + 1] += Stsum[i][j + 1]


def count_white(l, r, u, b):
    return Stsum[b][r] - Stsum[u][r] - Stsum[b][l] + Stsum[u][l]


def solve():

    comb = list(itertools.product(range(2), repeat=H - 1))

    ans = 10 ** 9 + 7
    for c in comb:

        hc = [0] + [i + 1 for i, x in enumerate(c) if x == 1] + [H]
        l, w = 0, 1
        cut_count = 0
        search = False
        p_cut = True

        while w <= W:
            cut = True
            for h in range(0, len(hc) - 1):
                if count_white(l, w, hc[h], hc[h + 1]) > K:
                    cut = False
                    break
            else:
                search = True

            if not cut:
                if search:
                    l = w - 1
                    cut_count += 1
                    search = False
                else:
                    p_cut = False
                    break
            else:
                w += 1

        if p_cut:
            ans = min(ans, cut_count + len(hc) - 2)

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [list(map(int,input().strip())) for i in range(h)]
from copy import deepcopy

ss = deepcopy(s)
for i in range(h):
    for j in range(w-1):
        ss[i][j+1] += ss[i][j]


def gru_hol(HOL): # セットから切り方を作る
    groups_a = []
    group_a = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups_a.append(group_a)
            group_a = [i+1]
        else:
            group_a.append(i+1)
    groups_a.append(group_a)
    return groups_a

def nex_hol(HOL): #次のセットを作る
    for j in range(h-1):
        if(HOL[j] == 0):
            HOL[j] = 1
            for k in range(0,j):
                HOL[k] = 0
            break
    return HOL

def cutsum(grp,lscut,nxcut): #groupのlastcut~nextcutのホワイトチョコを数える
    count = 0
    for i in grp:
        if(lscut != 0):
            count = count + ss[i][nxcut-1] - ss[i][lscut-1]
        else:
            count += ss[i][nxcut-1] 
    return count

def cutcheck(grp_a,lscut_a): #切ってもダメかチェック
    ct_a = 0
    for i in grp_a:
        ct_a += s[i][lscut_a]
    if(ct_a > k):
        return False
    else:
        return True

min_cut = h + w - 2
hol = [0]*(h-1)
for i in range(2**(h-1)):
    fl_ag = 0
    lastcut = 0
    cuts = 0 #切る回数
    groups = gru_hol(hol) #groupsを作る
    for j in range(1,w):
        flag = 0
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == False):
                    fl_ag = 1 #groupからやり直し
                    break
                else:
                    flag = 1
        if(fl_ag == 1):
            break
        if(flag == 1):
            cuts += 1
            lastcut = j

    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
import itertools
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    s = [list(map(int,list(input()))) for _ in [0]*h]
    '''
    sms = [[0]*w for _ in [0]*h]
    for i in range(w):
        for j in range(h):
            sms[j][i] = sms[j-1][i]+s[j][i]
        print(i)
    '''
    cmi = 10**18
    for i in range(2**(h-1)):
        pos = [0]*h
        for j in range(h-1):
            if (i >> j) & 1:
                pos[j+1] = pos[j]+1
            else:
                pos[j+1] = pos[j]
        cmii = pos[-1]
        si = [0]*h
        for jj in range(h):
            si[pos[jj]] += s[jj][0]
        if max(si) > k:
            continue
        f = True
        for j in range(1,w):
            if f:
                for ii in range(h):
                    if si[pos[ii]]+s[ii][j] > k:
                        cmii += 1
                        si = [0]*h
                        for jj in range(h):
                            si[pos[jj]] += s[jj][j]
                        if max(si) > k:
                            f = False
                        break
                    else:
                        si[pos[ii]]+=s[ii][j]
        if f and cmii < cmi:
            cmi = cmii
    print(cmi)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
h, w, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)


for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    #print(val,d)
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True#横がiのときにcnt2の要素がkを超えるとFalse
    flg = True#cntの要素がkを超えるとFalse
    cnt = [0] * len(lis)#全体での1の個数
    for i in range(w):
        cnt2 = [0] * len(lis)#iでの1の個数
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':#高さがkで横がiの時、
                    cnt[j] += 1#lis[j]を1たす
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        #print(cnt,cnt2)
        #print(i,val)
    if flg2 == True:
        ans = min(ans,val)
    #print(val,d,lis,flg)
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
res = 1000000
for i in range(2 ** (h - 1)):
    l = [0]
    cnt = 0
    for j in range(h - 1):
        if (i >> j) & 1:
            l.append(j + 1)
            cnt += 1
    l.append(h)
    li = [0] * (cnt + 1)
    j = 0
    ans = cnt
    f = 0
    while j < w:
        sm = 0
        idx = 0
        for i in range(h):
            if l[idx + 1] <= i:
                if sm > k:
                    f = 1
                    break
                sm = 0
                if li[idx] > k:
                    ans += 1
                    break
                idx += 1
            if s[i][j] == '1':
                sm += 1
                li[idx] += 1
        else:
            if li[idx] > k:
                if sm > k:
                    f = 1
                    break
                ans += 1
                li = [0] * (cnt + 1)
                continue
            j += 1
            continue
        if f:
            break
        li = [0] * (cnt + 1)
    if not f:
        res = min(res, ans)
print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        cnt = [0] * len(group)
        w = 0
        while w < W:
            now = [0] * len(group)
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = [0] * len(group)
                    break
                cnt[g] += now[g]
            if cut >= min_cut:
                break
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    h,w,k=map(int,readline().split())
    grid=[readline().strip() for _ in range(h)]

    ans=float("inf")
    for i in range(1<<(h-1)):
        div=[(i>>j)&1 for j in range(h-1)]
        l=len([0 for i in range(h-1) if div[i]])+1
        cnt=[0]*l
        tmp=0
        for j in range(w):
            now=0
            flag=False
            for i_2 in range(h):
                if grid[i_2][j]=="1":
                    cnt[now]+=1
                    if cnt[now]>k:
                        flag=True
                        break
                if i_2<h-1 and div[i_2]==1: now+=1
            if flag:
                tmp+=1
                cnt=[0]*l
                now=0
                flag=False
                for i_2 in range(h):
                    if grid[i_2][j]=="1":
                        cnt[now]+=1
                        if cnt[now]>k:
                            flag=True
                            break
                    if i_2<h-1 and div[i_2]==1: now+=1
                if flag: break
        else:
            tmp+=l-1
            ans=min(ans,tmp)

    print(ans)

if __name__=="__main__":
    main()