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 h in range(H)]

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if chocos[j][w] > K:
                _ans = float('inf')
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

Submission status: Accepted

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

def main():
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        S.append(list(int(x) for x in list(input().strip())))
    #print(S)
    ans=float('inf')
    for bit in range(1<<(h-1)):
        cut=0
        tmp=bit
        while tmp:
            cut+=tmp&1
            tmp>>=1
        C=[]
        Tmp=S[0][:]
        for i in range(h-1):
            if (bit>>i)&1==1:
                C.append(Tmp)
                Tmp=S[i+1][:]
            else:
                for j in range(w):
                    Tmp[j]+=S[i+1][j]
        C.append(Tmp)
        #print(bit,C)
        m=0
        for c in C:
            m=max(m,max(c))
        if m>k:
            continue
        W=[0]*(cut+1)
        l=len(W)
        for i in range(l):
            W[i]+=C[i][0]
        for i in range(w-1):
            for j in range(l):
                W[j]+=C[j][i+1]
            #print(W)
            if max(W)>k:
                cut+=1
                for j in range(l):
                    W[j]=C[j][i+1]
        #print(bit,C,cut)
        ans=min(ans,cut)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

for i in range(H):
    for j in range(W):
        c[i][j] += c[i-1][j]

def count(x1,y1,x2,y2):
    res = c[x2][y2]
    res -= c[x2][y1-1]
    res -= c[x1-1][y2]
    res += c[x1-1][y1-1]
    return res

ans = 10**9
for n in range(2**(H-1)):
    h = [0]
    cuts = 0
    for k in range(H-1):
        if 2**k&n:
            h.append(k+1)
            cuts += 1
    h.append(H)
    w1 = 0
    for w2 in range(W):
        ok = True
        for i in range(len(h)-1):
            h1 = h[i]
            h2 = h[i+1]-1
            if count(h1,w1,h2,w2)>K:
                ok = False
                break
        if not ok:
            cuts += 1
            if w1==w2:
                cuts = 10**9
            w1 = w2
    
    ans = min(ans,cuts)

print(ans)

Submission status: Accepted

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

ans = H+W
for b in range(1<<(H-1)):
    tmp = bin(b).count('1')
    ks = [0]*H
    valid = True
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
            if any(k > K for k in ks):
                valid = False
                break
    if valid:
        ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w,K = LI()
s = [input() for _ in range(h)]

ans = inf
for i in range(2**(h-1)):
    bit = [0]*(h-1)
    cnt = 0
    for j in range(h-1):
        if (i >> j) & 1:
            bit[j] = 1
            cnt += 1
    lst = [[0]*w for _ in range(cnt+1)]
    preans = cnt
    C = cnt
    tmp = 0
    cnt = 0
    for j in range(h-1):
        if bit[j]:
            for l in range(w):
                for k in range(tmp, j+1):
                    if s[k][l] == '1':
                        lst[cnt][l] += 1
            tmp = j+1
            cnt += 1

    for j in range(w):
        for k in range(tmp,h):
            if s[k][j] == '1':
                lst[-1][j] += 1
    T = [0]*(C+1)
    flg = True
    for k in range(w-1):
        for j in range(C+1):
            T[j] += lst[j][k]
            if lst[j][k] > K:
                flg = False
            if T[j] + lst[j][k+1] > K:
                preans += 1
                T = [0]*(C+1)
                break
    for j in range(C+1):
        if lst[j][-1] > K:
            flg = False
    if flg:
        ans = min(ans, preans)
print(ans)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
S = []
for i in range(H):
	s = list(map(int, list(input())))
	S.append(s)
A = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(H):
	for j in range(W):
		A[i+1][j+1] = A[i+1][j] + A[i][j+1] - A[i][j] + S[i][j]

def f(x1,y1,x2,y2):
	return A[x2][y2] - A[x1-1][y2] - A[x2][y1-1] + A[x1-1][y1-1]

if f(1,1,H,W) <= K:
	print(0)
	exit()

m = 100000

def int2bit(n):
	ret = [0 for i in range(H-1)]
	c = 0
	while n > 0:
		ret[c] = n % 2
		n = n // 2
		c += 1
	return ret

def getx1x2(b):
	ret = []
	x1 = 1
	for i in range(H-1):
		if b[i] == 1:
			ret.append((x1, i+1))
			x1 = i+2
	ret.append((x1, H))
	return ret

def check(x1x2):
	for y in range(1, W+1):
		for x1, x2 in x1x2:
			if(f(x1,y,x2,y) > K):
				return False
	return True

for i in range(2**(H-1)):
	x1x2 = getx1x2(int2bit(i))
	if not check(x1x2):
		continue
	cnt = len(x1x2) - 1
	y1 = 1
	for y2 in range(2, W+1):
		flag = False
		for x1, x2 in x1x2:
			if f(x1,y1,x2,y2) > K:
				flag = True
				break
		if flag:
			y1 = y2
			cnt += 1
	m = min(m, cnt)
print(m)

Submission status: Accepted

Solution code:
import copy

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

s1 = [[0]*(w+1) for _ in range(h)]
s12 = [[0]*(w+1) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '1':
            s1[i][j+1] = s1[i][j] + 1
        else:
            s1[i][j+1] = s1[i][j]

for i in range(h):
    for j in range(w+1):
        if i == 0:
            s12[i][j] = s1[i][j]
        else:
            s12[i][j] = s12[i-1][j] + s1[i][j]

li = []
ans = 10**10

def make_list():
    global li, h
    if len(li) != h - 1:
        li.append(0)
        make_list()
        li.pop(-1)
        li.append(1)
        make_list()
        li.pop(-1)
    else:
        hantei()

def hantei():
    global li, ans
    tmp = li.count(1)
    tmp_1 = -1
    s2 = []
    s3 = []
    for i in range(h-1):
        if li[i] == 1:
            if tmp_1 == -1:
                s2.append(s12[i])
                tmp_1 = i
            else:
                for j in range(w+1):
                    s3.append(s12[i][j] - s12[tmp_1][j])
                s2.append(s3)
                tmp_1 = i
                s3 = []
    if tmp_1 == -1:
        s2.append(s12[-1])
    else:
        for j in range(w+1):
            s3.append(s12[-1][j] - s12[tmp_1][j])
        s2.append(s3)

    tmp_2 = 0
    for i in range(w+1):
        for j in range(len(s2)):
            if s2[j][i] - s2[j][tmp_2] > k:
                tmp += 1
                tmp_2 = i - 1
                if s2[j][i] - s2[j][tmp_2] > k:
                    tmp += 10**5
                break

    ans = min(ans, tmp)

make_list()

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class v:
    def __init__(self, f):
        self.f = f
        self.v = None
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 

def f(i, H):
    B = format(i, "0" + str(H - 1) + "b")
    R = []
    left = 0
    right = 1
    for b in B:
        if b == "1":
            R.append((left, right))
            left = right
        right += 1
    R.append((left, right))
    
    return R


def g(S, H, W, K, block):
    wl = 0
    wr = 1
    res = 0
    while wr != W + 1:
        T = max(S[hr][wr] - S[hl][wr] - S[hr][wl] + S[hl][wl] for hl, hr in block)
        # print(wl, wr, T)
        if T > K:
            if wr - wl == 1:
                return 10 ** 10

            res += 1
            wl = wr - 1
            continue
        wr += 1
    
    return res + len(block) - 1


def main():
    H, W, K = read_values()
    C = [input() for _ in range(H)]

    S = [[0 for _ in range(W + 1)] for __ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            r = int(C[h][w])
            S[h + 1][w + 1] = S[h][w + 1] + S[h + 1][w] - S[h][w] + r

    r = v(min)
    for i in range(1 << (H - 1)):
        block = f(i, H)
        t = g(S, H, W, K, block)
        r.ud(t)
    
    print(r)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
s = []
for i in range(h):
    s.append(ins())
mn = 20000
for t in range(2**(h-1)):
    lbl = [0]*h
    top = 0
    for i in range(1,h):
        if (t>>(i-1))%2==1:
            top += 1
        lbl[i] = top
    #ddprint(f"t {t} mn {mn}")
    #ddprint(lbl)
    sm = [0]*(top+1)
    ans = top
    pos = True
    for j in range(w):
        ok = True
        tmp = [x for x in sm]
        for i in range(h):
            if s[i][j]=='1':
                tmp[lbl[i]] += 1
        if max(tmp)>k:
            ans += 1
            sm = [0]*(top+1)
        for i in range(h):
            if s[i][j]=='1':
                sm[lbl[i]] += 1
        if max(sm)>k:
            pos = False
            break
    if pos and ans<mn:
        mn = ans
print(mn)

Submission status: Accepted

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline


def input(): return inp().strip()


flush = sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)


def iin(): return int(input())


def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input


def main():
    def cnt_ones(n):
        ch = 0
        x = n
        ans = []
        while x:
            if x&1:
                ans.append(ch)
            x>>=1
            ch+=1
        return ans
    ans = []
    h, w, K = lin()
    a = [list(map(int, list(input()))) for _ in range(h)]
    h1 = 2**(h-1)
    for i in range(h1):
        ch = cnt_ones(i)+[h-1]
        l1 = len(ch)
        a1 = [0]*(l1)
        ch2 = 0
        for j in range(w):
            ch1 = 0
            a2 = [0]*(l1)
            for k in range(h):
                a2[ch1]+=a[k][j]
                if ch[ch1]==k:
                    ch1+=1
            for k in range(l1):
                if a1[k]+a2[k]>K:
                    ch2 += 1
                    a1 = a2[:]
                    break
            else:
                for k in range(l1):
                    a1[k]+=a2[k]
            #check
            for i in a1:
                if i>K:
                    ch2 = w*10
                    break
            else:
                continue
            break
        ans.append(l1-1+ch2)
    # print(ans)
    print(min(ans))

"""
TEST-
4 4 1
1111
1111
1111
1111
"""


main()
# threading.Thread(target=main).start()

Submission status: Accepted

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

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    # print(cut_h)
    # print(blocks)
    # print(counts)

    maxcounts = 0
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            maxcounts = max(maxcounts, counts[j][k])
    if maxcounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            # print(cumsums)
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    # print(tmpans)
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

h,w,k = get_nums_l()
grid = [ input() for _ in range(h)]

ruiseki_white = [ [0] * (w+1) for _ in range(h) ]
for y in range(h):
    for x in range(w):
        ruiseki_white[y][x+1] = ruiseki_white[y][x] + (1 if grid[y][x] == "1" else 0)

# log(ruiseki_white)

def num_whites(l,r,t,b):
    ret = 0
    for y in range(t, b):
        ret += ruiseki_white[y][r] - ruiseki_white[y][l]
    # log(l,r,t,b,ret)
    return ret

ans = 999999999999999999

for bits in range(2**(h-1)):
    h_breaks=[0]
    for i in range(h-1):
        if bits &  2**i != 0:
            h_breaks.append(i+1)
    h_breaks.append(h)

    # log("h_breaks: ", h_breaks)

    w_break_count = 0
    prev_w_break = 0
    ok = True
    for x in range(1,w+1):
        for i in range(len(h_breaks) - 1):
            top = h_breaks[i]
            bottom = h_breaks[i+1]
            left = prev_w_break
            right = x
            if num_whites(left, right, top, bottom) > k:
                # ここの左で切る
                # log("CUT", left, right, top, bottom)
                if prev_w_break + 1 == x:
                    # この縦の切り方はだめ
                    ok = False
                prev_w_break = x-1
                w_break_count += 1
                break
        if not ok:
            break
    if ok:
        # log("ok. wbreak_count: ", w_break_count)
        ans = min(ans, len(h_breaks)-2 + w_break_count)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, S):
    ans = 0
    S = [list(map(int, [c for c in r])) for r in S]
    # for r in S:
    #     print(r)
    # wn = sum([sum(r) for r in S])
    # # print(wn)


    ans = INF
    for p in product([0, 1], repeat=H-1):
        spl = [i+1 for i, v in enumerate(p) if v == 1]
        cand = len(spl)
        spl.append(H)
        rs = []
        p = 0
        for si in spl:
            r = [0] * W
            for j in range(W):
                for k in range(p, si):
                    r[j] += S[k][j]
            rs.append(r)
            p = si
        # print(spl,'------')
        # for r in rs:
        #     print(r)

        sr = [0] * len(rs)
        impossible = False
        for i in range(W):
            if any([sr[j] + rs[j][i] > K for j in range(len(rs))]):
                cand += 1
                for j in range(len(rs)):
                    sr[j] = rs[j][i]
                    if sr[j] > K:
                        impossible = True
            else:
                for j in range(len(rs)):
                    sr[j] += rs[j][i]
        if not impossible:
            ans = min(ans, cand)



    return ans


def main():
    H, W, K = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, K, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque

H, W, K = [int(x) for x in input().split()]
grid = [[int(x) for x in input()] for r in range(H)]


counts1 = Counter()
for cuts in range(2 ** H):
    numCuts = len([r for r in range(H) if (1 << r) & cuts])
    # print("trying", [r for r in range(H) if (1 << r) & cuts], "init", numCuts)

    counts1[cuts] = numCuts
    counts2 = Counter()
    for c in range(W):
        counts3 = {}
        curr = 0
        for r in range(H):
            curr += grid[r][c]
            # Cut ending at (inclusive) r or is last row
            if (1 << r) & cuts or r == H - 1:
                counts3[r] = curr
                curr = 0

        if all(counts2[r] + counts3[r] <= K for r, counts in counts3.items()):

            # print(c, "can add", counts2, counts3)
            for r, counts in counts3.items():
                counts2[r] += counts3[r]
        else:
            # print(c, "must cut", counts2, counts3)

            counts1[cuts] += 1
            if c == W - 1:
                if any(counts3[r] > K for r, counts in counts3.items()):
                    # print('impossible')
                    counts1[cuts] = float("inf")
            counts2 = counts3
    # print("total", counts1[cuts])
    # print()

print(min(counts1.values()))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    h, w, k = LI()
    s = SR(h)
    bit_length = [0] 
    for i in range((h-1)): 
        bit_length += [x + 1 for x in bit_length]
    ans = inf
    for i in range(1 << (h - 1)):
        tmp = [0] * (bit_length[i] + 1)
        num = 0
        for x in range(w):
            t = 0
            f = 0
            tmp1 = [0] * (bit_length[i]+1)
            for y in range(h):
                # print(t)
                tmp[t] += int(s[y][x])
                tmp1[t] += int(s[y][x])
                if tmp[t] > k:
                    f = 1
                if tmp1[t] > k:
                    break
                t += 1 & (i >> y) 

            else:
                if f:
                    num += 1
                    # print(tmp)
                    tmp = tmp1[::1]
                continue
            break
        else:
            # print(tmp,tmp1,bin(i),num)
            ans = min(ans, bit_length[i] + num)
    print(ans)


        
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

ans = float('inf')
for i in range(1 << (H-1)):
    parts = []
    tans = 0
    for k in range(H-1):
        if i & (1 << k):
            tans += 1
            parts.append(k+1)
    parts.append(H)
    cts = [0] * len(parts)
    for j in range(W):
        prev = 0
        flag1 = False
        for idx, p in enumerate(parts):
            c = accs[j][p] - accs[j][prev]
            cts[idx] += c
            if cts[idx] > K:
                flag1 = True
                break
            prev = p
        if flag1:
            tans += 1
            prev = 0
            flag2 = False
            for idx, p in enumerate(parts):
                c = accs[j][p] - accs[j][prev]
                if c > K:
                    # muri
                    flag2 = True
                    break
                cts[idx] = c
                prev = p
            if flag2:
                break
    else:
        ans = ans if ans < tans else tans
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

h,w,kk = list(map(int, input().split()))

info = []
for i in range(h):
    s = input()
    ss = []
    for j in range(w):
        ss.append(int(s[j]))
    info.append(ss)

n = 2**(h-1)
#print(info)

anss=[]

for i in range(n):
    #print()
    bit = ValueToBits(i,h-1)
    bitsum = sum(bit)
    blocks = bitsum + 1
    
    
    sums = [0 for i in range(blocks)]
    sums2 = [0 for i in range(blocks)]
    ids = []
    
    nowid = 0
    ids.append(nowid)
    for j in range(h-1):
        if(bit[j]==1):
            nowid+=1
        ids.append(nowid)
    
    #print(bit,blocks,ids)
    dead = 0
    lines = 0
    for k in range(w-1):
        flag=0
        for j in range(h):
            sums[ids[j]]+=info[j][k]
        
        for j in range(blocks):
            sums2[j] = sums[j]
            #print('sumsj',sums[j])
            if(sums[j]>kk):
                #print(sums[j],k)
                dead = 1
        full=0
        for j in range(h):
            sums2[ids[j]]+=info[j][k+1]
            
            
        for j in range(blocks):
            if(sums2[j] > kk):
                lines +=1
                full=1
                #print('full',sums2[j],'block',j,'w',k)
                break
        
        #print("sums",sums)
        if(full==1):
            for j in range(blocks):
                sums[j] = 0
                
        if(dead==1):
            #print('dead')
            break
    if(dead==1):
        anss.append(999999)
    else:
        anss.append(lines + bitsum)
        #print(lines+bitsum)

print(min(anss))

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
H,W,K=map(int,input().split())
S=[input() for i in range(H)]
from itertools import product
l=tuple(product([0,1], repeat=(H-1)))
a=2000
for i in l:
    t=sum(i)
    p=t
    w=[0]*(t+1)
    c=0
    x=[0]*W
    while c<W:
        it=0
        for k in range(H):
            if S[k][c]=="1":
                w[it]+=1
            if k!=H-1 and i[k]:
                it+=1
        for j in w:
            if j>K:
                w=[0]*(t+1)
                p+=1
                x[c]+=1
                break
        else:
            c+=1
            continue
        if x[c]==2:
            break
    else:
        if p<a:
            a=p
print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
C = [list(input().rstrip()) for i in range(h)]

for i in range(h):
    for j in range(w):
        C[i][j] = int(C[i][j])
# print(C)

A = [[0] * w for i in range(h)]
A = C
# for i in range(h):
#     A[i][0] = C[i][0]

# for i in range(h):
#     for j in range(1, w):
#         A[i][j] = A[i][j-1] + C[i][j]

# B = [[0] * w for i in range(2**h)]

# for i in range(2**h):
#     ib = format(i, "b").zfill(h)
#     for kk in range(w):
#         for j in range(h):
#             if ib[j] == "1":
#                 B[i][kk] += A[j][kk]


ans = 10**15

for i in range(2**(h-1)):
    owa=0
    ib = format(i, "b").zfill(h-1)
    H = [0] * h
    t = 0
    for j in range(h-1):
        if ib[j] == "1":
            t += 1
        H[j+1] = t
    # print(H)
    ans0 = ib.count("1")
    ans00 = ans0
    D = [0] * h
    for j in range(w):
        DD = [0] * h
        for kk in range(h):
            DD[H[kk]] += A[kk][j]
        f = 0
        # print(D)
        for kk in range(h):
            if DD[kk] > k:
                owa = 1
                break
            elif DD[kk]+D[kk] > k:
                f = 1
                
        if owa==1:
            break
        if f == 1:
            ans0 += 1
            D = DD[:]
        else:
            for kk in range(h):
                D[kk] += DD[kk]

    if owa==0:
        ans = min(ans, ans0)
        # print(ib, ans, ans00,ans0)
print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [input() for _ in range(h)]
data_yoko = [[0]*(w+1) for _ in range(h)]
for i in range(w):
    for j in range(h):
        if s[j][i] == "1":
            data_yoko[j][i+1] = 1
        data_yoko[j][i+1] += data_yoko[j][i]
data_tate = [[0]*w for _ in range(h+1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "1":
            data_tate[i+1][j] = 1
        data_tate[i+1][j] += data_tate[i][j]

ans = h*w
for case in range(2**(h-1)):
    now = 0
    use = []
    for bit in range(h-1):
        if case>>bit & 1:
            use.append(bit+1)
            now += 1
    use.append(h)
    left = [0]*len(use)
    pre = -1
    check1 = True
    check2 = True
    for i in range(w):
        for j in range(len(use)):
            to = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
            if k < to:
                check1 = False
                break
            if to + left[j] > k:
                check2 = False
                break
            left[j] += to
        if not check1:
            break
        if check2:
            continue
        for j in range(len(use)):
            left[j] = data_tate[use[j]][i] if j == 0 else data_tate[use[j]][i]-data_tate[use[j-1]][i]
        now += 1
        check2 = True
    if check1:
        ans = min(ans,now)

print(ans)

Submission status: Accepted

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

ans = float('inf')

for i in range(2**(h-1)):
    a = format(i,'b').zfill(h-1)
    choco = [[int(x) for x in s[0]]]
    for k in range(1,h):
        if a[k-1]=='1':
            choco.append([0 for x in range(w)])
        for j in range(w):
            if s[k][j]=='1':
                choco[-1][j]+=1
    b = 0
    c = [0 for x in range(len(choco))]
    ok = 1
    for j in range(w):
        for k in range(len(choco)):
            if choco[k][j]>K:
                ok = 0
                break
            c[k]+=choco[k][j]
        if max(c)>K:
            b+=1
            c = [choco[x][j] for x in range(len(choco))]
    if ok:
        ans = min(b+a.count('1'),ans)
print(ans)