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())
choco = []
mcut = h+w
for i in range(h):
    choco.append(list(map(int,list(input()))))
for i in range(2**(h-1)):
    chocos = []
    cut = 0
    choco1 = choco[0][:]
    for j in range(h-1):
        if i >> j & 1:
            chocos.append(choco1)
            choco1 = choco[j+1][:]
            cut += 1
        else:
            for l in range(w):
                choco1[l] += choco[j+1][l]
    chocos.append(choco1)
    num = len(chocos)
    chocosum = [0 for _ in range(num)]
    flag = True
    for j in range(w):
        for l in range(num):
            if chocos[l][j] > k:
                flag = False
            chocosum[l] += chocos[l][j]
            if chocosum[l] > k:
                cut += 1
                chocosum = [chocos[_][j] for _ in range(num)]
                break
    if flag:
        mcut = min(cut,mcut)
print(mcut)

Submission status: Accepted

Solution code:
import sys 
MOD = 10**9 +7
INF = 10**5

def main():
    h,w,k = map(int,input().split())
    grid = [[0] * (w + 1)] + [[0] + [int(i) for i in list(input())] for _ in range(h)]
    

    for i in range(h + 1):
        for j in range(1,w + 1):
            grid[i][j] += grid[i][j - 1]
    
    for i in range(1,h + 1):
        for j in range(w + 1):
            grid[i][j] += grid[i - 1][j]
    #print(grid)
    ans = INF
    for bit in range(1<<(h - 1)):
        flag = False
        cut = [0]
        for i in range(h - 1):
            if (bit>>i)&1:
                    cut.append(i + 1)
        cut.append(h)
        #print(cut)
        l = len(cut)
        cnt = l - 2
        c = 0
        for j in range(1,w + 1):
            for i in range(1,l):
                #print(c)
                a = cut[i - 1]
                b = cut[i]
                if grid[b][j] - grid[b][c] - grid[a][j] + grid[a][c] > k:
                    if j != 1:
                        c = j - 1
                        cnt += 1
                        break
                    else:
                        flag = True
                        break
            if flag:
                break
        if flag == False:
            ans = min(ans,cnt)
    
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h, w, k = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = list(map(int, list(input())))
    ss.append(s)

from itertools import product

mi = 1e9
ss = np.array(ss)
sss = np.cumsum(ss, axis = 1)
for binary in product([0, 1], repeat=h - 1):
    binary  = [0] + list(binary)
    
    ssss = [0]
    for j in range(h):
        if binary[j] == 1:
            ssss.append(sss[j])
        else:
            ssss[-1] = sss[j] + ssss[-1]
        
    ssss = np.array(ssss)
    if np.max(np.diff(ssss, axis = 1)) > k:
        continue
    
    count = 0
    for i in range(w):
        if max(ssss[:, i]) > k:
            ssss -= ssss[:, i - 1][:, None]
            count += 1
    count += sum(binary)
#     print(binary, count)
#     aaaaaa
    if count < mi:
        mi = count
print(mi)

Submission status: Accepted

Solution code:
from pprint import pprint
h, w, k = map(int, input().split())
maze = []
ts = []
for _ in range(h):
    l = input()
    l = list(map(int, list(l)))
    #print(l)
    x = 0
    tmps = []
    for j in range(w):
        x += l[j]
        tmps.append(x)
    ts.append(tmps)
    maze.append(l)
#pprint(maze)
#pprint("--")
#pprint(ts)

bin_a = ["{:09b}".format(a) for a in range(0, 2 ** (h - 1))]

res = 9999999
for cutpat in bin_a:
    cutpat = cutpat[::-1]
    #print("cutpat", cutpat)
    cutsum = [0] * 10
    gr = [-1] * 10
    gr[0] = 0
    grnum = 0
    for i in range(1, h):
        if cutpat[i - 1] == "1":
            grnum += 1
        gr[i] = grnum
    #print("grlist", gr)

    firstFail = False

    cutcount = cutpat.count("1") # 縦の切った回数
    for i in range(w): # 進む
        #print(" do", i)
        for j in range(h):
            cutsum[ gr[j] ] += maze[j][i]
        #print(" res", cutsum)
        isFail = False
        for j in range(h):
            #print("  chk gr", j)
            if cutsum[j] > k:
                #print("over! gr:", j)
                isFail = True
                if i == 0:
                    firstFail = True
        if isFail:
            #print("cut", i)
            cutcount += 1
            cutsum = [0] * 10
            for j in range(h):
                cutsum[gr[j]] += maze[j][i]
            for j in range(h):
                #print("  chk gr", j)
                if cutsum[j] > k:
                    isFail = True
                    if i == 0:
                        firstFail = True

    if firstFail:
        continue

    res = min(res, cutcount)

print(res)

Submission status: Accepted

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

h_loop = 2**(h-1)
ans = 100000000
for i in range(h_loop):
    sep = format(i,'b').zfill(h-1)
    ups = sum(map(int,list(sep)))
    slash = ups
    buf = [0 for j in range(ups+1)]
    temp_buf = [0 for j in range(ups+1)]
    is_sep = False
    # print(sep)
    # print("########")
    # print(slash)
    for j in range(w):
        # print("#####")
        # print(j)
        b_ind = 0
        is_sep = False
        for k in range(h):
            if k == 0:
                temp_buf[b_ind] += arr[k][j]
            else:
                if sep[k-1] == "1":
                    b_ind += 1
                    temp_buf[b_ind] += arr[k][j]
                else:
                    temp_buf[b_ind] += arr[k][j]

        for k in range(ups+1):
            if temp_buf[k] + buf[k] > kk :
                is_sep = True
        for k in range(ups+1):
            if buf[k] > kk :
                slash = 1000000000
        # print(buf)
        # print(temp_buf)
        # print(is_sep)
        if is_sep:
            slash += 1
            buf = temp_buf
        else:
            for k in range(ups+1):
                buf[k] += temp_buf[k]

        temp_buf = [0 for j in range(ups + 1)]


    # print(slash)
    if ans > slash:
        ans = slash

print(ans)

Submission status: Accepted

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]

    ans = H+W-2
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        cur = inf
                        break
                    cur += 1
                    L = [0] * (len(cut))
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]
        if not flag:
            continue
        ans = min(ans,cur)

    print(ans)
    return
"""
2 1 1
1
1
"""# 1

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]

    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[[int(c) for c in input()] for i in range(H)]
A=[[0]*(W+1) for i in range(H+W)]
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]
from itertools import product
r=2000
def v(l,r,t,b):
    return A[b][r]-A[t][r]-A[b][l]+A[t][l]
for x in product((0,1),repeat=H-1):
    l=0
    a=sum(x)
    for j in range(W):
        f=1
        t=0
        for k in range(H-1):
            if x[k]:
                if v(l,j+1,t,k+1)>K:
                    f=2 if l<j else 0
                    l=j
                t=k+1
        if v(l,j+1,t,H)>K:
            f=2 if l<j else 0
            l=j
        if f==2:
            a+=1
        elif f==0:
            a=-1
            break
    if a>=0:
        r=min(r,a)
print(r)

Submission status: Accepted

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

    m = 10 * 1000
    for h in range(2 ** (H - 1)):
        T = []
        s = [0]
        c = 0
        for i in range(H - 1):
            if h & (1 << i):
                T.append(s)
                s = [i + 1]
                c += 1
            else:
                s.append(i + 1)
        T.append(s)
        C = [0] * len(T)
        CC = [0] * len(T)
        fail = False
        for w in range(W):
            split = False
            for i, t in enumerate(T):
                cc = 0
                for j in t:
                    if S[j][w] == '1':
                        cc += 1
                CC[i] = cc
                if C[i] + CC[i] > K:
                    split = True
            if split:
                for i in range(len(C)):
                    C[i] = CC[i]
                    if C[i] > K:
                        fail = True
                c += 1
            else:
                for i in range(len(C)):
                    C[i] += CC[i]
        if not fail:
            m = min(c, m)
    return m

print(main())

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
chocolate = [input() for _ in range(H)]
cumsums = [[0] for _ in range(W)]
for w in range(W):
    for h in range(H):
        cumsums[w].append(cumsums[w][-1] + int(chocolate[h][w]))
ans = (H-1) + (W-1)
for bit in range(1 << (H-1)):
    h_splits = [0]
    temp = 0
    for l in range(H):
        if (bit >> l) & 1: h_splits.append(l+1); temp += 1
    h_splits.append(H)
    n_sp_hr = (len(h_splits) - 1)
    counter = [0] * n_sp_hr
    for w in range(W):
        admissible = True
        cumsum = cumsums[w]
        to_be_added = [0] * n_sp_hr
        for s in range(n_sp_hr):
            to_be_added[s] = cumsum[h_splits[s+1]] - cumsum[h_splits[s]]
            if to_be_added[s] > K: admissible = False; break
        if not admissible: break
        for s in range(n_sp_hr):
            counter[s] += to_be_added[s]
            if counter[s] > K: temp += 1; counter = to_be_added[:]; break
    else:
        ans = min(ans, temp)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W,K = MAP()
    S = [input() for _ in range(H)]
    accum_s = [[0]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if j == 0:
                accum_s[i][j] = int(S[i][j])
            else:
                accum_s[i][j] = accum_s[i][j-1]+int(S[i][j])

    answer = 10**9
    for p in product([0,1],repeat=H-1):
        one_index = [i for i in range(H-1) if p[i] == 1]
        one_index.append(H-1)
        score = 0
        prev_j = -1
        outflag = False

        for j in range(W):
            if outflag:
                break
            prev_i = 0
            for slice_index in one_index:
                group_count = 0
                
                while prev_i <= slice_index:
                    if prev_j == -1:
                        group_count += accum_s[prev_i][j]
                    else:
                        group_count += accum_s[prev_i][j] - accum_s[prev_i][prev_j]

                    prev_i += 1
                
                if group_count > K:
                    if prev_j == j-1:
                        outflag = True
                    score += 1
                    prev_j = j-1
                    break
        else:
            if answer > score+len(one_index)-1:
                answer = score+len(one_index)-1
    
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
h,w,k=map(int,input().split())
s=[]
for i in range(h):
  s+=[[int(i) for i in input()]]
ans=h+w-2
for i in range(2**(h-1)):
  t=format(i,''.join(['0',str(h-1),'b']))
  a=sum([int(tt) for tt in t])
  h1=[0]+[ii+1 for ii in range(h-1) if t[ii]=='1']+[h]
  h2=[[h1[ii],h1[ii+1]] for ii in range(len(h1)-1)]
  j0=0
  slsum=[0]*len(h2)
  sl=[0]*len(h2)
  for j in range(w):
    for l in range(len(h2)):
      sl[l] = sum([s[ii][j] for ii in range(h2[l][0],h2[l][1])])
      slsum[l]+=sl[l]
      if sl[l]>k:
        a=-1
        break
    if a==-1:
      break
    if any([x>k for x in slsum]):
      slsum=copy.deepcopy(sl)
      a+=1
  if a==-1:
    continue
  ans=min(ans,a)
print(ans)

Submission status: Accepted

Solution code:
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      now = j - 1
      ans += 1
      cane = []
      for k in range(l):
        cane.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
        #if tmp == [0,1,3]:
          #print(cane,j)
        if max(cane) > K:
          ans += 1
          now = j
    #print(l-1,ans,time)
  else:
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
print(min(can))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

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

h,w,k = na()
s = []
for i in range(h):
    o = list(map(int, list(ns())))
    q = 0
    r = []
    for x in o:
        q += x
        r.append(q)
    s.append(r)

ans = 1000000000000000000

for i in range(2**(h-1)):
    b = [0]*w
    c = []
    d = 0 #分割数
    for j in range(h):
        b = [x + y for (x, y) in zip(b, s[j])]
        if j == h:
            break
        if ((i >> j) & 1):
            c.append(b)
            b = [0]*w
            d += 1
    c.append(b)
    e = -1
    for p in range(w):
        flag = False
        for l in c:
            u = 0 if e == -1 else l[e]
            if l[p]-u > k:
                if p-e == 1:
                    flag = True
                    break
                e = p-1
                d += 1
                break
        if flag:
            d = 1000000000000000000
            break
    ans = min(ans, d)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import time
import random

H, W, K = map(int, input().split())
s = [np.array(list(input()), dtype=np.int32) for _ in range(H)]

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

mi = 10 ** 9
seed = [0] * 1000 + [1] * 1000
selected = []

# 全部0
ls = [0]*(H-1)
# numは横線の数
num = 1
tmp = 0

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp


# 全部1
ls = [1]*(H-1)
# numは横線の数
num = H
tmp = num - 1

s3 = np.zeros((num, W))
s3[0] = s2[0]
cnt = 0
for i in range(H - 1):
    if ls[i] == 0:
        s3[cnt] += s2[i + 1]
    else:
        cnt += 1
        s3[cnt] = s2[i + 1]
s3 = s3.T

hosei = np.zeros(num)
for w in range(W):
    if np.max(s3[:][w] - hosei) > K:
        tmp += 1
        if w != 0:
            hosei = s3[:][w - 1]
        else:
            tmp = 10 ** 9
if mi > tmp:
    mi = tmp
    
while time.time() - start < 1.7:
    t = random.sample(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls) + 1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Submission status: Accepted

Solution code:
# ABC159e

ans = 10 ** 12


def main():
    import sys
    import numpy as np
    sys.setrecursionlimit(10 ** 6)
    from copy import deepcopy
    # 再帰関数を使わない限りPypyで出すこと

    def dump(*args):
        sys.stderr.write(str(args))

    h, w, K = map(int, input().split())
    s = [list(map(int, list(input()))) for _ in range(h)]
    s = np.array(s).T
    s = s.tolist()
    # print(s)

    waru = set()

    def dfs(i):
        if i == h-1:
            cho = [0] * (len(waru) + 1)
            bunkatsu = [False]*(w-1)
            sl = [0]
            sl.extend(list(waru))
            sl.append(h)
            t = len(waru)
            j = 0
            while j < w:
                for k in range(1, len(sl)):
                    #print(sl[k - 1], sl[k])
                    cho[k - 1] += sum(s[j][sl[k - 1]: sl[k]])
                #print(waru, j, cho)
                for k in range(len(sl)-1):
                    if cho[k] > K:
                        if bunkatsu[j-1]:
                            return
                        cho = [0] * (len(waru) + 1)
                        bunkatsu[j-1] = True
                        t += 1
                        j -= 1
                j += 1
            #print(waru, t)
            global ans
            ans = min(ans, t)
            return
        waru.add(i+1)
        dfs(i + 1)
        waru.remove(i+1)
        dfs(i + 1)
    dfs(0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inpl():
    return list(map(int, input().split()))


def solve(i):
    def getChoco(choco, w):
        for i in range(H):
            if S[i][w] == "1":
                choco[t[i]] += 1
        return choco

    t = {}
    t[0] = 0
    x = 0
    for h in range(H - 1):
        if (i >> h) % 2 == 1:
            x += 1
            t[h + 1] = x
        else:
            t[h + 1] = x
    choco = [0 for _ in range(x + 1)]
    ret = x
    # print(i, t)

    for w in range(W):
        choco = getChoco(choco, w)
        if any(c > K for c in choco):
            choco = getChoco([0 for _ in range(x + 1)], w)
            if any(c > K for c in choco):
                return H + W - 2
            else:
                ret += 1
    return ret


H, W, K = inpl()
S = [input() for _ in range(H)]

ans = H + W - 2
for i in range(2**(H - 1)):
    ans = min(ans, solve(i))

print(ans)

Submission status: Accepted

Solution code:
import bisect


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

    C = [[0] for _ in range(W)]
    for i in range(W):
        for j in range(H):
            if S[j][i] == "1":
                C[i].append(C[i][-1] + 1)
            else:
                C[i].append(C[i][-1])

    if W == 1:
        c = C[0]
        res = 0
        cut = 0
        for i in range(H):
            if c[i + 1] - c[cut] > K:
                res += 1
                cut = i
        return res

    res = 20000
    for i in range(2 ** (H - 1)):
        f = 0
        cut = [[0]]
        for j in range(H - 1):
            if (2 ** j) & i != 0:
                cut[-1].append(j + 1)
                cut.append([j + 1])
        cut[-1].append(H)
        lc = len(cut)
        tres = lc - 1
        w = [0 for _ in range(lc)]
        for k in range(W):
            if f == 1:
                break
            for j in range(lc):
                t = C[k][cut[j][1]] - C[k][cut[j][0]]
                if t > K:
                    f = 1
                    break
                w[j] += t
            if max(w) > K:
                tres += 1
                w = [C[k][cut[p][1]] - C[k][cut[p][0]] for p in range(lc)]
        if f == 0:
            res = min(res, tres)

    return res


print(main())

Submission status: Accepted

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

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

# tab_v = [[0] * (H + 1) for _ in range(W)]
# for j in range(W):
#     cnt = 0
#     for i in range(H):
#         cnt += S[i][j]
#         tab_v[i + 1][j] = cnt

ans = 1000000007
for case in range(2 ** (H - 1)):
    case_tmp = case
    iscut_v = []
    for i in range(H - 1):
        iscut_v.append(case_tmp % 2)
        case_tmp >>= 1
    #
    parts = []
    vsrc = 0
    for vdst in range(1, H + 1):
        if vdst == H:
            parts.append((vsrc, vdst))
            break
        elif iscut_v[vdst - 1] == 1:
            parts.append((vsrc, vdst))
            vsrc = vdst
        else:
            continue
    #
    possible = False
    hsrc = 0
    iscut_h = [0] * (W - 1)
    for hdst in range(1,  W + 1):
        num_1 = 0
        for vsrc, vdst in parts:
            num_1_tmp = 0
            for i in range(vsrc, vdst):
                num_1_tmp += tab_h[i][hdst] - tab_h[i][hsrc]
            num_1 = max(num_1, num_1_tmp)
            # print("##", hdst, (vsrc, vdst), num_1_tmp)
        #
        if num_1 > K:
            if hdst == 1 or hdst - 1 == hsrc:
                break
            else:
                iscut_h[hdst - 2] = 1
                hsrc = hdst - 1
        else:
            continue
    else:
        possible = True
    #
    if possible:
        ans_tmp = sum(iscut_v) + sum(iscut_h)
        # print("#", iscut_v, iscut_h, ans_tmp)
        ans = min(ans, ans_tmp)

print(ans)

Submission status: Accepted

Solution code:
import copy
H,W,K = [int(i) for i in input().split()]
Chocolate = [[int(i) for i in list(input())]for j in range(H)]
YokoChoko = [[Choc[s] for Choc in Chocolate] for s in range(W)]
minlist = []
for warikata in range(2**(H-1)):#bit全探索
    #[0,1,1,1,2,2,3,3,3,3]みたいなlistを作りたい
    #1start,0なら増やさず1なら増やす
    wareta = [0]
    curw = 0
    for k in range(H-1):
        if (warikata>>k) & 1:
            curw += 1
        wareta.append(curw)
    #curw回割れてcurw + 1ピースに
    nums = [0 for xx in range(curw + 1)]
    watta = curw
    for nbanme,NewChoco in enumerate(YokoChoko):
        newnums = copy.deepcopy(nums)
        for n,choconum in enumerate(NewChoco):
            newnums[wareta[n]] += choconum
        if max(newnums) <= K:#わらんでいい
            nums = newnums
        else:#割る
            if nbanme == 0:
                watta += 9999999999
            watta += 1
            nums = [0 for iii in range(curw + 1)]
            for n,choconum in enumerate(NewChoco):
                nums[wareta[n]] += choconum
    minlist.append(watta)
print(min(minlist))

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

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

        #tableの累積和dを返す
    def csum_gen(h, w, table):
        d = [[0]*w for _ in range(h)]
        d[0][0] = table[0][0]
        for i in range(1, w):
            d[0][i] = d[0][i-1]+table[0][i]
        #上のマスとその行の和を足す
        for i in range(1, h):
            total = 0
            for j in range(w):
                total += table[i][j]
                d[i][j] = d[i-1][j]+total
        return d
    
    d = csum_gen(H, W, table)

    #座標(p, q)を含む長方形の和
    def csum_cal(p, q, x, y, d):
        #p<=x and q<=y
        if p>x or q>y:
            return 0
        if p==0 and q==0:
            return d[x][y]
        if p==0:
            return d[x][y] - d[x][q-1]
        if q==0:
            return d[x][y] - d[p-1][y]
        return d[x][y]-d[p-1][y]-d[x][q-1]+d[p-1][q-1]

    res = 10**15
    for i in range(2**(H-1)):
        tate = [0]
        for j in range(H-1):
            if i & 2**j:
                tate.append(j+1)
        l = len(tate)
        tate.append(H)
        start = 0
        cnt = 0
        flag = 0
        for j in range(W-1):
            for k in range(l):
                if K < csum_cal(tate[k], start, tate[k+1]-1, j, d):
                    flag = 1
            for k in range(l):
                if K < csum_cal(tate[k], start, tate[k+1]-1, j+1, d):
                    cnt += 1
                    start = j+1
                    break
            if flag:
                break
        else:
            res = min(res, cnt+l-1)
    print(res)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

t = [[0]*h for _ in range(w)]
for i in range(h):
    for j in range(w):
        t[j][i] = int(p_[i][j])

#print(t)

ans = 10**7
for i in range(2**(h-1)):
    c = 0
    d = {}
    for j in range(h):
        d[j] = 0
    for j in range(h-1):
        if (i >> j) & 1:
            d[j] = c
            c += 1
        else:
            d[j] = c
    d[h-1] = c
    #print(c)
    #print(d)
    l = [0]*(c+1)
    cnt = c
    for a in range(w):
        temp = [0]*(c+1)
        for b in range(h):
            l[d[b]] += t[a][b]
            temp[d[b]] += t[a][b]
        if max(temp) > k:
            break
        if max(l) > k:
            cnt += 1
            l = temp
    else:
        ans = min(ans, cnt)
    continue

print(ans)

Submission status: Accepted

Solution code:
def check_block(comb, H):
    block = 0
    pre = (comb & 1) > 0
    mapping = {0: 0}
    cut_num = 0
    for i in range(1, H):
        cur = ((1 << i) & comb) > 0
        if pre != cur:
            block += 1
            pre = cur
            cut_num += 1
        mapping[i] = block
    return mapping, cut_num

H, W, K = map(int, input().split())
graph = [input() for ele in range(H)]
#
ans = 1319203291031903
for comb in range(1<<(H-1)):
    mapping, cut_num = check_block(comb, H)
    pre = [0] * (cut_num + 1)
    gg = False
    # preprocess 
    for j in range(H):
        pre[mapping[j]] += (graph[j][0] == '1')
    for ele in pre:
        if ele > K:
            gg = True
            break
    if gg: continue

    for i in range(1, W):
        cum = pre[:]
        for j in range(H):
            cum[mapping[j]] += (graph[j][i] == '1')
        for ii in range(len(cum)):
            if cum[ii] - pre[ii] > K or cut_num > ans:
                gg = True
                break
            if cum[ii] > K:
                cut_num += 1
                for idx in range(len(cum)):
                    cum[idx] -= pre[idx]
                break
        pre = cum
        if gg: break

    if not gg:
        ans = min(ans, cut_num)
print(ans)