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 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)
    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]
#                    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 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,1
#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:])])
            cnt = np.zeros(len(cand)).astype(np.int32)

            if np.count_nonzero(cand > K):
               continue 

            temp = i
            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():
    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]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        base_w = 0
        w = 0
        #print(grids)
        while w <= W:
            #print(base_w, w)
            for grid in grids:
                if np.count_nonzero(grid[:, base_w: w]) > K:
                    #print('out', base_w, w)
                    base_w = w - 1
                    w = base_w
                    tmp_ans += 1
                    break
            else:
                w += 1
        # print('tmp', tmp_ans)
        # print("\n")
        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

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)
    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]
#                    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:
from itertools import combinations
h,w,k=map(int,input().split())
s=[input() for _ in range(h)]

def white_count(l,r,u,d):
    return sum(c[l:r].count('1') for c in s[u:d])

def line_count(horizontal):
    horizontal = [0] + list(horizontal) + [h]
    count = 0
    l=0
    r=1
    
    
    while r<=w:
        if r-l == 1:
            white_count_list=[0]*(len(horizontal)-1)
        
        for i in range(len(horizontal)-1):
            white_count_list[i] += white_count(r-1,r,horizontal[i],horizontal[i+1])
            
            if white_count_list[i]>k:
                count += 1
                if r-l == 1:
                    return h+w
                l = r-1
                break
        else:
            r += 1
    return count
    
ans = line_count(())
for i in range(h):
    for horizontal in combinations(range(1,h),i):
        count = i
        count += line_count(horizontal)
        ans = min(ans,count)
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)):
    cut = [i & (2**a) != 0 for a in range(h - 1)]
    t = 0
    to_add = [0]
    for cut_ in cut:
        if cut_:
            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
            cnts = [0 for _ in range(n_h + 1)]
            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())
import numpy as np
l=[[0 for i in range(w+1)]]+[[0]+[int(j) for j in input()] for i in range(h)]
a=np.cumsum(l,axis=1)
a=np.cumsum(a,axis=0)
ans=h*w
def ink(h2,h1,w2,w1):
    return a[h2][w2]-a[h1][w2]-(a[h2][w1]-a[h1][w1])
for i in range(2**(h-1)):
    tl=[0]
    for j in range(h-1):
        if i>>j&1:
            tl.append(j+1)
    tl.append(h)
    t=len(tl)-2
    w1=0
    for w2 in range(1,w+1):
        for h1,h2 in zip(tl,tl[1:]):
            if ink(h2,h1,w2,w1)>k:
                w1=w2-1
                t+=1
                break
    ans=min(ans,t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int,input().split())
s = []
for i in range(h):
    s0 = list(input())
    s.append(s0)
al = []
wl = [[0 for i in range(h)] for i in range(w)]
for i in range(w):
    count = 0
    for j in range(h):
        if s[j][i] == "1":
            count += 1
        wl[i][j] = count
for i in range(2**(h-1)):
    ans = 0
    b = []
    for j in range(h-1):
        if ((i >> j) & 1):
            b.append(j)
    #print(b)
    b.append(h-1)
    bl = []
    now = -1
    for j in b:
        if now == -1:
            bl.append(wl[0][j])
            now = j
        else:
            bl.append(wl[0][j]-wl[0][now])
            now = j
    ans = len(bl)-1
    key = 1
    key2 = 0
    for j in range(1,w):
        now = -1
        aa = []
        key2 = 0
        for x in  range(len(bl)):
            #print(bl)
            if now == -1:
                if bl[x] > k:
                    key = 0
                    break
                else:
                    bl[x] += wl[j][b[x]]
                    aa.append(wl[j][b[x]])
                    if bl[x] > k:
                        key2 = 1
                    now = b[x]
            else:
                if bl[x] > k:
                    key = 0
                    break
                else:
                    bl[x] += wl[j][b[x]] - wl[j][now]
                    aa.append(wl[j][b[x]]-wl[j][now])
                    now = b[x]
                    if bl[x] > k:
                        key2 = 1
        if key2 == 1 and key == 1:
            for x in range(len(bl)):
                bl[x] = aa[x]
            ans += 1
        elif key == 0:
            break
    if key == 1:
        al.append(ans)
print(min(al))

Submission status: Time Limit Exceeded

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

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

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

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

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

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

def num_whites(l,r,t,b):
    ret = 0
    for y in range(t, b):
        for x in range(l, r):
            if grid[y][x] == "1":
                ret += 1
    # log(l,r,t,b,ret)
    return ret

ans = 999999999999999999

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

    # log("h_breaks: ", h_breaks)

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

print(ans)

Submission status: Time Limit Exceeded

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

def white_count(l,r,u,d):
    return sum(c[l:r].count('1') for c in s[u:d])

def line_count(horizontal):
    count = 0
    l=0
    r=1
    while r<=w:
        for u,d in zip([0]+list(horizontal),list(horizontal)+[h]):
            if white_count(l,r,u,d)>k:
                count += 1
                if r-l == 1:
                    return h+w
                l = r-1
                break
        else:
            r += 1
    return count
    
ans = line_count(())
for i in range(h):
    for horizontal in combinations(range(1,h),i):
        count = i
        count += line_count(horizontal)
        ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

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
      l = ok
      tres += int(l < W)

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

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)])
#H,W,K = 10,1000,1
#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 = []
            for f,g in zip(p,p[1:]):
                c = np.sum(s[f:g],axis=0)
                cand.append(c)
            cand = np.array(cand)
            cnt = np.zeros(len(cand)).astype(np.int32)
            temp = i
            sums = np.cumsum(cand,axis=1)
            for w in range(W):
                '''
                if np.count_nonzero(sums[:,w] > K):
                    temp += 1
                    print("a",sums)
                    print("b",[sums[:,w-1]])
                    sums -= [sums[:,w-1]]
                '''
                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():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


#n,*a = [int(i) for i in read().split()]

h,w,k = [int(i) for i in readline().split()]
b = [readline() for _ in range(h)]

ans = INF = 10**9
N = 2**(h-1)


for mask in range(N):
    res = [(mask>>j)&1 for j in range(h-1)]
    
    R = []
    now = [0]
    for i in range(h-1):
        if res[i] == 0:
            now.append(i+1)
        else:
            R.append(now[:])
            now = [i+1]
    if now: R.append(now[:])
    
    L = len(R)
    val = res.count(1)

    num = [0]*L
    for i in range(w):
        nnum = [0]*L
        for j in range(L):
            p = 0
            for kk in R[j]:
                if b[kk][i]=="1": p += 1
            nnum[j] = p
        
        #print(R,i,num,nnum)
        for j in range(L):   
            if num[j] + nnum[j] > k:
                val += 1
                num = nnum
                break
        else:
            for j in range(L): num[j] += nnum[j]
        
        
        if any(ni>k for ni in nnum):
            val = INF
            break
    
    #print(val)
    ans = min(ans,val)

print(ans)

Submission status: Time Limit Exceeded

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:
                cnt += 1
                l = r-1
                r = r
                break
        else:
            r += 1
    ans = min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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
import numpy as np
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:
        nS = np.zeros(W)
        for tS in tmpS:
            nS += tS
        # print(nS)
        nSS.append(nS)

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

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
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int,input().split())

sl = []
for _ in range(h):
    s = list(input())
    s = [int(i) for i in s]
    sl.append(s)
import itertools
sl_ac = []
for s in sl:
     ac = [0] + list(itertools.accumulate(s))
     sl_ac.append(ac)

anss = float("inf")


from itertools import product
for bits in product([0, 1], repeat=h-1):
    ans = 0
    ans += sum(bits)
    p = 0
    group = [0 for i in range(h)]
    for idx, bit in enumerate(bits):
        group[idx] = p
        p += bit
    group[-1] = p
    sum_group = [0 for i in range(sum(bits) + 1)]
    reset = 0
    flag = "OK"
    for i in range(w):
        for j in range(h):
            sum_group[group[j]] += sl[j][i]
        if max(sum_group) > k:
            if i == 0:
                flag = "NG"
            else:
                ans += 1
                reset = i
                sum_group = [0 for i in range(sum(bits) + 1)]
                for j in range(h):
                    sum_group[group[j]] += sl[j][i]
                if max(sum_group) > k:
                    flag = "NG"

    if flag == "OK":
        anss = min(ans, anss)
print(anss)

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

ans = 10 * 1000 + 100
for i in range(H):
    for p in combinations(range(1,H),i):
        p = [0] + list(p) + [H]
        cand = []
        for f,g in zip(p,p[1:]):
            c = np.sum(s[f:g],axis=0)
            cand.append(c)
        cand = np.array(cand)
        cnt = np.zeros(len(cand)).astype(np.int32)
        temp = i
        for w in range(W):
            cnt += cand[:,w]
            if np.count_nonzero(cnt > K):
                temp += 1
                cnt = cand[:,w]
        ans = min(temp,ans)
                
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, K = map(int, input().split())
S = [[int(i) for i in input()] 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
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

Submission status: Time Limit Exceeded

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 = now.copy()
        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: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

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

h,w,k = nm()
s = [list(map(int, list(ns()))) for _ in range(h)]
ans = h*w
for bit in range(1<<(h-1)):
    d = dict()
    l = list()
    q = [0]
    for j in range(h-1):
        if bit & (1<<j):
            l.append(tuple(q))
            q = list()
        q.append(j+1)
    l.append(tuple(q))
    t = len(l)
    for i in range(t):
        for x in l[i]:
            d[x] = i
    cur = bin(bit).count('1')
    g = [0]*t
    for j in range(w):
        c = [0]*t
        for i in range(h):
            c[d[i]] += s[i][j]
        if max(c) > k:
            cur = h*w
            break
        for i in range(t):
            g[i] += c[i]
        if max(g) > k:
            cur += 1
            g = c[:]
    if ans > cur: ans = cur
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, K = na()
b = []
for i in range(n):
    b.append(ns())

ans = 999999999999999
for ptn in range(1<<m-1):
    lans = 0
    x = ptn
    while x > 0:
        lans += x&1
        x //= 2

    to = [0] * n
    for i in range(1,n):
        if ptn>>i-1&1:
            to[i] = i
        else:
            to[i] = to[i-1]
    f = [0] * n
    ok = True
    for j in range(m):
        plus = [0] * n
        for r in range(n):
            plus[to[r]] += ord(b[r][j])-ord("0")
            if plus[to[r]] > K:
                ok = False
                break

        if not ok: break
        reset = False
        for r in range(n):
            if f[r] + plus[r] > K:
                reset = True
        if reset:
            lans += 1
            f = plus
        else:
            for i in range(n):
                f[i] += plus[i]
    if not ok:
        continue
    ans = min(ans, lans)
print(ans)

Submission status: Accepted

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

ans = float("inf")
for i in range(2 ** (h - 1)):
    a = 0
    for j in range(h - 1):
        if (i >> j) & 1 == 1:
            a += 1
    c = a
    b = [0] * (c + 1)
    ok2 = True
    for j in range(w):
        tmp = 0
        for l in range(h):
            if s[l][j] == "1":
                b[tmp] += 1
            if (i >> l) & 1 == 1:
                tmp += 1

        ok = True
        for l in b:
            if l > k:
                ok = False

        if not ok:
            a += 1
            b = [0] * (c + 1)

            tmp = 0
            for l in range(h):
                if s[l][j] == "1":
                    b[tmp] += 1
                if (i >> l) & 1 == 1:
                    tmp += 1

            ok = True
            for l in b:
                if l > k:
                    ok = False
            if not ok:
                ok2 = False
                break
    if ok2:
        ans = min(ans, a)

print(ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[]
    for _ in range(H):
        s=input()
        S.append(s)
        
    # Hに関してbit全探索
    import itertools
    
    inf=10**10
    ans=inf
    
    import bisect
    for ite in itertools.product([0,1], repeat=H-1):
        temp=sum(ite)
        g=[-1]#グループに分ける，区切り(末尾)の数字をいれる
        for i in range(len(ite)):
            if ite[i]==1:
                g.append(i)
        
        M=len(g)
        cnt=[0]*M#グループ毎
        
        flag=1#無理かどうか
        for j in range(W):
            if flag==0:
                break
            cnt2=[0]*M#各列用
            
            #数える
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)-1
                    cnt[num]+=1
                    cnt2[num]+=1
            
            #無理
            for i in range(M):
                if cnt2[i]>K:
                    temp=inf
                    flag=0
                    break
                
            #わるか確認
            flag2=0
            for i in range(M):
                if cnt[i]>K:
                    flag2=1
                    break
            #わる
            if flag2:
                for i in range(M):
                    cnt[i]=cnt2[i]
                temp+=1
                
        # print(ite,temp,g)
                    
        ans=min(ans,temp)
        
    print(ans)
                  
                
                

main()

Submission status: Accepted

Solution code:

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


INF = float("inf")
ans = INF

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



for i in range(1<<(H-1)):
    to_cut = []
    tmp = 0
    for j in range(H-1):
        if (i>>j)&1:
            tmp += 1
            to_cut.append(j+1)
    to_cut.append(H)
    blocks = []
    for i in range(len(to_cut)):
        if i == 0:
            blocks.append(cum[to_cut[0]][W])
        else:
            blocks.append(cum[to_cut[i]][W] - cum[to_cut[i-1]][W])
    # print(to_cut, blocks)
    dic = {i: 0 for i in range(1, H+1)}
    ptr = 0
    for i in range(1, H+1):
        if i <= to_cut[ptr]:
            dic[i] = ptr
        else:
            ptr += 1
            dic[i] = ptr
    # print(dic)
    length = len(blocks)
    tmp_sum = [0]*length
    w = 1
    last_cut_pnt = 0
    is_all_bad = 0
    while w <= W:
        for i in range(1, H+1):
            tmp_sum[dic[i]] += int(S[i][w]==1)
        is_over_k = 0
        for i in range(1, H+1):
            if tmp_sum[dic[i]] > K:
                is_over_k = 1
                break
        
        if is_over_k:
            tmp_sum = [0]*length
            tmp += 1
            if last_cut_pnt == w:
                is_all_bad = 1
                break
            last_cut_pnt = w
        else:
            w += 1

    if is_all_bad:
        continue
    else:
        ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
Ss = [list(map(int, input().replace("\n", ""))) for _ in range(H)]

cut_yoko_patterns = ["0","1"]
options = ["0","1"]

import copy

for i in range(H-2):
    cut_yoko_patterns = [cut_yoko_patterns[i] + options[j] for i in range(len(cut_yoko_patterns)) for j in range(len(options))]

answer = int(1e+5)
for cut_yoko_pattern in cut_yoko_patterns:
    yoko_cut_num = cut_yoko_pattern.count("1")
    boxs = [0 for _ in range(yoko_cut_num+1)]
    box_num = [0 for _ in range(H)]
    for i in range(H-1):
        if cut_yoko_pattern[i] == "1":
            box_num[i+1] = box_num[i] + 1
        else:
            box_num[i+1] = box_num[i]
    
    tate_cut_num = 0
    for j in range(W):
        temp_boxs = [0 for _ in range(yoko_cut_num+1)]
        for i in range(H):
            if Ss[i][j] == 1:
                temp_boxs[box_num[i]] += 1
        Impossible = False
        Should_cut = False
        for i in range(yoko_cut_num+1):
            if temp_boxs[i] > K:
                Impossible = True
            
            elif boxs[i] + temp_boxs[i] > K:
                Should_cut = True
        
        if Impossible == True:
            break
        elif Should_cut ==True:
            boxs = copy.deepcopy(temp_boxs)
            tate_cut_num += 1
        else:
            for i in range(yoko_cut_num+1):
                boxs[i] += temp_boxs[i]
    else:
        
        if tate_cut_num+yoko_cut_num < answer:
            answer = tate_cut_num + yoko_cut_num
print(answer)