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 = [list(map(int, input())) for _ in range(H)]
ans = 10**18
for i in range(2**(H-1)):
    flag2 = False
    tate = 0
    tmp = [0 for _ in range(H)]
    for k in range(W):

        flag1 = False
        for j in range(H):
            if S[j][k] == 1:
                tmp[j] += 1
        tmp2 = tmp[:]
        for j in range(H - 1):
            if not ((i >> j) & 1):
                tmp2[j + 1] += tmp2[j]
        for j in range(H):
            if tmp2[j] > K:
                tate += 1
                flag1 = True
                break
        if flag1:
            tmp = [0 for _ in range(H)]
            for j in range(H):
                if S[j][k] == 1:
                    tmp[j] += 1
            tmp2 = tmp[:]
            for j in range(H - 1):
                if not ((i >> j) & 1):
                    tmp2[j + 1] += tmp2[j]
            for j in range(H):
                if tmp2[j] > K:
                    flag2 = True
                    break
        if flag2:
            break
    if flag2:
        continue

    yoko = 0
    for j in range(H - 1):
        if (i >> j) & 1:
            yoko += 1
    ans = min(ans, tate+yoko)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
def popcnt(n):
  c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
  c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
  c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
  c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
  c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
  return c

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

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inpl(): return list(map(int, sys.stdin.readline().split()))


def inpl_str(): return list(sys.stdin.readline().split())


H, W, K = inpl()
SS = [list(map(int, str(input()))) for _ in range(H)]

ans = INF

for bit in range(1 << H-1):
    tmpSS = []
    nSS = []
    for b in range(H):
        nSS.append(SS[b])
        # print(bin(bit), nSS)
        if bit & (1 << b) != 0:
            tmpSS.append(nSS)
            nSS = []

    tmpSS.append(nSS)
    tmp_ans = len(tmpSS) - 1
    nSS = []

    for tmpS in tmpSS:
        L = len(tmpS)
        nS = [0]*W
        for x in range(W):
            for y in range(L):
                nS[x] += tmpS[y][x]
        nSS.append(nS)

    # print(nSS)

    L = len(nSS)
    tmpl = [0]*L
    for x in range(W):
        for y in range(L):
            tmpl[y] += nSS[y][x]

        if max(tmpl) > K:
            for y in range(L):
                tmpl[y] = nSS[y][x]
            tmp_ans += 1
            if max(tmpl) > K:
                tmp_ans = INF

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

H, W, K = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << (H-1)):
    cnt = 0
    prev = -1
    for h in range(H-1):
        cnt += (bit >> h) & 1
    for w in range(W):
        s = 0
        cut = False
        for h in range(H):
            if h > 0 and bit >> (h-1) & 1:
                if s > K:
                    cut = True
                    break
                s = 0
            s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
        if s > K:
            cut = True
        if cut:
            if w-1 == prev:
                break
            cnt += 1
            prev = w-1
            continue
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w,k = inpm()
    s = [[] for _ in range(h)]
    for i in range(h):
        a = list(input())
        for j in range(w):
            s[i].append(int(a[j]))
    dp = [[0 for _ in range(w+1)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j+1] = dp[i][j] + s[i][j]
    ans = (h-1)+(w-1)
    for e in range(pow(2,h-1)):
        cut = []
        for _ in range(h-1):
            cut.append(e%2)
            e //= 2
        NUM = sum(cut)+1
        DP = [[0 for _ in range(w)] for _ in range(NUM)]
        index = [0 for _ in range(h)]
        for i in range(h-1):
            index[i+1] = index[i] + cut[i]
        for i in range(h):
            for j in range(w):
                DP[index[i]][j] += s[i][j]
        ANS = sum(cut)
        cnt = [0 for _ in range(NUM)]
        for j in range(w):
            for i in range(NUM):
                if cnt[i]+DP[i][j] <= k:
                    cnt[i] += DP[i][j]
                else:
                    ANS += 1
                    for d in range(NUM):
                        cnt[d] = DP[d][j]
                    break
            if j == w-1:
                if max(cnt)>k:
                    ANS = (h-1)+(w-1)
        ans = min(ans,ANS)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def nasu(x):
  L = [0]
  t = x
  cnt = 1
  while t != 0:
    if t & 1:
      L.append(cnt)
    t >>= 1
    cnt += 1
  Ans = len(L) - 1

  L.append(H)
  pr = 0
  for i in range(1, W + 1):
    f = True
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        pr = i - 1
        Ans += 1
        #print(pr, end = ",")
        break     
    else:
      continue
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        return 10 ** 10
  #print(L, Ans)
  return Ans

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

N = 2 **(H - 1)

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

for i in range(1, H + 1):
  for j in range(2, W + 1):
    D[i][j] = D[i][j - 1] + S[i - 1][j - 1]

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

Ans = 10 ** 10
for i in range(N):
  Ans = min(Ans, nasu(i))

print(Ans)

Submission status: Accepted

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

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

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(input())[: -1] for _ in range(H)]
cs = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
  for j in range(W): cs[i][j + 1] = cs[i][j] + int(S[i][j] == "1")
res = H * W
#print(cs)
for t in range(H):
  for c in combi([x for x in range(H - 1)], t):
    l = 0
    tres = 0
    while l < W:
      ok = l
      ng = W + 1
      while ng - ok > 1:
        m = (ok + ng) // 2
        tt = 0
        i = 0
        ttt = 0
        while i < H:
          ttt += cs[i][m] - cs[i][l]
          if i in c:
            tt = max(tt, ttt)
            ttt = 0
          i += 1
        tt = max(tt, ttt)
        if tt <= K: ok = m
        else: ng = m
      if l == ok:
        tres = H * W
        break
      l = ok
      tres += int(l < W)

    #print(c, tres)
    res = min(res, tres + len(c))
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W,K=map(int,input().split())
    S=[[] for _ in range(H)]
    for i in range(H):
        S[i]=list(map(int,list(input())))
    ans=INF
    for i in range(2**(H-1)):
        f=True
        tmp=0
        wari=0
        d={}
        d[0]=0
        for j in range(H-1):
            if (i>>j)&1:
                tmp+=1
            d[j+1]=tmp
        wari+=tmp
        l=[0]*H
        for yoko in range(W):
            f=False
            for tate in range(H):
                if S[tate][yoko]:
                    l[d[tate]]+=1
                    if l[d[tate]]>K:
                        wari+=1
                        l=[0]*H
                        f=True
                        break
            if f:
                f2=False
                for tate in range(H):
                    if S[tate][yoko]:
                        l[d[tate]]+=1
                        if l[d[tate]]>K:
                            f2=True
                            break
                if f2:
                    wari=INF
                    break
        ans=min(ans,wari)
    print(ans)
                    
            
            

if __name__ == '__main__':
    main()

Submission status: Accepted

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

count_table = []
for line in s:
	counts = [0]
	count = 0
	for c in line:
		if c == 1:
			count += 1
		counts.append(count)
	count_table.append(counts)

def check_limit(groups, last_div, x):
	for g in groups:
		whites = 0
		for y in g:
			counts = count_table[y]
			whites += counts[x + 1] - counts[last_div]
			if whites > K:
				return False
	return True

def check(groups):
	count = 0
	last_div = 0
	divides = 0
	for x in range(W):
		if not check_limit(groups, last_div, x):
			if last_div == x:
				return None
			else:
				divides += 1
				last_div = x
	return divides

min_total = W + H

for i in range(2 ** (H - 1)):
	div = []
	n = i
	divides_h = 0
	for j in range(H - 1):
		if n % 2 == 0:
			div.append(True)
			divides_h += 1
		else:
			div.append(False)
		n = n // 2
	cur_group = [0]
	groups = [cur_group]
	for j in range(H - 1):
		if div[j]:
			cur_group = [j + 1]
			groups.append(cur_group)
		else:
			cur_group.append(j + 1)
	divides_v = check(groups)
	if divides_v != None and divides_h + divides_v < min_total:
		min_total = divides_h + divides_v

print(min_total)

Submission status: Accepted

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

n = h

final = 10000000

for ii in range(2**(n-1)):
    ans = 0
    op = [0]*(n-1)
    cnt = 1
    for j in range((n-1)):
        if (ii >> j) & 1:
            op[j] = 1
            cnt += 1
            ans += 1
    
    opp = [0]
    for i in range(n-1):
        opp.append(opp[-1]+op[i])
    h_block = [0]*cnt
    for j in range(w):
        err = False
        tmp = [0]*cnt
        for i in range(h):
            if s[i][j] == '1':
                tmp[opp[i]] += 1
        if max(tmp) > k:
            err = True
            break
        if any(tmp[i] + h_block[i] > k for i in range(cnt)):
                ans +=1
                h_block = tmp[:]
        else:
            for i in range(cnt):
                h_block[i] += tmp[i]
    if err:
        continue
    final = min(final,ans)

print(final)

Submission status: Accepted

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

ans = H*W
S2 = [[0]*(W+1) for _ in [0]*(H+1)]
for i in range(H):
    for j in range(W):
        S2[i+1][j+1] = S2[i][j+1] + S[i][j]
for i in range(1,H+1):
    for j in range(W):
        S2[i][j+1] += S2[i][j]

for i in range(1<<(H-1)):
    check = [0]+[j+1 for j in range(H-1) if i>>j&1]+[H]
    cnt = len(check)-2
    l = 0
    r = 1
    while r<=W:
        for j,k in zip(check[:-1],check[1:]):
            if S2[j][l] + S2[k][r] - S2[j][r] - S2[k][l] > K:
                if r==l+1:
                    cnt += H*W
                    r = W+1
                    break
                cnt += 1
                l = r-1
                r = r
                break
        else:
            r += 1
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

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

ans = 10 ** 18
for i in range(1 << (h-1)):
    possible = True
    x = i
    cut = [0] * (h-1)
    for j in range(h-1):
        cut[j] = x & 1
        x >>= 1
    index = [0] * h
    for j in range(h-1):
        index[j+1] = index[j] + cut[j]
    n = index[h-1] + 1

    s = [0 for _ in range(n)]
    ver = 0
    for j in range(w):
        need = False
        for z in range(h):
            s[index[z]] += int(f[z][j])
            if s[index[z]] > k:
                need = True
        if need:
            ver += 1
            s = [0 for _ in range(n)]
            for z in range(h):
                s[index[z]] += int(f[z][j])
                if s[index[z]] > k:
                    possible = False
    if possible:
        ans = min(ans, sum(cut) + ver)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
ans=float("inf")
import bisect
for i in range(2**(h-1)):
  Cut=[]
  cur=0
  for ii in range(h-1):
    if i&(1<<ii):
      Cut.append(ii)
  p=len(Cut)+1
  Num=[0]*h
  for ii in range(h):
    Num[ii]=bisect.bisect_left(Cut,ii)

  A=[0]*p
  Chk=True
  for j in range(w):
    B=[0]*p    
    for jj in range(h):
      if S[jj][j]=="1":
        B[Num[jj]]+=1
    for jj in range(p):
      if B[jj]>k:
        Chk=False
      if A[jj]+B[jj]>k:
        cur+=1
        A=B
        break
      else:
        continue
    else:
      for jjj in range(p):
        A[jjj]+=B[jjj]
  if Chk:
    ans=min(ans,cur+p-1)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from itertools import product

H,W,K = LI()
S = [list(map(str, input())) for _ in range(H)]

A = product([0,1],repeat=H-1)
ans = float('inf')
for a in A:
    count = 0
    for a0 in a:
        if a0 == 1:
            count += 1
    List = []
    now = []
    for i in range(H):
        now.append(i)
        if i != H-1:
            if a[i] == 1:
                List.append(now)
                now = []
    List.append(now)
    n = len(List)
    nums = [0]*n
    now_nums = [0]*n
    for j in range(W):
        flag = False
        # L = [0,1]
        for k,L in enumerate(List):
            for l in L:
                if S[l][j] == '1':
                    now_nums[k] += 1
        #print(a,j,now_nums)         
        for k in range(n):
            if now_nums[k] > K:
                flag = True
                break
        
        c_flag = False
        for k in range(n):
            if nums[k]+now_nums[k] > K:
                count += 1
                c_flag = True
                break
        
        if c_flag:
            nums = now_nums[:]
            now_nums = [0]*n
        else:
            for k in range(n):
                nums[k] += now_nums[k]
            now_nums = [0]*n

        if flag:
            break
    if flag:
        continue

    if count < ans:
        ans = count

print(ans)

Submission status: Accepted

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

h,w,KK = map(int,input().split())

if h == 1:
    s = input()
    res = 0
    cnt = 0
    for i in range(w):
        if s[i] == "1":
            cnt += 1
            if cnt == KK and i != w-1:
                res += 1
                cnt = 0
    print(res)
    exit()

s = []
for i in range(h):
    s.append(input())

res = 10**9

d = dict()
for i in range(1<<(h-1)):
    tmp = 0
    for j in range(h-1):
        d[j] = tmp
        if (i>>j)&1 == 1:
            tmp += 1
    d[h-1] = tmp
    cnt = [0]*h


    for j in range(w):
        r = [0]*h
        judge = False
        for k in range(h):
            if s[k][j] == "1":
                r[d[k]] += 1
                if r[d[k]] > KK:
                    tmp = 10**9
                    break
                if r[d[k]] + cnt[d[k]] > KK:
                    judge = True
        if tmp == 10**9:
            break
        if judge:
            tmp += 1
            for k in range(h):
                cnt[k] = r[k]
        else:
            for k in range(h):
                cnt[k] += r[k]



    if res > tmp:
        res = tmp
print(res)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

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

ans = (H-1) * (W-1)
for bit in range(1<<(H-1)):
	hs = []
	cur = [0]
	res = 0
	for i in range(1, H):
		if bit & (1 << (i-1)) == 0:
			cur.append(i)
		else:
			res += 1
			hs.append(cur)
			cur = [i]
	hs.append(cur)
	#print(hs)
	ng = False
	whites = [0 for _ in range(len(hs))]
	for c, d in enumerate(hs):
		for h in d:
			if s[h][0] == "1":
				whites[c] += 1
		if whites[c] > k:
			ng = True
	

	for w in range(1, W):
		tmp = [0 for _ in range(len(hs))]
		for c, d in enumerate(hs):
			for h in d:
				if s[h][w] == "1":
					tmp[c] += 1
			if tmp[c] > k:
				ng = True

		over = False
		for c in range(len(hs)):
			if whites[c] + tmp[c] > k:
				over = True

		if over:
			res += 1
			whites = tmp
		else:
			whites = [wh + t for wh, t in zip(whites, tmp)]
		#print(whites)

	if not ng:
		ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
a = [list(input()) for i in range(h)]
acc = [[0 for i in range(w+1)] for j in range(h+1)]
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] = acc[i-1][j]
    if a[i-1][j-1] == "1":
      acc[i][j] += 1
for i in range(1,h+1):
  for j in range(1,w+1):
    acc[i][j] += acc[i][j-1]
ans = 1000000
def cut(x,y,up,left):
  return acc[x][y]-acc[x][left]-acc[up][y]+acc[up][left]
for i in range(2**(h-1)):
  sep = [0]
  for r in range(h-1):
    if i&1<<r:
      sep.append(r+1)
  sep.append(h)
  anstmp = len(sep)-2
  left = 0
  for j in range(1,w):
#    print(i,j,left,list(cut(sep[x],j+1,sep[x-1],left) for x in range(1,len(sep))))
    if max(list(cut(sep[x],j,sep[x-1],left) for x in range(len(sep)))) > k:
      break
    if max(list(cut(sep[x],j+1,sep[x-1],left) for x in range(len(sep)))) > k:
      anstmp += 1
      left = j
  else:
    ans = min(ans,anstmp)
print(ans)

Submission status: Accepted

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

mi = 1 << 20
for i in range(1 << H - 1):
    X = []
    l = 0
    ii = i
    pc = 0
    while ii:
        a = ii & -ii
        ii -= a
        r = a.bit_length()
        X.append((l, r))
        l = r
        pc += 1
    X.append((l, H))
    Y = [0] * (pc + 1)
    l = 0
    cnt = 0
    r = l + 1
    ngflg = 0
    while r <= W + 1:
        for a, b in X:
            if S[b][r] - S[b][l] - S[a][r] + S[a][l] > K:
                if r == l + 1:
                    ngflg = 1
                    break
                l = r - 1
                cnt += 1
                break
        else:
            r += 1
        if ngflg: break
    if ngflg: continue
    mi = min(mi, pc + cnt)

print(mi)

Submission status: Accepted

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

H,W,K=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=1<<30
for i in range(1<<(H-1)):
    A=[]
    for j in range(H):
        if i & (1<<j) !=0:
            A.append(j+1)
    #print(A)

    SCORE=len(A)
    B=[0]*(len(A)+1)

    for w in range(W):
        ind=0
        for i in range(H):           
            if ind<len(A) and i==A[ind]:
                ind+=1
            if MAP[i][w]=="1":
                B[ind]+=1

        #print(A,w,B,SCORE)
        if max(B)>K:
            SCORE+=1
            B=[0]*(len(A)+1)
            ind=0

            for i in range(H):           
                if ind<len(A) and i==A[ind]:
                    ind+=1
                if MAP[i][w]=="1":
                    B[ind]+=1

        #print(A,w,B,SCORE)
        if max(B)>K:
            break
    else:
        ANS=min(ANS,SCORE)

print(ANS)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, W, K = list(map(int, sys.stdin.buffer.readline().split()))
S = [list(map(int, list(sys.stdin.buffer.readline().decode().rstrip()))) for _ in range(H)]


# print(S)

# TODO: H == 1

# @debug
def solve(counts):
    ts = [0] * len(counts)
    ret = 0
    for w in range(W):
        s = [0] * len(counts)
        div = False
        for i, cnts in enumerate(counts):
            s[i] += cnts[w]
            if s[i] > K:
                return INF
            if s[i] + ts[i] > K:
                div = True
        if div:
            ret += 1
            ts = s
        else:
            for i, c in enumerate(s):
                ts[i] += c
    return ret


if H == 1:
    ans = solve(S)
else:
    # 横の分割方法を全探索
    ans = INF
    for divs in itertools.product([True, False], repeat=H - 1):
        counts = []
        li = [0] * W
        for h, div in enumerate(divs):
            for w, c in enumerate(S[h]):
                li[w] += c
            if div:
                counts.append(li)
                li = [0] * W
        for w, c in enumerate(S[-1]):
            li[w] += c
        counts.append(li)
        ans = min(ans, solve(counts) + sum(divs))
print(ans)

Submission status: Accepted

Solution code:
from itertools import product,accumulate

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

grid = tuple(tuple(map(int,input())) for _ in range(H))

def check(gids):
    cnt = 0
    s = [0]*(gids[-1]+1)
    for i in range(W):
        for h,gid in enumerate(gids):
            s[gid] += grid[h][i]
        if any(v > K for v in s):
            cnt += 1
            s = [0]*(gids[-1]+1)
            for h,gid in enumerate(gids):
                s[gid] += grid[h][i]
            if any(v > K for v in s):
                return float('inf')
    return cnt

def it():
    for p in product(range(2),repeat=H-1):
        gids = [0]+list(accumulate(p))
        yield check(gids)+gids[-1]

print(min(it()))

Submission status: Accepted

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

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    index = 0
    flag = 1
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            try:
                for k in range(len(white_after)):
                    white_after[k] -= white_before[k]
                    if white_after[k] > K:
                        flag = 0
                white_before = white_after[:]
                ans_temp += 1
            except:
                flag = 0
                break
        index = 0
    if flag == 0:
        continue
    ans = min(ans, ans_temp)

print(ans)

Submission status: Accepted

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

ret = 10 ** 18
for bit_state in range(1 << (h - 1)):
    memo = {}
    pos = 0
    res = 0
    for i in range(h - 1):
        memo[i] = pos
        if bit_state & (1 << i):
            pos += 1
    memo[h - 1] = pos
    len_m = (pos + 1)
    ans = [0] * len_m
    
    flag = False
    for j in range(w):
        tmp = [0] * len_m
        for i in range(h):
            if s[i][j] == "1":
                tmp[memo[i]] += 1
        for i in range(len_m):
            if tmp[i] > k:
                flag = True
        for i in range(len_m):
            if tmp[i] + ans[i] > k:
                res += 1
                for i in range(len_m):
                    ans[i] = tmp[i]
                break
        else:
            for i in range(len_m):
                ans[i] += tmp[i]
    if not flag:
        ret = min(ret, res + len_m - 1)
print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**16

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

ans = INF
for bit in range(1<<(H-1)):
    zones = []
    tmp = [0]
    for h in range(H-1):
        if bit&(1<<h):
            zones.append(tmp)
            tmp = [h+1]
        else:
            tmp.append(h+1)
    zones.append(tmp)
    L = len(zones)
    Scores = [0]*L
    tmp_point = L-1
    for w in range(W):
        out = False
        C = []
        for l, z in enumerate(zones):
            p = 0
            for i in z:
                if state[i][w]:
                    p += 1
            C.append(p)
            if p + Scores[l] > K:
                out = True
            Scores[l] += p
        if max(C) > K:
            tmp_point = INF
            break
        if out:
            tmp_point += 1
            Scores = C[:]
    if tmp_point < ans:
        ans = tmp_point

print(ans)

Submission status: Accepted

Solution code:

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

A = []
for i in range(H):

    a = list(map(int,list(input())))
    A.append(a)

#print (A)
ans = float("inf")

for i in range(2**(H-1)):

    wtk = [0]
    cut = 0

    for j in range(H-1):

        if i & 2**j > 0:
            wtk.append(wtk[-1]+1)
            cut += 1
        else:
            wtk.append(wtk[-1])

    now = [0] * (H)

    for y in range(W):

        flag = True
        nnow = []
        for ll in now:
            nnow.append(ll)
        save = [0] * (H)

        for x in range(H):

            nnow[wtk[x]] += A[x][y]
            save[wtk[x]] += A[x][y]

        if max(save) > K:
            cut = float("inf")
            break
        if max(nnow) > K:
            cut += 1
            nnow = save

        now = nnow

    ans = min(ans,cut)
            
print (ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())
    grid = []
    for _ in range(H):
        line = input().rstrip('\n')
        grid.append([int(s) for s in line])

    ans = 10**9
    for i in range(2**(H-1)):
        tmp = 0
        h_list = [[0]]
        for j in range(H-1):
            if i >> j & 1:
                tmp += 1
                h_list.append([j+1])
            else:
                h_list[-1].append(j+1)
        L = len(h_list)
        white = [0] * L
        ok = 1
        for w in range(W):
            white_new = [0] * L
            for l in range(L):
                for h in h_list[l]:
                    if grid[h][w] == 1:
                        white_new[l] += 1
            if max(white_new) > K:
                ok = 0
            flg = 0
            for l in range(L):
                if white[l] + white_new[l] > K:
                    flg = 1
            if flg:
                tmp += 1
                white = white_new
            else:
                for l in range(L):
                    white[l] += white_new[l]
        if ok:
            ans = min(ans, tmp)
    print(ans)


if __name__ == '__main__':
    main()