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: Wrong Answer

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)]
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][w+1]

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

    cut += len(yoko) - 1
    # tate
    # print(yoko)
    yoko = yoko + [H]
    cnt = [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:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        # print('ncnt', ncnt)
        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt[:]
                break
        # print('cnt', cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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)]
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**18
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    # print(yoko)
    yoko = yoko + [H]
    cnt = [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:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        # print('ncnt', ncnt)
        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt[:]
                break
        # print('cnt', cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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)]
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**18
for i in range(2**n):
    cut = 0
    # print('i:', i)
    yoko = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    # print(yoko)
    yoko = yoko + [H]
    cnt = [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:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        # print('ncnt', ncnt)
        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt.copy()
                break
        # print('cnt', cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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)]
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 = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    # print(yoko)
    yoko = yoko + [H]
    cnt = [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:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]
        # print('ncnt', ncnt)
        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt.copy()
                break
        # print('cnt', cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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 copy, 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 = [0]
    for j in range(n):
        if ((i>>j) & 1):
            yoko.append(j+1)

    cut += len(yoko) - 1
    # tate
    yoko = yoko + [H]
    cnt = [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:])):
            ncnt[k] = cumS[y2][j+1] - cumS[y1][j+1]

        for ind, nc in enu(ncnt):
            cnt[ind] += nc
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt
                break
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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))
    cnt = [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)
        for ind, nc in enu(ncnt):
            cnt[ind] += ncnt[ind]
            if K < cnt[ind]:
                cut += 1
                cnt = ncnt.copy()
                break
    #     print(cnt)
    # print(cut)
    cut_min = min(cut_min, cut)
print(cut_min)

Submission status: Wrong Answer

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
    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] = 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: Wrong Answer

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
        # 縦に切っていく
        cut = group_number
        zeros = [0] * (group_number + 1)
        now = zeros.copy()
        for w in loop_W:
            for g in range(len(group)):
                cnt = 0
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        cnt += 1
                if cnt > K:
                    cut = INF
                    break
                if now[g] + cnt > K:
                    cut += 1
                    now = zeros.copy()
                    break
                now[g] += cnt
            if cut == INF:
                break
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

Submission status: Wrong Answer

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)
    white_chocolate = [ [0]*(W+1) for _ in range(10) ]
    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
        # グループごと白チョコを数える
        for i in loop_W:
            for g in range(group_number+1):
                white_chocolate[g][i] = 0
                for j in group[g]:
                    if chocolate[j][i] == '1':
                        white_chocolate[g][i] += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * (10)
        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: Wrong Answer

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 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: Wrong Answer

Solution code:
h, w, k = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = 0
if h == 1:
    cnt = 0
    for i in range(w):
        if s[0][i] == '1':
            cnt += 1
        if cnt > k:
            ans += 1
            cnt -= k
    print(ans)
    exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False

    d.append(False)
    val = 0
    for i in range(len(d)):
        if d[i] == True:
            val += 1
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []
    lis2 = [0] * len(lis)
    flg = True
    flg2 = True
    cnt = [0] * len(lis)
    for i in range(h):
        for j in range(len(lis)):
            cnt2 = [0] * len(lis)
            for k in lis[j]:
                if s[i][k] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
                    if cnt[j] > k:
                        flg2 = False
            if cnt2[j] > k:
                flg = False
        if flg2 == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg2 = True
            val += 1
    if flg == True:
        ans = max(ans,val)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = 0
if h == 1:
    cnt = 0
    for i in range(w):
        if s[0][1] == '1':
            cnt += 1
        if cnt > k:
            ans += 1
            cnt -= k
        print(ans)
        exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False

    d.append(False)
    val = 0
    for i in range(len(d)):
        if d[i] == True:
            val += 1
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []
    lis2 = [0] * len(lis)
    flg = True
    flg2 = True
    cnt = [0] * len(lis)
    for i in range(h):
        for j in range(len(lis)):
            cnt2 = [0] * len(lis)
            for k in lis[j]:
                if s[i][k] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
                    if cnt[j] > k:
                        flg2 = False
            if cnt2[j] > k:
                flg = False
        if flg2 == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg2 = True
            val += 1
    if flg == True:
        ans = max(ans,val)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = 0
if h == 1:
    cnt = 0
    for i in range(w):
        if s[0][1] == '1':
            cnt += 1
        if cnt > k:
            ans += 1
            cnt -= k
        print(ans)
        exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False

    d.append(False)
    val = 0
    for i in range(len(d)):
        if d[i] == True:
            val += 1
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []
    lis2 = [0] * len(lis)
    flg = True
    flg2 = True
    for i in range(h):
        cnt = [0] * len(lis)
        for j in range(len(lis)):
            cnt2 = [0] * len(lis)
            for k in lis[j]:
                if s[i][k] == '1':
                    cnt[j] += 1
                    cnt2[j] += 1
                    if cnt[j] > k:
                        flg2 = False
            if cnt2[j] > k:
                flg = False
        if flg2 == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg2 = True
            val += 1
    if flg == True:
        ans = max(ans,val)
print(ans)

Submission status: Wrong Answer

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

ans = 10**15

for div in range(1<<(H-1)):
  g = 0
  id = [None] * (H)

  # 列をgroup分け
  for i in range(H):
    id[i] = g
    if (div>>i)&1: g += 1

  # groupごとにwhite chocolateが何個あるのか
  c = [ [0]*W for _ in range(g+1) ]
  for i,block in zip(id, chocolate):
    for j,b in enumerate(block):
      if b == "1":
        c[i][j] += 1

  # indexごとにwhite chocolateを求めて、もしKを超えたら0に初期化
  now = [0] * (g+1)
  lines = g
  for j in range(W):
    for i in range(g+1):
      now[i] += c[i][j]

    ok = all( n<=K for n in now )
    if not ok:
      lines += 1
      now = [0] * (g+1)
      for i in range(g+1):
        now[i] += c[i][j]

  ans = min(ans, lines)

print(ans)

Submission status: Wrong Answer

Solution code:
ans = 10**6
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    

for bit in range(2**(H-1)):
    # 先に横に割る
    # 横方向に割ったあとの、縦の和のリストを作る
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
    # そもそも可能かどうか
    possible = True
    
    #　縦方向に何回割ったか
    count = 0
    
    #最後に割ったところ
    laststop = -1
    for stop in range(0,W):
        #左からどん欲に考える
        
        each_ok = True
        for row in new_choco:
            if sum(row[laststop+1:stop+1]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop+1
        else:
            if laststop+1==stop:
                possible = False
                break
            else:
                laststop = stop
                count += 1
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Wrong Answer

Solution code:
ans = 10**4
H,W,K = map(int,input().split())
chocolate = []
for _ in range(H):
    chocolate.append(list(map(int,input())))
    

for bit in range(2**(H-1)):
    # 先に横に割る
    # 横方向に割ったあとの、縦の和のリストを作る
    i = 0
    new_choco = []
    new_choco.append(chocolate[0])
    for each_bit in range(H-1):
        if((bit>>each_bit)&1):
            i += 1
            new_choco.append(chocolate[each_bit+1])
        else:
            new_choco[i] = [new_choco[i][j]+chocolate[each_bit+1][j] for j in range(W)]
    # そもそも可能かどうか
    possible = True
    
    #　縦方向に何回割ったか
    count = 0
    
    #最後に割ったところ
    laststop = -1
    for stop in range(0,W):
        #左からどん欲に考える
        
        each_ok = True
        for row in new_choco:
            if sum(row[laststop+1:stop+1]) > K:
                each_ok = False
                break
        if each_ok:
            maxstop = stop+1
        else:
            if laststop+1==stop:
                possible = False
                break
            else:
                laststop = stop
                count += 1
    if possible:
        tmpans = (bin(bit).count('1')+count)
        ans = tmpans if ans > tmpans else ans
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
def split(word): 
    return [char for char in word]  
      
m=[]
for i in range(h):
  m.append(input())
t=[0]*(h-1)
ans=w-1+h-1
for i in range(2**(h-1)):
  s=split("{0:b}".format(i))
  s.reverse()
  for j in range(h-1-len(s)):
    s.append('0')
  s.reverse()
  a=[]
  a.append([])
  for j in range(w):
    a[0].append(int(m[0][j]))
  for j in range(1,h):
    if s[j-1]=='0':
      for l in range(w):
        a[-1][l]+=int(m[j][l])
    else:
      a.append([])
      for l in range(w):
        a[-1].append(int(m[j][l]))
  n=len(a)
  tmp=0
  p=[0]*n
  flag=0
  for j in range(w):
    for l in range(n):
      if p[l]+a[l][j]>k:
        flag=1
        break
    if flag==1:
      tmp+=1
      flag=0
      for t in range(n):
        p[t]=0
    for l in range(n):
      p[l]+=a[l][j]
  if n-1+tmp<ans:
    ans=n-1+tmp
print(ans)

Submission status: Wrong Answer

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 = []
    group = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups.append(group)
            group = [i+1]
        else:
            group.append(i+1)
    groups.append(group)
    return groups

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(group,lastcut,nextcut): #groupのlastcut~nextcutのホワイトチョコを数える
    count = 0
    for i in group:
        for j in range(lastcut,nextcut):
            count += s[i][j]
    return count

def cutcheck(group,lastcut): #切ってもダメかチェック
    count = 0
    for i in group:
        count += s[i][lastcut]
    if(count > 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):
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == True):
                    cuts += 1
                    lastcut = j
                    break
                else:
                    fl_ag = 1 #groupからやり直し
                    break
        if(fl_ag == 1):
            break
    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

Submission status: Wrong Answer

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


ans = 10**8
for i in range(2 ** (H-1)):
    fail_flag = False
    comb = []
    for j in range(H-1):
        if ((i >> j) & 1): 
            comb.append(j)
    comb.append(H-1)
    # print(comb)
    sections = []
    for k in range(0,len(comb)):
        if k == 0:
            sections.append( sl[0:comb[0]+1] )
        else:
            sections.append( sl[comb[k-1]+1:comb[k]+1] )
    # print(sections)

    partition_cnt = 0
    sections_w_cnts = [0]*len(sections)
    for w in range(W):
        sections_curr_w_cnts = [0]*len(sections)
        partition_flag = False
        for i, sec in enumerate(sections):
            for row in sec:
                if row[w] == '1':
                    sections_curr_w_cnts[i] += 1
                    sections_w_cnts[i] += 1
                    if sections_curr_w_cnts[i] > K:
                        fail_flag = True
                        break
                    if sections_w_cnts[i] > K:
                        partition_flag = True
            if fail_flag: break
        if fail_flag: break

        if partition_flag:
            sections_w_cnts[:] = sections_curr_w_cnts[:]
            partition_cnt += 1
        
    ans = min(len(comb)-1+partition_cnt, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
ch1 = [input() for i in range(h)]
ch =[[0]*w for i in range(h)]
d = [list(map(int,bin(x)[2:].zfill(h-1))) for x in range(2**(h-1))]

for i in range(h):
    ch[i][0]=int(ch1[i][0])

for i in range(h):
    for j in range(1,w):
        ch[i][j]=int(ch1[i][j])+ch[i][j-1]
mi = float('inf')
for i in d:
    cut=[0]*h
    ans = 0
    i = i+[2]
    for j in range(w):
        stock=[0]*h
        for l in range(h):
            stock[l]+=ch[l][j]-cut[l]
            if i[l]==0:
                stock[l+1]+=stock[l]
        if max(stock)>k:
            ans +=1
            for l2 in range(h):
                cut[l2]+=ch[l2][j-1]
    ans += sum(i)-2
    mi = min(mi,ans)
print(mi)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w,k = mi()

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

def cc(i,j):
    return int(s[i][j])

mincut = 10**6
for i in range(2**(h-1)):
    # print(bin(i))
    tcut = 0
    # 横割りぶん
    hc = [0] * (h) #横カットの位置
    for j in range(9):
        if i>>j &1:
            hc[j] = 1
    tcut += sum(hc)
    
    # 縦割り分
    hb = [0] * h
    for j in range(w):
        # print('w',j)
        thb = [0] * h
        idx = 0
        for kk in range(h):
            thb[idx] += cc(kk,j)
            if hc[kk] == 1:
                idx += 1
        # print(hb,thb)

        if max(thb) > k:
            break

        for kk in range(h):
            hb[kk] += thb[kk]

        if max(hb) > k:
            # print('cut!!')
            tcut += 1
            hb = thb

    # print(tcut)
    mincut = min(mincut, tcut)

print(mincut)

Submission status: Wrong Answer

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w,k = mi()

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

def cc(i,j):
    return int(s[i][j])

mincut = 10**6
for i in range(2**(h-1)):
    # print(bin(i))
    tcut = 0
    # 横割りぶん
    hc = [0] * (h)
    for j in range(9):
        if i>>j &1:
            hc[j] = 1
    tcut += sum(hc)
    
    # 縦割り分
    hb = [0] * h
    for j in range(w):
        # print('w',j)
        thb = [0] * h
        idx = 0
        for kk in range(h):
            thb[idx] += cc(kk,j)
            if hc[kk] == 1:
                idx += 1
        # print(hb,thb)

        for kk in range(h):
            hb[kk] += thb[kk]

        if max(hb) > k:
            # print('cut!!')
            tcut += 1
            hb = thb

    # print(tcut)
    mincut = min(mincut, tcut)

print(mincut)

Submission status: Wrong Answer

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 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=j,j+(t<j);i=h
 m+=r+c,
print(min(m))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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;t=j;j-=t<j;i=h
 m+=r+c,
print(min(m))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
  while h-i:d[c]+=s[i][j]>'0';r+=h*w*(d[c]>k);c+=b>>i&1;i+=1
  j+=1
 m+=r+c,
print(min(m))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(9**9)
x,*s=open(0)
h,w,k=map(int,x.split())
p=lambda b:b and(b&1)+p(b>>1)
g=lambda b,j,t,d,i=0,c=0:j==w and~p(b)or i==h and g(b,j+1,t,d)or d.__setitem__(c,d[c]+int(s[i][j]))or d[c]>k and(t<j and-1+g(b,j,j,[0]*h)or h*w)or g(b,j,t,d,i+1,c+(b>>i&1))
print(min(~g(b,0,0,[0]*h)for b in range(512)))