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 as acc

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

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    while x < W:
        w_split_num += 1
        x = solve(l, x, K)
    split_num = w_split_num + h_split_num
    min_num = min(split_num, min_num)

print(min_num)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate as acc

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

acc_list = [list(acc([0] + s)) for s in S]

# print(acc_list)

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    while x < W:
        w_split_num += 1
        x = solve(l, x, K)
    split_num = w_split_num + h_split_num
    min_num = min(split_num, min_num)

print(min_num)

Submission status: Time Limit Exceeded

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

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    #import numpy as np
    import sys, math
    from itertools import permutations, combinations
    from collections import defaultdict, Counter, deque
    from math import factorial#, gcd
    from bisect import bisect_left #bisect_left(list, value)
    sys.setrecursionlimit(10**7)
    enu = enumerate
    MOD = 10**9+7
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

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

    from copy import deepcopy
    cS = [[0]*(W+1) for _ in range(H+1)]
    # cS = deepcopy(S)

    for h in range(1, H+1):
        for w in range(W):
            cS[h][w+1] = cS[h][w] + S[h-1][w]
    for w in range(1, W+1):
        for h in range(H):
            cS[h+1][w] = cS[h][w] + cS[h+1][w]
    # pl(cS)

    mcut = 10**9
    for i in range(2**(H-1)):
        yoko = []
        for j in range(H):
            if ((i >> j) & 1):
                yoko.append(j+1)
        yoko = [0] + yoko + [H]
        # yoko.append(H)
        # print(yoko)
        
        cut = len(yoko)-2
        lastcut = 0 # index-w
        w = 1
        while w < W+1:
            cannot = False
            for ind, y in enu(yoko):
                if cannot:
                    w = W + 100
                    break
                if ind == 0:
                    continue
                v1 = cS[y][w]
                v2 = cS[yoko[ind-1]][w]
                v3 = cS[yoko[ind-1]][lastcut]
                v4 = cS[y][lastcut]
                val = v1 - v2 + v3 - v4
                # print('  v1, v2', v1, v2)
                if K < val:
                    cut += 1
                    if lastcut == w-1:
                        cannot = True
                    lastcut = w-1
                    break
            else:
                w += 1
            # print(' val', val)
        if cut < mcut:
            mcut = cut

    print(mcut)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    #import numpy as np
    import sys, math
    from itertools import permutations, combinations
    from collections import defaultdict, Counter, deque
    from math import factorial#, gcd
    from bisect import bisect_left #bisect_left(list, value)
    sys.setrecursionlimit(10**7)
    enu = enumerate
    MOD = 10**9+7
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

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

    from copy import deepcopy
    cS = [[0]*(W+1) for _ in range(H+1)]
    # cS = deepcopy(S)

    for h in range(1, H+1):
        for w in range(W):
            cS[h][w+1] = cS[h][w] + S[h-1][w]
    for w in range(1, W+1):
        for h in range(H):
            cS[h+1][w] = cS[h][w] + cS[h+1][w]
    # pl(cS)

    mcut = 10**9
    for i in range(2**(H-1)):
        yoko = []
        for j in range(H):
            if ((i >> j) & 1):
                yoko.append(j+1)
        yoko = [0] + yoko + [H]
        # yoko.append(H)
        # print(yoko)
        
        cut = len(yoko)-2
        lastcut = 0 # index-w
        w = 1
        while w < W+1:
            for ind, y in enu(yoko):
                if ind == 0:
                    continue
                v1 = cS[y][w]
                v2 = cS[yoko[ind-1]][w]
                v3 = cS[yoko[ind-1]][lastcut]
                v4 = cS[y][lastcut]
                val = v1 - v2 + v3 - v4
                # print('  v1, v2', v1, v2)
                if K < val:
                    cut += 1
                    lastcut = w-1
                    break
            else:
                w += 1
            # print(' val', val)
        if cut < mcut:
            mcut = cut

    print(mcut)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

from copy import deepcopy
cS = [[0]*(W+1) for _ in range(H+1)]
# cS = deepcopy(S)

for h in range(1, H+1):
    for w in range(W):
        cS[h][w+1] = cS[h][w] + S[h-1][w]
for w in range(1, W+1):
    for h in range(H):
        cS[h+1][w] = cS[h][w] + cS[h+1][w]
# pl(cS)

mcut = 10**9
for i in range(2**(H-1)):
    yoko = []
    for j in range(H):
        if ((i >> j) & 1):
            yoko.append(j+1)
    yoko = [0] + yoko + [H]
    # yoko.append(H)
    # print(yoko)
    
    cut = len(yoko)-2
    lastcut = 0 # index-w
    w = 1
    while w < W+1:
        for ind, y in enu(yoko):
            if ind == 0:
                continue
            v1 = cS[y][w]
            v2 = cS[yoko[ind-1]][w]
            v3 = cS[yoko[ind-1]][lastcut]
            v4 = cS[y][lastcut]
            val = v1 - v2 + v3 - v4
            # print('  v1, v2', v1, v2)
            if K < val:
                cut += 1
                lastcut = w-1
                break
        else:
            w += 1
        # print(' val', val)

    mcut = min(mcut, cut)
print(mcut)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')
from copy import deepcopy

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

# for h in range(H):
#     for w in range(W):
#         cumS[h+1][w+1] += cumS[h+1][w]
for h in range(H):
    for w in range(W):
        cumS[h+1][w+1] += S[h][w]
        cumS[h+1][w+1] += cumS[h][w+1]

n = H-1
cut_min = 10**9
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = []
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko)
    # tate
    yoko = [0] + yoko + [H]
    cnt = np.array([0]*(len(yoko)-1))
    ncnt = [0]*(len(yoko)-1)
    for j in range(W):
        for k, (y1, y2) in enu(zip(yoko[:-1], yoko[1:])):
            # print('npS[y1:y2, j]', npS[y1:y2, j])
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        ncnt = np.array(ncnt)

        if any(K < cnt+ncnt):
            cut += 1
            cnt = ncnt.copy()
        else:
            cnt += ncnt
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')
from copy import deepcopy

H, W, K = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
cumS = [[0]*(W+1) for _ in range(H+1)]
for h in range(H):
    for w in range(W):
        cumS[h+1][w+1] = S[h][w]

# for h in range(H):
#     for w in range(W):
#         cumS[h+1][w+1] += cumS[h+1][w]
for h in range(H):
    for w in range(W):
        cumS[h+1][w+1] += cumS[h][w+1]

n = H-1
cut_min = 10**9
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = []
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko)
    # tate
    yoko = [0] + yoko + [H]
    cnt = np.array([0]*(len(yoko)-1))
    ncnt = [0]*(len(yoko)-1)
    for j in range(W):
        for k, (y1, y2) in enu(zip(yoko[:-1], yoko[1:])):
            # print('npS[y1:y2, j]', npS[y1:y2, j])
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        ncnt = np.array(ncnt)

        if any(K < cnt+ncnt):
            cut += 1
            cnt = ncnt.copy()
        else:
            cnt += ncnt
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

n = H-1
cut_min = 10**9
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = []
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    # print(yoko)
    cut += len(yoko)
    # tate
    cnt = np.array([0]*(len(yoko)+1))
    yoko = [0] + yoko + [H]
    for j in range(W):
        ncnt = []
        for k, (y1, y2) in enu(zip(yoko[:-1], yoko[1:])):
            # print('npS[y1:y2, j]', npS[y1:y2, j])
            ncnt.append(np.count_nonzero(npS[y1:y2, j]))
        ncnt = np.array(ncnt)
        # print('ncnt', ncnt)

        if any(K < cnt+ncnt):
            cut += 1
            cnt = ncnt
        else:
            cnt += ncnt

    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Time Limit Exceeded

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

def gru_hol(HOL): # セットから切り方を作る
    groups_a = []
    group_a = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups_a.append(group_a)
            group_a = [i+1]
        else:
            group_a.append(i+1)
    groups_a.append(group_a)
    return groups_a

def nex_hol(HOL): #次のセットを作る
    for j in range(h-1):
        if(HOL[j] == 0):
            HOL[j] = 1
            for k in range(0,j):
                HOL[k] = 0
            break
    return HOL

def cutsum(grp,lscut,nxcut): #groupのlastcut~nextcutのホワイトチョコを数える
    count = 0
    for i in grp:
        for j in range(lscut,nxcut):
            count += s[i][j]
    return count

def cutcheck(grp_a,lscut_a): #切ってもダメかチェック
    ct_a = 0
    for i in grp_a:
        ct_a += s[i][lscut_a]
    if(ct_a > k):
        return False
    else:
        return True

min_cut = h + w - 2
hol = [0]*(h-1)
for i in range(2**(h-1)):
    fl_ag = 0
    lastcut = 0
    cuts = 0 #切る回数
    groups = gru_hol(hol) #groupsを作る
    for j in range(1,w):
        flag = 0
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == False):
                    fl_ag = 1 #groupからやり直し
                    break
                else:
                    flag = 1
        if(fl_ag == 1):
            break
        if(flag == 1):
            cuts += 1
            lastcut = j

    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    line = [0]*(W+1)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        white_chocolate = [ line.copy() for _ in range(group_number+1) ]
        for i in loop_W:
            for g in range(group_number+1):
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ list(map(int, list(input()[:-1]))) for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        white_chocolate = [ [0]*(W+1) for _ in range(group_number+1) ]
        for i in loop_W:
            for g in range(group_number+1):
                for j in group[g]:
                    white_chocolate[g][i] += chocolate[j][i]
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [input()[:-1] for _ in range(H)]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # グループごと白チョコを数える
        white_chocolate = [ [0]*(W+1) for _ in range(group_number+1) ]
        for i in loop_W:
            for g in range(group_number+1):
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(white_chocolate)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(white_chocolate)):
                if white_chocolate[g][w] > K:
                    cut = INF
                    break
                else:
                    now[g] += white_chocolate[g][w]
                if now[g] + white_chocolate[g][w+1] > K:
                    cut += 1
                    now = zeros.copy()
                    break
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

h, w, K = map(int, input().split())
choco = []

for i in range(h):
  li = list(map(int, list(input())))
  choco.append(li)

ans = 10**4*10*10
for i in range(2**(h-1)):
  score = 0
  newChoco = copy.deepcopy(choco)
  for j in reversed(range(h-1)):
    if (i>>j)&1:
      newChoco[j] = list(np.array(newChoco[j]) + np.array(newChoco[j+1]))
      newChoco.pop(j+1)
    else:
      score += 1
  cnts = np.array([0]*len(newChoco))
  for k in range(w):
    cntsNow = np.array([0]*len(newChoco))
    for j in range(len(newChoco)):
      cntsNow[j] = newChoco[j][k]
    if max(cntsNow)>K:
      score += 9999999
      break
    elif max(cnts+cntsNow)<=K:
      cnts += cntsNow
    else:
      cnts = cntsNow
      score += 1
  ans = min(ans, score)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np
h, w, K = map(int, input().split())
chocolate = np.array([list(map(int, input())) for _ in range(h)])

a = 10**10
for i in range(1 << (h-1)):

    cnt = 0
    group = []
    for j in range(h):
        group.append(cnt)
        if i & (1 << j):
            cnt += 1

    d = np.zeros((cnt+1, w))
    for j in range(h):
        d[group[j]] += chocolate[j]

    check = np.zeros(cnt+1)
    flg = False
    ans = 0
    for j in range(w):
        if not all(check <= K):
            flg = True
            break
        check += d[:, j]
        if not all(check <= K):
            ans += 1
            check = d[:, j]

    if flg:
        continue

    a = min(a, ans+cnt)

print(a)

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;t=j=w;r,*d=[0]*w
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j,i=j,j+(t>j),h
 m+=r+c,
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;j-=t<j;t=j;i=h
 m+=r+c,
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;j-=t<j;t=j;i=h
 m+=r+c,
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;j-=1;i=h
 m+=r+c,
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print(min(m))

Submission status: Time Limit Exceeded

Solution code:
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):z=i>>j&1;t+=[j+1]*z;l+=z
 t+=h,
 c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if g<1:m=min(m,v+l)
print(m)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

INF = 1 << 60
H, W, K = nm()
grid = []
for i in range(H):
    row = ns()
    assert len(row) == W
    grid.append(row)


def min_vsplits(ranges):
    vsplits = 0
    block_count = [0] * len(ranges)
    for c in range(W):
        line_count = [0] * len(ranges)
        for i, (start, end) in enumerate(ranges):
            for r in range(start, end):
                if grid[r][c] == "1":
                    line_count[i] += 1
                    block_count[i] += 1
        if max(line_count) > K:
            return INF  # one column contains more than K.
        if max(block_count) > K:
            vsplits += 1
            for i in range(len(block_count)):
                block_count[i] = line_count[i]
    return vsplits


def solve():
    S = 1 << (H - 1)
    min_splits = (H - 1) * (W - 1)  # split all
    for splits in range(S):
        ranges = []
        start = 0
        stop = 1
        while splits:
            if splits & 1:
                ranges.append((start, stop))
                start = stop
            splits >>= 1
            stop += 1
        ranges.append((start, H))
        hsplits = len(ranges) - 1
        vsplits = min_vsplits(ranges)
        s = hsplits + vsplits
        if min_splits > s:
            min_splits = s
    return min_splits


print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np
#import math
#from fractions import Fraction
#import itertools
#import heapq

h,w,k=map(int,input().split())
s = [list(map(int, input())) for _ in range(h)]
res=0
ans=10**9
for i in range(2**(h-1)):
    p=1
    partation=[-1]*(h-1)

    for j in range(h-1):
        if i &(1<<j):
            partation[j]=1
            p+=1
    g=[0]*p
    res=0
    l=0
    while l<w:
        m=0
        for j in range(h):
            g[m]+=s[j][l]
            if g[m]>k:
                res+=1
                g=[0]*p
                break
            if j<h-1 and partation[j]==1:
                m+=1
        else:
            l+=1
    res+=p-1
    if res<ans:
        ans=res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


tdiv=2**(h-1)
import numpy as np
s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    tmp=np.zeros(w)
    tmp+=s[0,:]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            tmp+=s[j+1,:]
        else:
            lis.append(tmp)
            tmp=np.zeros(w)
            tmp+=s[j+1,:]
            cnt+=1
    lis.append(tmp)
    lis = np.array(lis)
    clis=np.zeros(cnt+1)
    #print(lis,cnt)
    for ind in range(w):
        #if lis[:,ind].max()>k:
        #    cnt=10010010
        #    break
        clis+=lis[:,ind]
        if clis.max()>k:
            clis=lis[:,ind]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


tdiv=2**(h-1)
import numpy as np
s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    tmp=np.zeros(w)
    tmp+=s[0,:]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            tmp+=s[j+1,:]
        else:
            lis.append(tmp)
            tmp=np.zeros(w)
            tmp+=s[j+1,:]
            cnt+=1
    lis.append(tmp)
    lis = np.array(lis)
    clis=np.zeros(cnt+1)
    #print(lis,cnt)
    for ind in range(w):
        if lis[:,ind].max()>k:
            cnt=10010010
            break
        clis+=lis[:,ind]
        if clis.max()>k:
            clis=lis[:,ind]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


tdiv=2**(h-1)
import numpy as np
s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    tmp=np.copy(s[0,:])
    cnt = 0
    #print(s)
    for j in range(h-1):
        if (i>>j&1):
            tmp+=s[j+1,:]
        else:
            lis.append(tmp)
            tmp=np.copy(s[j+1,:])
            cnt+=1
    lis.append(tmp)
    lis = np.array(lis)
    clis=np.zeros(cnt+1)
    #print(lis,cnt)
    for ind in range(w):
        if lis[:,ind].max()>k:
            cnt=10010010
            break
        clis+=lis[:,ind]
        if clis.max()>k:
            clis=lis[:,ind]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Time Limit Exceeded

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


def add(j):
    for i in range(g):
        now[i] += c[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True


ans = 10**30
for i in range(2 ** (H-1)):
    g = 0
    id = [-1]*H
    for j in range(H):  # このループが一番のポイント
        id[j] = g
        if (i >> j & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            g += 1
    g += 1

    c = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += S[i][j]

    num = g-1
    now = [0]*g
    for j in range(W):
        if not add(j):
            num += 1
            now = [0]*g
            if not add(j):
                num = 10**30
                continue

    ans = min(ans, num)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    ret = float('inf')
    for w in range(1, W):
        S[:,w] += S[:,w-1]
    for h in range(1, H):
        S[h,:] += S[h-1,:]

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1, r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i]-1, r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i+1]-1, l-1]
                else:
                    cri = S[idxes[i+1]-1, r-1] - S[idxes[i]-1, r-1] - S[idxes[i+1]-1, l-1] + S[idxes[i]-1, l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()