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:
h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for _ in range(h)]
ans = (h-1)*(w-1)
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s_ = [int(i) for i in input()]
    s.append(s_)
ans = float("INF")
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: continue
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s_ = [int(i) for i in input()]
    s.append(s_)
ans = float("INF")
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    if flag: break
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = []
for _ in range(h):
    s_ = [int(i) for i in input()]
    s.append(s_)
ans = float("INF")
for i in range(2**(h-1)):
    d = [(i >> j) & 1 for j in range(h-1)]
    count, count_tmp = [0]*(sum(d)+1), [0]*(sum(d)+1)
    ans_, res = 0, 0
    flag = False
    for w_ in range(w):
        count[0] += s[0][w_]
        count_tmp[0] += s[0][w_]
        res += 1
        tmp = 0
        for h_ in range(1, h):
            if d[h_-1]: tmp += 1
            if s[h_][w_]:
                count[tmp] += 1
                count_tmp[tmp] += 1
        for j in count:
            if j > k:
                if res==1:
                    flag = True
                    break
                else:
                    for idx in range(sum(d)+1):
                        count[idx] = count_tmp[idx]
                    ans_ += 1
                    res = 0
                    break
        if flag: break
        count_tmp = [0]*(sum(d)+1)
    ans_ += sum(d)
    ans = min(ans, ans_)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

H,W,K = inputIL()
C = inputSLs(H)


best = INF
for h in range(pow(2,H-1)):
  nC = []
  nC.append([int(i) for i in C[0]])
  for i in range(1,H):
    if h>>(i-1) & 1:
      for j in range(W):
        nC[-1][j] += int(C[i][j])
    else:
      nC.append([int(j) for j in C[i]])
  n = len(nC)
  count = [0 for j in range(n)]
  cut = 0
  while len(nC[0]):
    now = [nC[j].pop() for j in range(n)]
    if max(count[j]+now[j] for j in range(n)) > K:
      count = now
      cut += 1
    else:
      count = [count[j]+now[j] for j in range(n)]
  
  yoko = H-1
  while h:
    h &= h -1
    yoko -= 1
  best = min(best,cut+yoko)

print(best)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

h, w, k = inpl()
s = [input()[:-1] for _ in range(h)]
ans = 10 ** 4
for t in itertools.product([0, 1], repeat=h-1):
    cnt = t.count(1)
    tmp = s[0]
    SW = []  # 縦方向に圧縮したマップを格納
    tmp = [int(s) for s in s[0]] # tmp[j]=横方向に切ったブロックのj列目の総和
    for i, c in enumerate(t):
        if c: #横に切る
            SW.append(tmp) # SWが確定する
            tmp = [int(s) for s in s[i + 1]] # 次弾装填
        else:
            tmp = [tmp[j] + int(s[i + 1][j]) for j in range(w)]
    SW.append(tmp)
    new_h = len(SW)  #圧縮後の高さ
    sums = [0] * new_h
    print(SW)
    if max(itertools.chain.from_iterable(SW)) > k:
        # itertools.chain.from_iterable([[A,B],[C,D]]) -> A,B,C,D
        # 各マスの時点でダメだったらこの横の切り方ではだめ
        continue
    for j in range(w):
        sumtmp = [sums[i] + SW[i][j] for i in range(new_h)]
        if max(sumtmp) > k:
            # 左から足してみてどこかがkを超えるようなら切る
            cnt += 1
            sums = [SW[i][j] for i in range(new_h)]  #新しいSW[i][j]で上書き
        else:
            sums = sumtmp
    ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = (H - 1) * (W - 1)
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons)
        if result > 0 and result < answer:
            answer = result
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons):
    answer = sum(horizons)
    # greedyに縦線を引いていく
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    left = 0
    right = 0
    partial_sums = [0] * len(S2)
    while right <= W - 1:
        if not satisfy(K, S2, partial_sums):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
            partial_sums = [0] * len(S2)
        else:
            right += 1
    return answer

def satisfy(K, S2, partial_sums):
    result = True
    for idx, row in enumerate(S2):
        partial_sums[idx] += row[idx]
        if partial_sums[idx] > K:
            result = False
    return result

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(S2, partial_sums):
    global K
    for idx, row in enumerate(S2):
        partial_sums[idx] += row[idx]
        if partial_sums[idx] > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    # greedyに縦線を引いていく
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    left = 0
    right = 0
    partial_sums = [0 for _ in range(len(S2))]
    while right <= W - 1:
        if not satisfy(S2, partial_sums):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
            partial_sums = [0 for _ in range(len(S2))]
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

# if S.sum() <= K:
#     print(0)
#     exit(0)

def satisfy(left, right, S2):
    global K
    for row in S2:
        if row[left:(right + 1)].sum() > K:
            return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    # greedyに縦線を引いていく
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    left = 0
    right = 0
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

if S.sum() <= K:
    print(0)
    exit(0)

def satisfy(left, right, S2):
    global K
    for row in S2:
        # if row[left:(right + 1)].sum() > K:
        #     return False
        pass
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    global W, S
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # TODO: 横線で分けた後のそれぞれのブロックで集計
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0))
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0))
    while right <= W - 1:
        if not satisfy(left, right, S2):
            # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Wrong Answer

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

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            # total = sum(map(lambda row: sum(
            #     row[left:(right + 1)]), S[top:(bottom + 1)]))
            total = 0
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    # total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    total = 0
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)

Submission status: Wrong Answer

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


def _f(H, W, S):
    '''
    >>> f = _f(3, 3, [[1, 0, 0], [1, 0, 1], [0, 1, 1]])
    >>> f(0, 0, 1, 1)
    1
    >>> f(0, 0, 3, 0)
    0
    >>> f(0, 0, 3, 1)
    2
    >>> f(1, 1, 3, 3)
    3
    >>> f(0, 0, 3, 3)
    5
    >>> f(2, 0, 3, 3)
    2
    '''
    acc = [[0] * (W + 1) for _ in range(H+1)]
    for h in range(1, H+1):
        for w in range(1, W+1):
            acc[h][w] = acc[h][w-1] + acc[h-1][w] - acc[h-1][w-1] + S[h-1][w-1]

    def f(sh, sw, eh, ew):
        return acc[eh][ew] + acc[sh][sw] - acc[sh][ew] - acc[eh][sw]

    return f

def _solve(H, W, K, S, c, f):
    #print(H, W, K, S, c, f)
    sw = 0
    cut = 0
    for ew in range(1, W+1):
        #print([(((sh, sw), (eh, ew)), f(sh, sw, eh, ew)) for sh, eh in c])
        if any(f(sh, sw, eh, ew) > K for sh, eh in c):
            cut += 1
            sw = ew - 1
    return cut


def solve(H, W, K, S):
    from itertools import product, compress
    f = _f(H, W, S)
    ans = float('inf')
    for flag in product(range(2), repeat=H-1):
        t = (0,) + tuple(compress(range(1,H), flag)) + (H,)
        c = tuple(zip(t, t[1:]))
        ans = min(ans, _solve(H, W, K, S, c, f)+sum(flag))
    return ans


    

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    H, W, K = list(map(int, input().split()))
    S = [list(map(int, input())) for _ in range(H)]
    print(solve(H, W, K, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Wrong Answer

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

h, w, K = map(int, input().split())
s = []
for i in range(h):
    s.append(input().rstrip())

ans = float('inf')

for i in range(2 ** (h-1)):
    # 仕切り 1, 2, ...
    sep = [0]
    for j in range(h-1):
        if i & (1 << j):
            sep.append(j+1)

    memo = [0 for _ in range(len(sep))]
    cnt = 0
    

    # print(memo)
    # print('new sep: {}'.format(sep))

    for k in range(w):
        # print(memo)
        memo2 = [0 for _ in range(len(sep))]
        sep_index = 0
        for l in range(h):
            # print(sep_index)
            if sep_index < len(sep) - 1 and sep[sep_index+1] < l:
                sep_index += 1
                # print('yay', l, sep_index)
            if s[l][k] == '1':
                if memo[sep_index] + memo2[sep_index] == K:
                    cnt += 1
                    memo = [0 for _ in range(len(sep))]
                memo2[sep_index] += 1
                if memo2[sep_index] > K:
                    cnt += ans
        for ii in range(len(sep)):
            memo[ii] += memo2[ii]
    ans = min(ans, cnt + len(sep) - 1)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


INF = float("inf")

H, W, K = map(int, input().split())
S = []
for i in range(H):
    S.append(input().strip())

ans = INF
for div in range(1 << (H - 1)):
    id = defaultdict(int)
    # 横に割った回数(=グループID)
    g = 0
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1

    # 元の[H行W列]の板チョコを、[g+1行W列]の板チョコとして考え直す
    c = [[0] * W for _ in range(g + 1)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == "1":
                c[id[i]][j] += 1

    now = defaultdict(int)

    def add(j):
        # 1列分追加してみる
        for i in range(g + 1):
            now[i] += c[i][j]
    
    def is_over():
        # Kを超えるグループがあったらFalse、なかったらTrue
        for i in range(g + 1):
            if now[i] > K:
                return False
        return True
        
    num = g
    for j in range(W):
        add(j)
        if is_over():
            num += 1
            now = defaultdict(int)
            add(j)
            if is_over():
                num = INF
                break

    ans = min(ans, num)

print(ans)

Submission status: Wrong Answer

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

S = [input() for _ in range(H)]

ans = 10**10
for i in range(2**(H-1)):   # iはbit
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b
    
    print(rel)
    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    oS=[list(map(int, list(input().rstrip()))) for _ in range(H)]

    ans=10**10
    for p in range(1<<(H-1)):
        S=[[oS[i][j] for j in range(W)] for i in range(H)]
        tmp=0
        for i in range(1,H):
            if p&1:
                for j in range(W):
                    S[i][j] += S[i-1][j]
            else:
                tmp+=1
            p>>=1

        for j in range(W-1):
            for i in range(H):
                if S[i][j]+S[i][j+1]>K:
                    tmp+=1
                    break
            else:
                for i in range(H):
                    S[i][j+1] += S[i][j]

        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    oS=[list(map(int, list(input().rstrip()))) for _ in range(H)]

    ans=10**10
    for p in range(1<<(H-1)):
        S=[[oS[i][j] for j in range(W)] for i in range(H)]
        tmp=0
        up=0
        for i in range(1,H):
            c=p&1
            p>>=1
            if c==up:
                for j in range(W):
                    S[i][j] += S[i-1][j]
            else:
                tmp+=1
            up=c

        for j in range(W-1):
            for i in range(H):
                if S[i][j]+S[i][j+1]>K:
                    tmp+=1
                    break
            else:
                for i in range(H):
                    S[i][j+1] += S[i][j]

        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    oS=[list(map(int, list(input().rstrip()))) for _ in range(H)]

    ans=10**10
    for p in range(1<<H):
        S=[[oS[i][j] for j in range(W)] for i in range(H)]
        tmp=0
        up=p&1
        p>>=1
        for i in range(1,H):
            c=p&1
            p>>=1
            if c==up:
                for j in range(W):
                    S[i][j] += S[i-1][j]
            else:
                tmp+=1
            up=c

        for j in range(W-1):
            for i in range(H):
                if S[i][j]+S[i][j+1]>K:
                    tmp+=1
                    break
            else:
                for i in range(H):
                    S[i][j+1] += S[i][j]

        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

S = [input() for _ in range(H)]

def calc(L):
    M = len(L)
    cnt = [0] * M
    ret = 0

    for w in range(W):
        for i, (t, b) in enumerate(zip(L, L[1:])):
            for j in range(t, b):
                if S[j][w] == '1':
                    cnt[i] += 1
        if max(cnt) > K:
            cnt = [0] * M
            for i, (t, b) in enumerate(zip(L, L[1:])):
                for j in range(t, b):
                    if S[j][w] == '1':
                        cnt[i] += 1
            ret += 1

    return ret

ans = 10**18
for mask in range(1 << (H - 1)):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]
    ans = min(ans, len(L) - 2 + calc(L))
print(ans)

Submission status: Wrong Answer

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

S = [input() for _ in range(H)]

def calc(L):
    M = len(L)
    cnt = [0] * M
    ret = 0

    for w in range(W):
        for i, (t, b) in enumerate(zip(L, L[1:])):
            for j in range(t, b):
                if S[j][w] == '1':
                    cnt[i] += 1
        if max(cnt) > K:
            cnt = [0] * M
            for i, (t, b) in enumerate(zip(L, L[1:])):
                for j in range(t, b):
                    if S[j][w] == '1':
                        cnt[i] += 1
            ret += 1

    return ret

ans = H * W
for mask in range(1 << (H - 1)):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]
    ans = min(ans, len(L) - 2 + calc(L))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input().strip("\n")))) for _ in range(H)]
    sumS = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            sumS[h+1][w+1] = sumS[h+1][w] + sumS[h][w+1] - sumS[h][w] + S[h][w]
    minK = 1000000000000
    for h in range(2 ** (H - 1)):
        count = 0
        border = [0]
        k = h
        for i in range(H-1):
            if k % 2 == 1: 
                border.append(i+1)
                count += 1
            k //= 2
        border.append(H)
        bN = len(border)
        left = 0
        for right in range(1, W + 1):
            ng = False
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    if right - 1 == left: continue
                    else: ng = True
            if ng: 
                left = right - 1
                count += 1
        if left == W - 1:
            right = W
            ng = False
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    continue
 
        minK = min(minK, count)
    print(minK)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

ans = H+W
for b in range(1<<(H-1)):
    gs = [[0]]
    for k in range(H-1):
        if b&(1<<k):
            gs.append([k+1])
        else:
            gs[-1].append(k+1)
    tmp = bin(b).count('1')
    ws = [0] * len(gs)
    for x in range(W):
        for i,g in enumerate(gs):
            for h in g:
                if S[h][x] == '1':
                    ws[i] += 1
        if any(w>K for w in ws):
            tmp += 1
            ws = [0] * len(gs)
            for i,g in enumerate(gs):
                for h in g:
                    if S[h][x] == '1':
                        ws[i] += 1
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

ans = H*W
for b in range(1<<(H-1)):
    gs = [[0]]
    for k in range(H-1):
        if b&(1<<k):
            gs.append([k+1])
        else:
            gs[-1].append(k+1)
    tmp = bin(b).count('1')
    ws = [0] * len(gs)
    for x in range(W):
        for i,g in enumerate(gs):
            for h in g:
                if S[h][x] == '1':
                    ws[i] += 1
        if any(w>K for w in ws):
            tmp += 1
            ws = [0] * len(gs)
            for i,g in enumerate(gs):
                for h in g:
                    if S[h][x] == '1':
                        ws[i] += 1
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input().strip("\n")))) for _ in range(H)]
    sumS = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            sumS[h+1][w+1] = sumS[h+1][w] + sumS[h][w+1] - sumS[h][w] + S[h][w]
    minK = 1000000000000
    for h in range(2 ** (H - 1)):
        count = 0
        border = [0]
        k = h
        for i in range(H-1):
            if k % 2 == 1: 
                border.append(i+1)
                count += 1
            k //= 2
        border.append(H)
        bN = len(border)
        left = 0
        for right in range(1, W + 1):
            ng = False
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    if right - 1 == left: continue
                    else: ng = True
            if ng: 
                left = right - 1
                count += 1
                
        minK = min(minK, count)
    print(minK)
    return 0

if __name__ == "__main__":
    solve()