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:
def main():
  H, W, K = map(int, input().split())
  #H , W, K = 10, 1000, 5000
  S = []
  for _ in range(H):
    S.append(input())
  #for k in range(H):
    #S.append('0'*(W- len(bin(k))+2)+str(bin(k))[2:])
  hsummation = [[int(S[0][k])]for k in range(W)]
  for k in range(W):
    for j in range(1, H):
      hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
  for k in range(W):
    hsummation[k] = [0] + hsummation[k]
  #print(hsummation)
  ans = float('inf')
  anskouho = 0
  h = -1
  for j in range(2**(H-1)):
    h += 1
    binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
    hlist=[]
    for k in range(H-1):
      if binh[-k-1] == '1':
        hlist.append(k)
    hlist = [0] + hlist + [-1]
    #print(hlist)
    anskouho = len(hlist)-2
    now = 0
    while now < W:
      counter = [0 for _ in range(len(hlist)-1)]
      while now < W:
        for l in range(1, len(hlist)):
          counter[l-1] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
        if max(counter) > K:
          anskouho += 1
          break
        else:
          now += 1
      if anskouho > ans:
        break
    else:
      ans = min(ans, anskouho)

        #print(counter)
  #print(anskouho)
  print(ans)


main()

Submission status: Wrong Answer

Solution code:
from itertools import product
H,W,K = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {i:[0 for _ in range(W+1)] for i in range(H)}
for i in range(H):
    for j in range(1,W+1):
        C[i][j] = C[i][j-1]+int(S[i][j-1])
cmin = (H-1)*(W-1)
for x in product((0,1),repeat=H-1):
    A = []
    cur = 0
    for i in range(H-1):
        if x[i]==1:
            A.append(list(range(cur,i+1)))
            cur = i+1
    A.append(list(range(cur,H)))
#     print("A={}".format(A))
    cur = 0
    cnt = 0
#     ind = 0
    for j in range(1,W+1):
        flag = 0
        for a in A:
            tot = 0
            for i in a:
                tot += C[i][j]-C[i][cur]
            if tot<=K:continue
            else:
                flag = 1
                break
        if flag==1:
            cnt += 1
            cur = j-1
    cmin = min(cmin,cnt+sum(x))
#     print("cmin={},x={}".format(cmin,x))
print(cmin)

Submission status: Wrong Answer

Solution code:
import collections

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

ans = float("inf")


for i in range(2 ** (H - 1)):
    bundan = {}
    bundan[0] = 0
    prev = 0
    tmp = 0
    for j in range(H - 1):
        if i >> j & 1 == 1:
            prev += 1
            bundan[j + 1] = prev
            tmp += 1
        else:
            bundan[j + 1] = prev

    c = collections.Counter()
    for kk in range(W):
        f = False
        for k in range(H):
            if f:
                break
            if S[k][kk] == '1':
                c[bundan[k]] += 1
                if c[bundan[k]] > K:
                    tmp += 1
                    f = True
                    c = collections.Counter()
                    for kkk in range(H):
                        if S[kkk][kk] == '1':
                            c[bundan[kkk]] += 1
                    break

    ans = min(ans, tmp)


print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
H, W, K = [int(_) for _ in input().split()]
S = np.array(
    [[0] * (W + 1)] + [[0] + list(map(int, input())) for _ in range(H)],
    dtype=np.int64)
cum = S.cumsum(axis=0).cumsum(axis=1)
ans = 10**10
for h in range(H):
    for c in itertools.combinations(range(1, H), h):
        I = np.array([0] + list(c) + [H], dtype=int)
        cum2 = np.diff(cum[I, :], axis=0)
        j = 0
        i = 0
        cnt = h
        while True:
            iold = i
            i += 1
            if i > W:
                break
            if np.max(cum2[:, i] - cum2[:, j]) > K:
                j = i = i - 1
                cnt += 1
            if iold == i:
                cnt = 10**10
                break
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

min_split = 10**10

for i in range(2**(h-1)):
    li = []

    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = [0]*w
    total = []

    for l in range(h):
        for m in range(w):
            lin[m] += s[l][m]
        if l in li:
            total.append(lin)
            lin = [0]*w
    now = 0
    t = len(total)
    count = t-1

    for n in range(t):
        total[n] = [0]+list(accumulate(total[n]))
    for o in range(1,w+1):
        for p in range(t):
            if total[p][o]-total[p][now] > k:
                now = o-1
                count += 1
                break

    min_split = min(min_split,count)

print(min_split)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

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

min_split = 10**10

for i in range(2**(h-1)):
    li = []
    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = [0]*w
    total = []
    for l in range(h):
        for m in range(w):
            lin[m] += s[l][m]
        if l in li:
            total.append(lin)
            lin = [0]*w
    now = 0
    t = len(total)
    count = t-1
    for n in range(t):
        total[n] = list(accumulate(total[n]))
    for o in range(w):
        for p in range(t):
            if total[p][o]-total[p][now] > k:
                now = o
                count += 1
                break
    min_split = min(min_split,count)

print(min_split)

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import numpy as np

h,w,k = map(int,input().split())
s = [list(map(int,"".join(input()))) for _ in range(h)]
s = np.array(s,dtype=np.int64)

min_split = 10**10

for i in range(2**(h-1)):
    li = []

    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = np.zeros(w,dtype=np.int64)
    total = []

    for l in range(h):
        lin += s[l]
        if l in li:
            total.append(lin)
            lin = np.zeros(w,dtype=np.int64)
    total = np.array(total,dtype=np.int64).tolist()
    check = [0 for _ in range(len(total))]
    count = len(total)-1

    for yoko in range(w):
        for tate in range(len(total)):
            check[tate] += total[tate][yoko]
        for nakami in check:
            if nakami >= k+1:
                check = [0 for _ in range(len(total))]
                count += 1
                for tate in range(len(total)):
                    check[tate] += total[tate][yoko]
            continue
    min_split = min(min_split,count)
    
print(min_split)

Submission status: Wrong Answer

Solution code:
from numba import njit
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]


def solve(H, W, K, S):
    cum = S.cumsum(axis=0).cumsum(axis=1)
    #sum(a,b -> x,y) (1-indexed)
    #cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
    ans = 10**10
    for bs in itertools.product([True, False], repeat=H - 1):
        bs = [True] + list(bs) + [True]
        idxs = []
        for i, b in enumerate(bs):
            if b:
                idxs += [i]
        cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
        i = 0
        cnt = sum(bs) - 3
        f = True
        while i < W:
            i2 = min(np.searchsorted(c, K + c[i], side='right') for c in cum2)
            if i2 == i:
                f = False
                break
            i = i2
            cnt += 1
        if f:
            ans = min(ans, cnt)
    print(ans)


solve(H, W, K, S)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
#sum(a,b -> x,y) (1-indexed)
#cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        i = min(np.searchsorted(c, K + c[i], side='right') for c in cum2)
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = int(1e15)
    for i in range(1 << (H - 1)):
        cut = 0
        L = [0 for _ in range(H)]
        t = 0
        for j in range(H - 1):
            L[j] = t
            if i >> j & 1:
                cut += 1
                t += 1
        L[-1] = t
        isOK = True
        cnt = [0 for _ in range(H)]
        for w in range(W):
            row = [0 for _ in range(H)]
            for h in range(H):
                if S[h][w] == '1':
                    row[L[h]] += 1
            flag = True
            for h in range(H):
                if row[h] + cnt[h] > K:
                    flag = False
                if row[h] > K:
                    isOK = False
            if not isOK:
                break
            if not flag:
                cnt = [0 for _ in range(H)]
                cut += 1
            for h in range(H):
                cnt[h] += row[h]
        ans = min(ans, cut)
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


H, W, K = 0, 0, 0
S = None
L = None
isOK = False

INF = int(1e15)


def func(h1, h2):
    global L, isOK
    cnt = 0
    for w in range(W):
        line = 0
        for h in range(h1, h2 + 1):
            if S[h][w] == '1':
                line += 1
        if line > K:
            isOK = False
            return
        if w + 1 in L:
            cnt = line
            continue
        if cnt + line > K:
            L.append(w)
            cnt = 0
        cnt += line
    return


def solve():
    global H, W, K, S, L, isOK
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = INF

    for i in range(1 << (H - 1)):
        pop_cnt = 0
        rem = 0
        L = []
        isOK = True
        for j in range(H - 1):
            if i >> j & 1:
                func(rem, j)
                rem = j + 1
                pop_cnt += 1
        func(rem, H - 1)
        if isOK:
            ans = min(ans, len(L) + pop_cnt)
        # print(len(L) + pop_cnt)
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

INF = 10000

ans = INF
for bit in range(1 << (h - 1)):

    # 横線でグループ化
    id = [0] * h
    group_idx = 0
    for i in range(h):
        id[i] = group_idx
        if (bit >> i) & 1:
            group_idx += 1

    group_num = group_idx + 1
    cnt = [[0] * w for _ in range(group_num)]
    for i in range(h):
        for j in range(w):
            cnt[id[i]][j] += int(s[i][j])

    # グループ化した際に、1列でkを超えてるならこの縦の区切り方はそもそも無理
    flag = True
    for g in range(group_num):
        for j in range(w):
            if cnt[g][j] > k:
                flag = False
    if not flag:
        continue

    divnum = group_num - 1
    now = [0] * group_num
    cur = 0
    while cur < w:
        for g in range(group_num):
            now[g] += cnt[g][cur]
            if now[g] > k:
                divnum += 1
                now = [0] * group_num
                cur -= 1
                break
        cur += 1
    print(divnum)
    ans = min(ans, divnum)

print(ans)

Submission status: Wrong Answer

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

INF = 10000

ans = INF
for bit in range(1 << (h - 1)):

    # 横線でグループ化
    id = [0] * h
    group_idx = 0
    for i in range(h):
        id[i] = group_idx
        if (bit >> i) & 1:
            group_idx += 1

    group_num = group_idx + 1
    cnt = [[0] * w for _ in range(group_num)]
    for i in range(h):
        for j in range(w):
            cnt[id[i]][j] += int(s[i][j])

    # グループ化した際に、1列でkを超えてるならこの縦の区切り方はそもそも無理
    flag = True
    for g in range(group_num):
        for j in range(w):
            if cnt[g][j] > k:
                flag = False
    if not flag:
        continue

    divnum = group_num - 1
    now = [0] * group_num
    cur = 0
    while cur < w:
        for g in range(group_num):
            now[g] += cnt[g][cur]
            if now[g] > k:
                divnum += 1
                now = [0] * group_num
                cur -= 1
        cur += 1

    ans = min(ans, divnum)

print(ans)

Submission status: Wrong Answer

Solution code:
# E - Dividing Chocolate
import sys
sys.setrecursionlimit(10000)

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

def check(border, num):
    global H,W,K,S
    now = [0]*(num+1)
    add = 0
    for j in range(W):
        tmp = [0]*(num+1)
        for i in range(H):
            now[border[i]] += int(S[i][j])
            tmp[border[i]] += int(S[i][j])
        if max(now)>K:
            add += 1
            now = tmp
    return num+add

def rec(border, num, i):
    global H,W,K,S,ans
    if i<H:
        border[i] = num
        rec(border, num, i+1)
        border[i] = num+1
        rec(border, num+1, i+1)
    else:
        ans = min(ans, check(border, num))

rec([0]*H, 0, 1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = mat[0].count("1") - 1
        print(max(0, tmp // k))
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = mat[0].count("1")
        print(tmp // k if tmp % k else max(0, tmp // k - 1))
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = mat[0].count("1")
        print(tmp // k if tmp % k else tmp // k - 1)
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = mat[0].count("1")
        print(tmp // k + 1 if tmp % k else tmp // k)
        exit(0)

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        print(mat[0].count("1")//k)
        exit(0)

    ans = INF
    for i in range(2 ** (h-1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    ans = INF
    for i in range(2 ** (h-1)):
        cut = format(i, "b").count("1")
        row = h - (h - cut) + 1
        if row == 0:
            continue

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1 == 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  for a in range(w):
    for b in range(len(c)):
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  cr=[]
  for cc in c:
    cr.append(cc[::-1])
  cr_mx=[0]*len(c)
  t_cnt2=0
  for a in range(w):
    for b in range(len(cr)):
      cr_mx[b]+=cr[b][a]
      if cr_mx[b]>K:
        t_cnt2+=1
        cr_mx=[0]*len(cr)
        for b in range(len(cr)):
          cr_mx[b]+=cr[b][a]
        break
  ans=min(ans,t_cnt+t_cnt1,t_cnt+t_cnt2)
  # ans=min(ans,t_cnt+t_cnt1)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  for a in range(w):
    for b in range(len(c)):
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  ans=min(ans,t_cnt+t_cnt1)
print(ans)

Submission status: Wrong Answer

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

ans = 100000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for l in range(H):
        div[group[l]] += S[l][0]
    for j in range(W-1):
        for k in range(H):
            if div[group[k]] + S[k][j+1] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j+1]
                break
            else:
                div[group[k]] += S[k][j+1]
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

ans = 10000
for i in range(2**H):
    cnt = 0
    temp = i
    group = [0]*H
    for j in range(H):
        group[j] = cnt
        if temp & 1:
            cnt += 1
        temp >>= 1
    div = [0]*H
    for l in range(H):
        div[group[l]] += S[l][0]
    for j in range(W-1):
        for k in range(H):
            if div[group[k]] + S[k][j+1] > K:
                cnt += 1
                div = [0]*H
                for l in range(H):
                    div[group[l]] += S[l][j+1]
                break
            else:
                div[group[k]] += S[k][j+1]
    ans = min(ans, cnt)
print(ans)