Problem:


Score : 500 points

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


class cumsum2d:  # 二次元累積和クラス pypyでも使えるよ
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        # 縦に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        # 横に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


class cumsum1d:  # 一次元累積和クラス
    def __init__(self, ls: list):
        '''
        1次元リストを受け取る
        '''
        from itertools import accumulate
        self.ls_accum = [0] + list(accumulate(ls))

    def total(self, i, j):
        # もとの配列lsにおける[i,j)の中合計
        return self.ls_accum[j] - self.ls_accum[i]


def iter_p_adic(p, length):
    '''
    連続して増加するp進数をリストとして返す。lengthはリストの長さ
    return
    ----------
    所望のp進数リストを次々返してくれるiterator
    '''
    from itertools import product
    tmp = [range(p)] * length
    return product(*tmp)


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right


# やっぱり二次元累積和でホワイトチョコレートの個数を管理して良さそう。
# Kが10以上なら簡単で縦に着れば良い
# 縦は全探索
# 横は累積和で管理

H, W, K = read_ints()
S = read_map(H)
S_cums = []
for s in S:
    S_cums.append(cumsum1d(map(int, list(s))))
# いや累積和を10こ作って於けばいいんじゃね


def ret_renketusum(p, i, j):
    # pの分割で[i,j)まで最大いくつの1があるか
    ma = S_cums[0].total(i, j)
    tmp = S_cums[0].total(i, j)
    for k, pp in enumerate(p, start=1):
        if pp == 1:  # cutする
            ma = max(ma, tmp)
            tmp = S_cums[k].total(i, j)
        else:
            tmp += S_cums[k].total(i, j)
    ma = max(ma, tmp)
    return ma


ans = 1000000000
for p in iter_p_adic(2, H - 1):
    # どこを分割するのか全探索
    l = 0
    r = 1
    n_cut = 0
    while r <= W:
        # print(l, r, ret_renketusum(p, l, r))
        if ret_renketusum(p, l, r) > K:
            if r - l == 1:
                n_cut = 1000000000000
                break
            n_cut += 1
            l = r - 1
            r = l
        r += 1
    ans = min(n_cut + sum(p), ans)

print(ans)

Submission status: Accepted

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

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

ans = H * W

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

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

    num_groups += 1

    num_lines = num_groups - 1 

    g_sum = [0] * num_groups

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

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

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

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

Submission status: Accepted

Solution code:
from itertools import product
INFTY = 10**4
H,W,K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
cmin = INFTY
for x in product((0,1),repeat=H-1):
    cur = 0
    cnt = 0
    h = sum(x)+1
    A = [0 for _ in range(h)]
    for j in range(W):
        ind = 0
        A0 = [0 for _ in range(h)]
        for i in range(H):
            if i<H-1 and x[i]==1:
                A0[ind] += S[i][j]
                ind += 1
            else:
                A0[ind] += S[i][j]
        B = [A[i]+A0[i] for i in range(h)]
        if max(A0)>K:
            cnt = INFTY
            break
        if max(B)>K:
            cur = j
            cnt += 1
            A = A0[:]
        else:
            A = B[:]
    cmin = min(cmin,cnt+sum(x))
print(cmin)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools
sys.setrecursionlimit(10**7)
#input = sys.stdin.readline
def LI(): return [int(x) for x in sys.stdin.readline().split()]
INF = 10000
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
H,W,K = LI()
C = [[int(x) for x in input()] for _ in range(H)]

min_cnt = INF
for y in range(2**H):
    cnt = 0
    bit = 1
    shikiri = [False] * H
    for b in range(H):
        if y & bit:
            shikiri[b] = True     #仕切り
            cnt +=1
        bit = bit << 1
    ct = [0] * H
    x = 0
    bx = 0
    while x < W:
        ix = 0
        for i in range(H):
            ct[ix] += C[i][x]
            if shikiri[i] : ix = i+1
        if max(ct) > K:
            if x != bx:
                cnt += 1
                ct = [0] * H
                bx = x
            else:
                cnt = INF
                break
        else:
            x = x + 1

    min_cnt = min(min_cnt,cnt)
print (min_cnt)

Submission status: Accepted

Solution code:
ans=10**8
h,w,K=map(int,input().split())
s=[]
import copy
def two(x):
	return "0"*(h-1-len(bin(x)[2:]))+bin(x)[2:]
for i in range(h):
	s.append(input())
for i in range(2**(h-1)):
	r=two(i)
	pre_ans=r.count("1")
	d=[0]*(pre_ans+1)
	dd=copy.copy(d)
	cnt=0
	for j in range(w):
		now=0
		for k in range(h):
			if s[k][j]=="1":
				d[now]+=1
			if k!=h-1:
				if r[k]=="1":
					now+=1
		if max(d)>K:
			e=[]
			for x in range(len(d)):
				e.append(d[x]-dd[x])
			d=copy.copy(e)
			cnt+=1
		if max(d)>K:
			cnt=10**7
		dd=copy.copy(d)
	pre_ans+=cnt
	ans=min(ans,pre_ans)
print(ans)

Submission status: Accepted

Solution code:
def chk(area):
    num=0
    l=len(area)
    cnt=[0 for _ in range(l)]

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            if i>0: num+=1
            cnt=[0 for _ in range(l)]
            for j in range(h):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

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

area=[0 for i in range(h)]
ans=10**10

for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1
        else: area[i+1]=area[i]

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Submission status: Accepted

Solution code:

H,W,K = map(int,input().split())
S = [list(map(int,input())) for _ in range(H)]
ans = float("inf")
for i in range(2**(H-1)):
    kari = 0
    l = [0]*H
    if H > 1:
        for j in range(0,H-1):
            if i >> j & 1:
                l[j+1] = l[j]+1
                kari += 1
            else:
                l[j+1] = l[j]
    num = [0]*H

    for w in range(W):
        tmp = [0]*H
        for h in range(H):
            if S[h][w]:
                tmp[l[h]] += 1

        if max(tmp) > K:
            break

        if max([num[i]+tmp[i] for i in range(H)]) <= K:
            num = [num[i]+tmp[i] for i in range(H)]
            
            #num += tmp
        else:
            num = tmp
            kari += 1
    else:

        ans = min(ans,kari)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=readline = sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s


#@lru_cache(maxsize=None)  
def f():
    return 1
#main
H,W,K=list(map(int,input().split()))
S=[list(map(int,list(input()))) for _ in range(H)]
R=[[0 for a in range(W)] for b in range(H+1)]
for a in range(W):
    cnt=0
    for b in range(H):
        if(S[b][a]==1):cnt+=1
        R[b+1][a]=cnt

ans=inf
for a in range(0,1<<(H-1)):
    x_siki=0
    B=bin_(a,H-1)
    ku=B.count(1)+1
    hi=[0]*ku
    f=True
    for b in range(W):
        now=[0]*ku

        sen=[0]
        for c in range(len(B)):
            if(B[c]==1):sen.append(c+1)
        sen.append(H)
        for c in range(len(sen)-1):
            now[c]=R[sen[c+1]][b]-R[sen[c]][b]
        if(max(now)>K):
            f=False
            continue
        for c in range(len(now)):
            hi[c]+=now[c]
        if max(hi)>K:
            x_siki+=1
            hi=now[:]
    if(f):ans=min(x_siki+ku-1,ans)
print(ans)

Submission status: Accepted

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

    ans = float('inf')
    for pattern in product([0, 1], repeat=H - 1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        d = set()
        df = False
        counts = [0] * len(rows)
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]

            if [c for c in counts if c > K]:
                if w in d:
                    df = True
                    break
                d.add(w)
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

            if df:
                break
        
        if not df:
            tmp_ans += len(div) - 2
            ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

white = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i != 0:
            white[i][j] += white[i-1][j]
        if j != 0:
            white[i][j] += white[i][j-1]
        if i != 0 and j != 0:
            white[i][j] -= white[i-1][j-1]
        white[i][j] += choco[i][j]
ans = float('inf')
for i in range(2**(h-1)): #横に切る位置をbitでもつ
    temp = format(i,'b').count('1') # 横に何かいきるか
    hw = []#h == どこの下で切るか
    j = i
    cnt = 0
    while j >0:
        if j&1:
            hw.append(cnt)
        cnt += 1
        j = j >> 1
    hw.append(h-1)
    now = -1
    #if w == 1:
    flag = True
    for l in range(len(hw)):
        if l == 0:
            if white[hw[l]][0] > k:
                flag = False
                break
        else:
            if white[hw[l]][0] - white[hw[l-1]][0] > k:
                flag = False
                break
    if not flag:
        continue
    elif w == 1:
        ans = min(ans,temp)
        continue

    for j in range(w-1):
        flag = True
        if now == -1:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l-1]][j+1] > k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
        else:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] - white[hw[l]][now] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l]][now] - white[hw[l-1]][j+1] + white[hw[l-1]][now]> k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
    ans = min(ans,temp)
print(ans)

Submission status: Accepted

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

for i in range(1<<(H-1)):
    cnt=0
    
    lst=[0]*H
    qqq=0
    for j in range(H-1):
        if i&(1<<j)==0:
            lst[j+1]=qqq
            continue
        else:
            qqq+=1
            lst[j+1]=qqq
            cnt+=1
    data=[0]*H
    for j in range(W):
        for k in range(H):
            data[lst[k]]+=S[k][j]
            if data[lst[k]]>K:
                cnt+=1
                break
        else:
            continue
        data=[0]*H
        for k in range(H):
            data[lst[k]]+=S[k][j]
            if data[lst[k]]>K:
                break
        else:
            continue
        break
    else:
        ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from itertools import accumulate, product
def main():
    H, W, K = map( int, input().split())
    S = [ list( map( int, list( input()))) for _ in range(H)]
    ans = 10**5
    cnt = 0
    AS = [ [0] + list( accumulate(S[i])) for i in range(H)]
    #print(AS)
    #TAS = list( zip(*AS))
    SAS = []
    for a in AS:
        SAS.extend(a)
    for P in product( range(2), repeat=H-1):
    # for i in range(2**(H-1)):
    #     P =[]
    #     for _ in range(H-1):
    #         P.append(i%2)
    #         i //= 2
        now = sum(P)
        if ans < now:
            continue
        start = 0
        goal = 0
        #print(P, now)
        while start < W:
            for i in range(start, W):
                cnt = 0
                check =True
                for j in range(H):
                    #cnt += AS[j][i+1] - AS[j][start]
                    #cnt += TAS[i+1][j] - TAS[start][j]
                    #                    print(P, start, i, j,cnt)
                    cnt += SAS[j*(W+1)+i+1] - SAS[j*(W+1)+start]
                    if j == H-1:
                        if cnt > K:
                            check = False
                            break
                    else:
                        if P[j] == 1:
                            if cnt > K:
                                check = False
                                
                                break
                            cnt = 0
                if check:
                    goal += 1
            if start == goal:
                start = W+1
                now = 10**5
                break
            #print("sg",P,start, goal, W)
            start = goal
            if goal < W:
                #print("now")
                now += 1
            #print(now)
        
        if now < ans:
            ans = now
    print(ans)
                
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = None
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    n_w = 0
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    is_new = True
    is_fail = False
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            n_w += 1
            if ans is not None and ans <= n_h + n_w:
                break
            cnts = zz.copy()
            for y in range(h):
                z = to_add[y]
                cnts[z] += ar[y][x]
                if cnts[z] > k:
                    is_fail = True
                    break
            if is_fail:
                break
    if not is_fail and (ans is None or ans > n_h + n_w):
        ans = n_h + n_w
print(ans)

Submission status: Accepted

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

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

# sum_h = [[0] * w for _ in range(h+1)]
# for i in range(1,h+1):
#     for j in range(w):
#         sum_h[i][j] = sum_h[i-1][j] + sum_w[i-1][j+1]

sums = []
for i in range(h):
    sums.append([[0] * w for _ in range(h+1)])

for i in range(h):
    for j in range(i+1,h+1):
        for l in range(w):
            sums[i][j][l] = sums[i][j-1][l] + sum_w[j-1][l+1]

ans = h + w
for i in range(2**(h-1)):
    nums = []
    for j in range(h-1):
        if((i >> j)&1 == 1):
            nums.append(j+1)
    tmp = len(nums)
    nums.append(h)
    # print(nums)
    head = 0
    checks = []
    for j in nums:
        checks.append(sums[head][j])
        head = j
    # print(i)
    # print(checks)

    minus_num = [0] * len(checks)
    w_now = 0
    NG_flag = 0
    cut_flag = 0
    for j in range(w):
        if(NG_flag == 1):
            break
        for l in range(len(checks)):
            check_num = checks[l][j] - minus_num[l]
            if(check_num > k):
                if(w_now == 0):
                    # print('hoge')
                    NG_flag = 1
                    break
                cut_flag = 1
                break


        if(cut_flag==1):
            # print('j={}'.format(j))
            tmp += 1
            for l in range(len(checks)):
                minus_num[l] = checks[l][j-1]
                check_num = checks[l][j] - minus_num[l]
                if(check_num > k):
                    NG_flag=1
                    break
            cut_flag = 0
            w_now = 1
        else:
            w_now += 1

    # print('')
    # print(tmp)
    if(NG_flag==0):
        ans = min(ans, tmp)
        # print('ans = {}'.format(ans))


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def check(sets):
  n = len(sets)
  data = [0]*n
  count = 0
  result_bit = 0
  for j in range(w):
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      # ここ不安
    F = 0
    for i in range(n):
      if tmp[i] > K:return -1
      if data[i] + tmp[i] > K:
        F = 1
      else:
        data[i] += tmp[i]
    if F:
      result_bit |= (1<<j-1)
      for i in range(n):
        data[i] = tmp[i]
  return result_bit
    # if tmp > K:
    #   return -1
    # if count + tmp > K:
    #   result_bit |= (1 << j-1)
    #   count = tmp
    # else:
    #   count += tmp
  return  result_bit

h,w,K = map(int,input().split())
S = [list(map(int,input())) for i in range(h)]
for bit in range(2**(h-1)):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  # print(re)
  if re == -1: continue
  mans = min(mans,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"])
  # print(bit,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"],bit,re)
print(mans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = []
for _ in range(h):
    s += [[int(i) for i in list(S())]]
ans = INF
for j in range(2 ** (h - 1)):
    L = []
    last = 0
    for m in range(h - 1):
        if j >> m & 1:
            L += [(last, m + 1)]
            last = m + 1
    L += [(last, h)]
    now = [0] * len(L)
    last_x = 0
    cnt = len(L) - 1
    flag2 = 0
    flag = 0
    x = 0
    while x < w:
        flag3 = 0
        K = [s[y][x] for y in range(h)]
        for i in range(len(L)):
            l, r = L[i]
            k_sum = sum(K[l:r])
            if now[i] + k_sum > k:
                cnt += 1
                if flag == 0:
                    flag2 = 1
                    break
                else:
                    flag = 0
                    now = [0] * len(L)
                    flag3 = 1
                    break
            else:
                now[i] += k_sum
        else:
            flag = 1
        if flag3:
            continue
        if flag2:
            break
        x += 1
    else:
        ans = min(ans, cnt)


print(ans)

Submission status: Accepted

Solution code:
def inputs(): return [int(x) for x in input().split()]
from collections import defaultdict
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
h,w,k= inputs()
s = [list(input()) for _ in range(h)]
res = 10**8
for bit in range(0,1<<h):
    l = popcnt(bit)
    cnt = [0]*(l+1)
    cnt2 = []
    ans = 0
    for i in range(w):
        cnt1=0
        cnt2=[]
        for j in range(h):
            if bit&1<<j and j!=0:
                cnt1+=1
            if s[j][i]=="1":
                cnt[cnt1]+=1
                cnt2.append(cnt1)
                #print(cnt,cnt1,cnt2,j,i)
                if k<cnt[cnt1]:
                    cnt = [0]*(l+1)
                    ans+=1
                    for m in cnt2:
                        cnt[m]+=1
                        if k<cnt[m]:
                            ans+=10**9
    #print(res,ans,l,bit)
    res = min(res,ans+l)
print(res)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
X = []
import sys;input=sys.stdin.readline
for _ in range(H):
    X.append(input().strip())

ks = [[0]*(W+1) for _ in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        ks[i][j] = ks[i][j-1] + ks[i-1][j] - ks[i-1][j-1] + int(X[i-1][j-1])
#print(ks[1])
#print(ks[2])
#print(ks[3])

R = 10**18
for ii in range(2**(H-1)):
    i = ii
    c = 0
    cs = []
    while i:
        if i%2:
            cs.append(c)
        i //= 2
        c += 1
    b = 0
    r = 0
    cs.append(H-1)
#    print(ii, cs)
    tmp = []
    fff = False
    for j in range(1, W+1):
        cb = 0
        for c in cs:
#            print(c+1, cb, j, b, ks[c+1][j] - ks[c][b] - ks[cb][j] + ks[cb][b])
            if ks[c+1][j] - ks[c+1][b] - ks[cb][j] + ks[cb][b] > K:
                if j - b == 1:
                    fff = True
                tmp.append(j)
                r += 1
                b = j-1
                break
            cb = c+1
    if fff:
        continue
#    print(ii, cs, tmp)
#    print(r+len(cs)-1)
    R = min(R, r+len(cs)-1)
print(R)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        flag=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k and flag==0:
                flag=1
                ans_+=1
                ll=[0]*h
            elif max(ll)>k and flag==1:
                ans_=10**5
                break
            else:
                j+=1
                flag=0
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

min_num = float("inf")
for i in range(1<<(h-1)):
    c = 0
    d = {0:0}
    bar = 0
    for ii in range(1,h):
        if i&(1<<(ii-1)):
            c += 1
            bar += 1
        d[ii] = c

    # print(bin(i), bar, d)
    ss = [0]*(c+1)
    invalid = False
    for wi in range(w):
        flag = False
        ss_tmp = [0]*(c+1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss_tmp[d[hi]] > k:
                    invalid = True
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        # print(wi, flag, bar)
        # print(ss, ss_tmp)

    if not invalid:
        min_num = min(min_num, bar)

    # from right
    bar = bin(i).count("1")
    ss = [0] * (c + 1)
    invalid = False
    for wi in range(w-1, -1, -1):
        flag = False
        ss_tmp = [0] * (c + 1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                ss[d[hi]] += 1
                if ss_tmp[d[hi]] > k:
                    invalid = True
                if ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        # print(wi, flag, bar)
        # print(ss, ss_tmp)

    if not invalid:
        min_num = min(min_num, bar)

print(min_num)