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: Time Limit Exceeded

Solution code:
from itertools import product
from copy import deepcopy

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

ans = float("inf")
for pat in product([1, 0], repeat=h):
    prev = 2
    sm = -1
    for e in pat:
        if e != prev:
            sm += 1
        prev = e
    #print(pat)
    #print(sm)

    ss = [[0] * w for _ in range(h)]
    for wi in range(w):
        acc = 0
        prev = 2
        for hi, e in enumerate(pat):
            if e != prev:
                acc = 0
            if s[hi][wi]:
                acc += 1
            ss[hi][wi] = acc
            prev = e

    sss = [[0] * w for _ in range(h)]
    for hi in range(h):
        for wi in range(w):
            if wi == 0:
                sss[hi][wi] = ss[hi][wi]
            else:
                sss[hi][wi] = sss[hi][wi-1] + ss[hi][wi]

    base = [0] * h
    cp_prev = [0] * h
    for wi in range(w):
        mx = 0
        cp = [0] * h
        for hi in range(h):
            mx = max(mx, sss[hi][wi] - base[hi])
            cp[hi] = sss[hi][wi]
        if mx > k:
            if wi == 0:
                sm = 10000
            sm += 1
            base = deepcopy(cp_prev)
        cp_prev = deepcopy(cp)

    ans = min(ans, sm)

print(ans)

Submission status: Time Limit Exceeded

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:
                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)

Submission status: Time Limit Exceeded

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
        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]:
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

min_cnt = H * W
for row_choice in range(2**(H-1)):
    S = np.copy(S_orig)
    row_splits = []
    for r in range(H-1):
        if (row_choice >> r) & 1:
            row_splits.append(r+1)
    splitted_rows = np.vsplit(S, row_splits)
    splitted_rows = np.array([np.sum(row, axis=0) for row in splitted_rows])
    
    cnt = len(row_splits)
    start = 0
    for i in range(W+1):
        if (splitted_rows[:, start: i].sum(axis=1) > K).any():
            start = i - 1
            cnt += 1
    min_cnt = min([cnt, min_cnt])
    
print(min_cnt)

Submission status: Time Limit Exceeded

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()
import numpy as np

h,w,k = na()
s = []
for i in range(h):
    o = list(np.cumsum(list(map(int, list(ns())))))
    s.append(o)

s = np.array(s)

ans = 1000000000000000000



for i in range(2**(h-1)):
    b = np.array([0]*w)
    c = []
    d = 0 #分割数
    for j in range(h):
        b += np.array(s[j])
        if j == h:
            break
        if ((i >> j) & 1):
            c.append(list(b))
            b = np.array([0]*w)
            d += 1
    c.append(list(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: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.buffer.readline
import numpy as np
 
def main():
    H,W,K = map(int,input().split())
    a = [input() for _ in range(H)]
    
    x = np.zeros((H,W+1),dtype=int)
    for i in range(H):
        for j in range(W):
            if a[i][j] == "1":
                x[i][j+1] = 1
            else:
                x[i][j+1] = 0

    ans = 10**5
    for i in range(1<<H-1):
        use = np.zeros((H,W+1),dtype=int)
        u,now,count = 0,0,0
        for j in range(H-1):
            if (i>>j)&1 == 1:
                count += 1
                bl = x[u:j+1,:]
                bl = np.sum(bl,axis=0)
                u = j+1
                use[now] = bl
                now += 1
        bl = np.sum(x[u:,:],axis=0)
        use[now] = bl
        r,vol = 1,np.zeros((H,1),dtype=int)
        while r<=W:
            vol += use[:,r].reshape(-1,1)
            if np.max(vol)>K:
                count += 1
                vol = np.zeros((H,1),dtype=int)
                vol += use[:,r].reshape(-1,1)
            r += 1
        ans = min(ans,count)
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
def saiki(num,lis):
    if num==H:
        cand.append(lis)
    else:
        saiki(num+1,lis+[lis[-1]])
        saiki(num+1,lis+[num])
#全探索
H,W,K=map(int,input().split())

S=[]
for h in range(H):
    s=list(input())
    S.append(list(map(int,s)))
        
cand=[]

saiki(1,[0])

ans=[]
for item in cand:
    temp=len(list(set(item)))-1
    wa=[[0]*W for i in range(H)]
    for i in range(H):
        for j in range(W):
            wa[item[i]][j]+=S[i][j]
    #クラスタを作っていきたい
    sam=[0]*H
    count=0
    for w in range(W):
        judge=False
        for h in range(H):
            if wa[h][w]>K:
                judge=True
            sam[h]+=wa[h][w]
            if w!=W-1:
                if sam[h]+wa[h][w+1]>K:
                    count+=1
                    for i in range(H):
                        
                        sam[i]=0
                    break
        if judge:
            count=10**9
            break
    """
    print("------------------")
    print(item)
    print(sam)
    """
    ans.append(temp+count)
    #print(wa)
print(min(ans))
#print(cand)
#print(S)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    from itertools import product
    H, W, K = map(int, input().split())
    G = np.array([list(map(int, list(input()))) for _ in range(H)])
    #print(np.count_nonzero(G[:, 1:1]))
    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]
        rows = []
        for i in range(len(div) - 1):
            rows.append(np.sum(G[div[i]: div[i + 1]], axis=0).tolist())

        w = 0
        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]:
                tmp_ans += 1
                counts = [0] * len(rows)
            else:
                w += 1

        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

area = [input() for _ in range(H)]
ans = float('inf')
for i in range(1 << H-1):
    flag = False
    tmp_ans = 0
    mapping = [-1 for n in range(H)]
    tmp = 0
    for j in range(H):
        if i >> j & 1 == 1:
            tmp_ans += 1
            mapping[j] = tmp
            tmp += 1
        else:
            mapping[j] = tmp
    T = tmp_ans+1
    counter = [0 for _ in range(T)]

    for w in range(W):
        tmp_counter = [0 for _ in range(T)]
        for h in range(H):
            if area[h][w] == '1':
                tmp_counter[mapping[h]] += 1
        for tmp in tmp_counter:
            if tmp > K:
                flag = True
        if flag:
            tmp_ans = float('inf')
            break

        for k, tmp in enumerate(tmp_counter):
            if counter[k]+tmp > K:
                tmp_ans += 1
                counter = tmp_counter
                break
            else:
                counter[k] += tmp
    ans = min(ans, tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

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()
    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 = [0 for _ in range(n_h + 1)]
            cnts = zz.copy()
            for y in range(h):
                cnts[to_add[y]] += ar[y][x]
    if ans is None or ans > n_h + n_w:
        ans = n_h + n_w
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int,input().split())
s = []
for i in range(h):
  si = str(input())
  s.append(si)
mn = float("inf")
for i in range(2**(h-1)):
  bi = bin(i)[2:]
  ze = ""
  for i in range(h-1-len(bi)):
    ze += "0"
  bi = ze + bi + "0"
  c = 0
  for bii in bi:
    if bii == "1":
      c += 1
  cc = c
  wh = [0 for _ in range(cc+1)]
  j = 0
  while j < w:
    p = 0  
    whn = [0 for _ in range(cc+1)]
    for l in range(h):
      if s[l][j] == "1":
        wh[p] += 1
        whn[p] += 1
      if bi[l] == "1":
        p += 1
    if max(whn) > k:
      break
    if max(wh) > k:
      c += 1
      wh = whn
    j += 1
  if j == w:
    if c < mn:
      mn = c
print(mn)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations
H,W,K= map(int,input().split())
s = np.array([list(map(int,list(input()))) for i in range(H)]).astype(np.int32)
#H,W,K = 10,1000,10000
#s = np.ones((10,1000)).astype(np.int32)

def solve():
    ans = 10 * 1000 + 100
    for i in range(H):
        for p in combinations(range(1,H),i):
            p = [0] + list(p) + [H]
            cand = np.array([np.sum(s[f:g],axis=0) for f,g in zip(p,p[1:])]).T

            if np.count_nonzero(cand > K):
               continue 

            temp = i

            cnt = np.zeros(i+1).astype(np.int32)
            for w in range(W):
                cnt += cand[w]
                if np.count_nonzero(cnt > K):
                    temp += 1
                    if temp > ans:
                        break
                    cnt = cand[w]
            ans = min(temp,ans)
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w, k = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    t = [[0]*(w+1) for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                t[i+1][j+1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1]
#    for i in range(h+1):
#        print(t[i])
    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        F = True
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
                for l in range(1, len(buf)):
                    if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][j-1] + t[buf[l-1]][j-1] > k:
                        F = False
        if a + b < ans and F:
#            print(a, b, i, x)
            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w,k = map(int,input().split())
s = []
for i in range(h):
  si = str(input())
  s.append(si)
mn = float("inf")
for i in range(2**(h-1)):
  bi = bin(i)[2:]
  ze = ""
  for i in range(h-1-len(bi)):
    ze += "0"
  bi = ze + bi + "0"
  c = 0
  for bii in bi:
    if bii == "1":
      c += 1
  cc = c
  wh = [0 for _ in range(cc+1)]
  j = 0
  while j < w:
    p = 0  
    whn = [0 for _ in range(cc+1)]
    for l in range(h):
      if s[l][j] == "1":
        wh[p] += 1
        whn[p] += 1
      if bi[l] == "1":
        p += 1
    if max(whn) > k:
      break
    if max(wh) > k:
      c += 1
      wh = copy.deepcopy(whn)
    j += 1
  if j == w:
    if c < mn:
      mn = c
print(mn)

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
Cho=[list(map(int,list(input()))) for _ in range(h)]
ans=10000000
for i in range(2**(h-1)):
	need=0
	seq=[]
	t=[]
	for j in range(h-1):
		t.append(j)
		if i&(1<<j):
			need+=1
			seq.append(t)
			t=[]
	seq.append(t+[h-1])
	f=1
	q=need+1
	cnt=[0]*q
	for x in range(w):
		cntp=[0]*q
		for i,g in enumerate(seq):
			cntg=0
			for y in g:
				cntg+=Cho[y][x]
				if cntg>k:
					f=0
					break
				cntp[i]+=Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx]+=cntp[xx]
		if any(xxx>k for xxx in cnt):
			need+=1
			cnt=cntp
	if f:
		ans=min(ans,need)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(2**h):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1 == 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1 == 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        cut = []
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    cut.append(j - 1)
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

res = 10**9

for i in range(2**(H-1)):
    yoko = []
    for j in range(H-1):
        if (i>>j) & 1:
            yoko.append(j+1)
    yoko.append(H)
    
    sen = len(yoko)-1

    rS = [[0]*W for _ in range(sen+1)]

    flag = False

    for w in range(W):
        b = 0
        for j in range(sen+1):
            t = b
            b = yoko[j]
            for h in range(t, b):
                if S[h][w] == "1":
                    rS[j][w] += 1
            if rS[j][w] > K:
                flag = True
                break
        if flag:
            break
    
    if flag:
        continue
    
    x = [r[0] for r in rS]
    for w in range(1, W):
        for h in range(len(yoko)):
            x[h] += rS[h][w]
            if x[h] > K:
                x = [r[w] for r in rS]
                sen += 1
                break
    
    res = min(sen, res)
    if res == 0:
        break

print(res)

Submission status: Time Limit Exceeded

Solution code:
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))
    for P in product( range(2), repeat=H-1):
        now = sum(P)
        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)
                    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
                    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: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline

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

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

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1 == 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        cut = []
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i in range(len(border) - 1):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[i + 1]][j0] - cs[
                        border[i]][j] + cs[border[i]][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    cut.append(j - 1)
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

# print(*cs, sep='\n')
# print()

ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1 == 1:
            border.append(i + 1)
            cand += 1
    border.append(h)
    cand0 = cand
    j0 = 0
    cut = []
    j = 1
    while j <= w:
        # for j in range(1, w + 1):
        for i in range(len(border) - 1):
            # print(
            #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
            #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
            if cs[border[i + 1]][j] - cs[border[i + 1]][j0] - cs[
                    border[i]][j] + cs[border[i]][j0] > k:
                cand += 1
                j0 = j - 1
                j -= 1
                cut.append(j - 1)
                # print(border[i + 1], j, cs[border[i + 1]][j])
                break
        j += 1

    # print(border, cand0, cand, cut)
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

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

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

# print(*cs, sep='\n')
# print()

ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1 == 1:
            border.append(i + 1)
            cand += 1
    border.append(h)
    cand0 = cand
    j0 = 0
    cut = []
    j = 1
    while j <= w:
        # for j in range(1, w + 1):
        for i in range(len(border) - 1):
            # print(
            #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
            #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
            if cs[border[i + 1]][j] - cs[border[i + 1]][j0] - cs[
                    border[i]][j] + cs[border[i]][j0] > k:
                cand += 1
                j0 = j - 1
                j -= 1
                cut.append(j - 1)
                # print(border[i + 1], j, cs[border[i + 1]][j])
                break
        j += 1

    # print(border, cand0, cand, cut)
    ans = min(ans, cand)
print(ans)

Submission status: Time Limit Exceeded

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
    cnts = [0 for _ in range(n_h + 1)]
    for x in range(w):
        for y in range(h):
            cnts[to_add[y]] += ar[y][x]
        if max(cnts) > k:
            n_w += 1
            for z in range(n_h + 1):
                cnts[z] = 0
            for y in range(h):
                cnts[to_add[y]] += ar[y][x]
            if ans is not None and ans <= n_h + n_w:
                break
    if ans is None or ans > n_h + n_w:
        ans = n_h + n_w
print(ans)