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=list(map(int,input().split()))
S=[input() for i in range(H)]
S1=0
for i in range(H):
    S1 += S[i].count('1')
if S1 <= K:
    print(0)
else:
    ans=0
    while S1 >= K:
        ans += 1
        S1 /= 2
    print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]


    ans = inf
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        cur = inf
                        break
                    cur += 1
                    L = [0] * (len(cut))
                    break
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]
        if not flag:
            continue
        ans = min(ans,cur)

    print(ans)
    return
"""
2 1 1
1
1
"""# 1

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

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

def main():
    h, w, k = na()
    Sum = 0
    s = []
    NumOfWhiteCol = []
    for i in range(h):
        s.append(ns())
        c = s[i].count("1")
        Sum += c
        NumOfWhiteCol.append(c)
    
    if Sum <= k:
        print(0)
        return

    if Sum % k == 0:
        print(Sum // k)
    else:
        print(-(-Sum // k) // 2)

    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w, k = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = list(map(int, list(input())))
    ss.append(s)

from itertools import product

mi = 1e9
ss = np.array(ss)

if h == 1 and w == 1:
    print(0)
else:
    if h > w:
        h, w = w, h
        ss = ss.T
    sss = np.cumsum(ss, axis = 1)
    
    for binary in product([0, 1], repeat=h - 1):
        binary  = [0] + list(binary)

        ssss = [0]
        for j in range(h):
            if binary[j] == 1:
                ssss.append(sss[j])
            else:
                ssss[-1] += sss[j]

        ssss = np.array(ssss)
#         if np.max(np.diff(ssss, axis = 1)) > k:
#             continue
#         print("----")
#         print(ssss)
#         print(ssss[:,0])
        if max(ssss[:,0]) > k:
            continue
    #     print(ssss)
        count = 0
        for i in range(w):
            if max(ssss[:, i]) > k:
                ssss -= ssss[:, i - 1][:, None]
                if max(ssss[:,i]) > k:
                    count += 99999

                count += 1
        count += sum(binary)
#         print(binary, count)
    #     aaaaaa
        if count < mi:
            mi = count
    print(mi)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
h, w, k = map(int, input().split())
maze = []
ts = []
for _ in range(h):
    l = input()
    l = list(map(int, list(l)))
    #print(l)
    x = 0
    tmps = []
    for j in range(w):
        x += l[j]
        tmps.append(x)
    ts.append(tmps)
    maze.append(l)
#pprint(maze)
#pprint("--")
#pprint(ts)

bin_a = ["{:09b}".format(a) for a in range(0, 2 ** (h - 1))]

res = 9999999
for cutpat in bin_a:
    cutpat = cutpat[::-1]
    #print("cutpat", cutpat)
    cutsum = [0] * 10
    gr = [-1] * 10
    gr[0] = 0
    grnum = 0
    for i in range(1, h):
        if cutpat[i - 1] == "1":
            grnum += 1
        gr[i] = grnum
    #print("grlist", gr)

    firstFail = False

    cutcount = cutpat.count("1") # 縦の切った回数
    for i in range(w): # 進む
        #print(" do", i)
        for j in range(h):
            cutsum[ gr[j] ] += maze[j][i]
        #print(" res", cutsum)
        isFail = False
        for j in range(h-1):
            #print("  chk gr", j)
            if cutsum[j] > k:
                #print("over! gr:", j)
                isFail = True
                if i == 0:
                    firstFail = True
        if isFail:
            #print("cut", i)
            cutcount += 1
            cutsum = [0] * 10
            for j in range(h):
                cutsum[gr[j]] += maze[j][i]
            for j in range(h-1):
                if cutsum[j] > k:
                    isFail = True
                    if i == 0:
                        firstFail = True

    if firstFail:
        continue

    res = min(res, cutcount)
print(res)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
c1=0
a=[]
for i in range(0,h):
  x=input()
  a.append(list(x))
  c1+=a[i].count('1') 
  #print(c1,a[i])
if c1<=k:
  print(0)
else:
  k1=2
  while (c1//k1) >= k:
      k1+=2
  if k1==0:
      print(0)
  else:
      print(k1//2)

Submission status: Wrong Answer

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

ans = None
for i in range(2**(h - 1)):
    t = 0
    to_add = [0]
    for a in range(h - 1):
        if i & (2**a):
            t += 1
        to_add.append(t)
    n_h = t
    n_w = 0
    zz = [0 for _ in range(n_h + 1)]
    cnts = zz.copy()
    for x in range(w):
        is_over = False
        for y in range(h):
            z = to_add[y]
            cnts[z] += ar[y][x]
            if cnts[z] > k:
                is_over = True
                break
        if is_over:
            n_w += 1
            if ans is not None and ans <= n_h + n_w:
                break
            
            cnts = zz.copy()
            for y in range(h):
                cnts[to_add[y]] += ar[y][x]
    if ans is None or ans > n_h + n_w:
        ans = n_h + n_w
print(ans)

Submission status: Wrong Answer

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

white = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i != 0:
            white[i][j] += white[i-1][j]
        if j != 0:
            white[i][j] += white[i][j-1]
        if i != 0 and j != 0:
            white[i][j] -= white[i-1][j-1]
        white[i][j] += choco[i][j]
ans = float('inf')
for i in range(2**(h-1)): #横に切る位置をbitでもつ
    temp = format(i,'b').count('1') # 横に何かいきるか
    hw = []#h == どこの下で切るか
    j = i
    cnt = 0
    while j >0:
        if j&1:
            hw.append(cnt)
        cnt += 1
        j = j >> 1
    hw.append(h-1)
    now = -1
    for j in range(w-1):
        flag = True
        if now == -1:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l-1]][j+1] > k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
        else:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] - white[hw[l]][now] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l]][now] - white[hw[l-1]][j+1] + white[hw[l-1]][now]> k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
    ans = min(ans,temp)
print(ans)

Submission status: Wrong Answer

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

sum_w = [[0] * (w+1) for _ in range(h)]
for i in range(h):
    for j in range(1,w+1):
        sum_w[i][j] = sum_w[i][j-1] + s[i][j-1]

# sum_h = [[0] * w for _ in range(h+1)]
# for i in range(1,h+1):
#     for j in range(w):
#         sum_h[i][j] = sum_h[i-1][j] + sum_w[i-1][j+1]

sums = []
for i in range(h):
    sums.append([[0] * w for _ in range(h+1)])

for i in range(h):
    for j in range(i+1,h+1):
        for l in range(w):
            sums[i][j][l] = sums[i][j-1][l] + sum_w[j-1][l+1]

ans = h + w
for i in range(2**(h-1)):
    nums = []
    for j in range(h-1):
        if((i >> j)&1 == 1):
            nums.append(j+1)
    tmp = len(nums)
    nums.append(h)
    # print(nums)
    head = 0
    checks = []
    for j in nums:
        checks.append(sums[head][j])
        head = j
    # print(i)
    # print(checks)

    minus_num = [0] * len(checks)
    w_now = 0
    NG_flag = 0
    cut_flag = 0
    for j in range(w):
        if(NG_flag == 1):
            break
        for l in range(len(checks)):
            check_num = checks[l][j] - minus_num[l]
            if(check_num > k):
                if(w_now == 0):
                    # print('hoge')
                    NG_flag = 1
                    break
                cut_flag = 1
                break


        if(cut_flag==1):
            # print('j={}'.format(j))
            tmp += 1
            for l in range(len(checks)):
                minus_num[l] = checks[l][j-1]
                check_num = checks[l][j] - minus_num[l]
                if(check_num > k):
                    NG_flag=1
                    break
            cut_flag = 0
            w_now = 0
        else:
            w_now += 1

    # print('')
    # print(tmp)
    if(NG_flag==0):
        ans = min(ans, tmp)
        # print('ans = {}'.format(ans))


print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
from itertools import combinations

def main():
    import sys
    H,W,K=list(map(int,sys.stdin.readline().split()))
    
    C=np.zeros((H,W))
    for i in range(H):
        C[i]=np.array(list(sys.stdin.readline().strip()))
    
    output=10**9

    cut=0
    cut_pos=0
    for j in range(1,W+1):
        if np.sum(C[:,cut_pos:j])>K:
            cut+=1
            cut_pos=j-1

    output=cut if cut<output else output
    
    if output<=1:
        print(output)
        return 


    for i in range(1,H):
        for cmb in combinations(list(range(1,H+1)),i):#横線の組み合わせ 
            cut=0
            cut_pos=0
            cut+=len(cmb)
            for j in range(1,W+1):
                for k in range(len(cmb)):
                    if k==0:
                        if np.sum(C[:cmb[k],cut_pos:j])>K:
                            cut+=1
                            if cut_pos==j-1:
                                cut=10**9
                                break
                            cut_pos=j-1
                    else:
                        if np.sum(C[cmb[k-1]:cmb[k],cut_pos:j])>K:
                            cut+=1
                            if cut_pos==j-1:
                                cut=10**9
                                break

                            cut_pos=j-1

                    if cut>output:
                        break
                
                if np.sum(C[cmb[-1]:,cut_pos:j])>K:
                    cut+=1
                    cut_pos=j-1

                if cut>output:
                    break
            

            output=cut if cut<output else output


    print(output)



main()

Submission status: Wrong Answer

Solution code:
h, w, kkk = map(int, input().split())
choco = [0]*h
for i in range(h):
  choco[i] = input()

answer = h+w-2
for i in range(max([2*(h-1), 1])):
  flag = True
  board = [0]*(h-1)
  for j in range(h-1):
    if (i >> j)&1:
      board[j] = 1
  count = sum(board)
  key = [0]*(count+1)
  ans = count
  for p in range(w):
    k = 0
    for q in range(h):
      if choco[q][p] == "1":
        key[k] += 1
      if q == h-1:
        break
      if board[q] == 1:
        k += 1
    for q in range(count+1):
      if key[q] <= kkk:
        continue
      ans += 1
      if p == w-1:
        flag = False
      key = [0]*(count+1)
      k = 0
      for q in range(h):
        if choco[q][p] == "1":
          key[k] += 1
        if q == h-1:
          break
        if board[q] == 1:
          k += 1
      break
  if ans < answer and flag:
    answer = ans
print(answer)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
s=[list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])
"""
前処理 : 二次元累積和 O(hw)
入力 : h(第一成分の長さ), w(第二成分の長さ), c(リスト)
cum[i][j]=(0,0)~(i,j)の和(面積)
"""
def cum_gen(h,w,c):
    cum = [[0]*w for i in range(h)]
    cum[0][0] = c[0][0]
    for j in range(1,w):
        cum[0][j] = cum[0][j-1] + c[0][j]
    for i in range(1,h):
        now = 0
        for j in range(w):
            now += c[i][j]
            cum[i][j] += cum[i-1][j] + now
    return cum
"""
計算パート O(1)
cum_calc(a,b,x,y)=(a,b)~(x,y)の和(面積)
"""
def cum_calc(a,b,x,y):
    if a>x or b>y:
        return 0
    if a==0 and b==0:
        return cum[x][y]
    if a==0:
        return cum[x][y]-cum[x][b-1]
    if b==0:
        return cum[x][y]-cum[a-1][y]
    return cum[x][y]-cum[x][b-1]-cum[a-1][y]+cum[a-1][b-1]
cum=cum_gen(h,w,s)
# print(cum_calc(1,2,2,3))
# for i in cum:
#     print(i)
ans=10101010011
for i in range(1<<(h-1)):
    se=[]
    for j in range(h-1):
        if i>>j&1:
            se.append(j)
    se.append(h-1)
    z=len(se)
    flag=True
    cnt=z
    x,y=0,0 #x:h方向, y:w方向
    sepy=set()
    for p in range(z):
        for j in range(w):
            if cum_calc(x,y,se[p],j)>k and (x==se[p] or y==j):
                flag=False
                break
            if j in sepy:
                y=j
            elif cum_calc(x,y,se[p],j)>k:
                y=j
                sepy.add(j)
                cnt+=1
        x=se[p]+1
        if not flag:
            break
    if flag:
        # print(cnt,i,se,sepy)
        ans=min(ans,cnt-1)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]


    ans = (H-1)*(W-1)
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        break
                    cur += 1
                    L = [0] * (len(cut))
                    break
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]

        if not flag:
            continue
        ans = min(ans,cur)



    print(ans)
    return

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
#未来の僕へ、これはクソ重実装だけどがんばって解読するなり、自分で解くなりしてくれ
#大まかな方針としては、どう横に切るかをbit全探索、どう縦に切るかを貪欲に探索していく形だ
#ある列のホワイトチョコレートが許容数を超えたら、縦線を追加し、一個巻き戻して進んでいく形になっている
#計算量はO(hw*2^h)で10^7ほどと十分に高速なはずなんだが、pythonのせいか通らなかった

#a...入力されたチョコレート
#b...bit全探索用の文字列
#c...そのブロックの中で何個ホワイトチョコレートがあったか
#d...そのbitで何回縦割りを行ったか
#e...出力用変数(その時点での最小分割数を保持)
#f...ホワイトチョコレートに当たった時に、cのどの横割りに格納すればよいか(累積和)
#g...ホワイトチョコレートが許容数を超えた際に1になるフラグ
#h...チョコレートの縦の長さ
#i...何回目のbit全探索か
#j...左から何個目の列を見ているか(正確には見ているはずだったか)
#k...上から何個目の行を見ているか
#l...何回巻き戻したか(ホワイトチョコレートがあふれて、一個前から数えなおした回数)
#w...チョコレートの横の長さ
#z...ホワイトチョコレートの許容数

#fを作るための累積和の定義

def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=int(a[i])
        b.append(c)
    return b

#入力の受け取り・変数の初期化

h,w,z=map(int,input().split())
a=[]
e=10000
g=0
l=0
for i in range(h):
    a.append(list(input()))

#bit全探索

for i in range(2**(h-1)):
    #変数のリセット
    b=(h-len(bin(i)[2:-1]+bin(i)[-1])-1)*'0'+bin(i)[2:-1]+bin(i)[-1]
    f=Csum(b)
    c=[0]*h
    d=0
    l=0
    j=0
    #巻き戻しの回数+横幅の回数だけ処理を行う
    while j<w+l:
        #巻き戻りフラグの確認
        if g==1:
            #切ったのでホワイトチョコレートのカウントを0に、巻き戻しのカウントをインクリメントする
            c=[0]*h
            l+=1
            g=0
        #縦に見ていく
        for k in range(h):
            #ホワイトチョコレートだったらカウンタをインクリメント
            if a[k][j-l]=='1':
                c[f[k]]+=1
        #ホワイトチョコレートが許容数をオーバーしていないかすべてのブロックで確認
        for k in range(h):
            #オーバーしていたら縦線を引き、フラグgを1にする
            if c[k]>z:
                d+=1
                g=1
        #while文なのでインクリメントを忘れずに
        j+=1
    #縦割りの数+横割りの数が現在の最小値より少なかったら更新
    e=min(e,d+f[-1])

#最小値を出力
print(e)

Submission status: Wrong Answer

Solution code:
h,w,kk = map(int,input().split())
arr = []
for i in range(h):
    arr.append(list(map(int,list(input()))))

h_loop = 2**(h-1)
ans = 100000000
for i in range(h_loop):
    sep = format(i,'b').zfill(h-1)
    ups = sum(map(int,list(sep)))
    slash = ups
    buf = [0 for j in range(ups+1)]
    temp_buf = [0 for j in range(ups+1)]
    is_sep = False
    # print(sep)
    for j in range(w):
        b_ind = 0
        is_sep = False
        for k in range(h):
            if k == 0:
                temp_buf[b_ind] += arr[k][j]
            else:
                if sep[k-1] == "1":
                    b_ind += 1
                    temp_buf[b_ind] += arr[k][j]
                else:
                    temp_buf[b_ind] += arr[k][j]

        for k in range(ups+1):
            if temp_buf[k] + buf[k] > kk:
                is_sep = True
        # print(buf)
        # print(temp_buf)
        # print(is_sep)
        if is_sep:
            slash += 1
            buf = temp_buf
        else:
            for k in range(ups+1):
                buf[k] += temp_buf[k]
        temp_buf = [0 for j in range(ups + 1)]

    # print(slash)
    if ans > slash:
        ans = slash

print(ans)

Submission status: Wrong Answer

Solution code:
###https://juppy.hatenablog.com/entry/2019/03/26/%E8%9F%BB%E6%9C%AC_Python_%E4%BA%8C%E6%AC%A1%E5%85%83%E7%B4%AF%E7%A9%8D%E5%92%8C_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da

def count(H,W,S):
    count = 0
    for i in range(H):
        for j in range(W):
            count += S[i][j]
    return count

H,W,K = map(int,input().split())
S = []
for i in range(H):
    tmp = list(input())
    tmp2 = []
    for j in range(W):
        tmp2.append(int(tmp[j]))
    S.append(tmp2)
if count(H,W,S) <= K:
    print(0)
    exit()
rsum = da_generate(H,W,S)
m = rsum[-1][-1]
ind = 0
mid = 1e9
for i in range(H):
    for j in range(W):
        tmp = abs(m/2-rsum[i][j])
        if tmp < mid:
            ind = [i,j]
            mid = tmp
import math
print(math.ceil(m/rsum[ind[0]][ind[1]]))

Submission status: Wrong Answer

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

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(max(0, ans))

Submission status: Wrong Answer

Solution code:
def Donyoku(pattern):
    global w,k
    l=len(pattern)
    saisho=0
    now=[0]*l
    tasu=[0]*l
    for yoko in range(w):
        daijobu=True
        for i in range(l):
            hahen=pattern[i]
            tasu[i]=0
            for ha in hahen:
                tasu[i]+=ha[yoko]
            if(now[i]+tasu[i]>k):
                daijobu=False
        if(daijobu):
            for i in range(l):
                now[i]+=tasu[i]
        else:
            saisho+=1
            for i in range(l):
                now[i]=tasu[i]
        #print(now)
    return saisho
                
        


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

choco=[]
for i in range(h):
    s=input()
    temp=[0]*w
    for j in range(w):
        temp[j]=int(s[j])
    choco.append(temp)

#print(choco)

ans=10**6
for i in range(2**(h-1)):
    wari=[]
    gen=0
    sude=0
    for j in range(h):
        if((i>>j) & 1):
            wari.append(choco[gen:j+1])
            gen=j+1
            sude+=1
    wari.append(choco[gen:h])
    #print(i,"番目の試行")
    #for wa in wari:
    #    print(wa)
    ima=sude+Donyoku(wari)
    #print(ima)
    if(ima<ans):
        ans=ima

print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]


    ans = (H-1)*(W-1)
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        prev = 0
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if prev == w:
                        flag = False
                        break
                    prev = w
                    cur += 1
                    L = [0] * (len(cut))
                    break
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]

        if not flag:
            continue
        ans = min(ans,cur)



    print(ans)
    return

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*N for _ in range(S*2)]
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
c1=0
a=[]
for i in range(0,h):
  x=input()
  a.append(list(x))
  c1+=a[i].count('1') 
  #print(c1,a[i])
if c1<=k:
  print(0)
else:
  k1=2
  while (c1//k1) > k:
      k1+=2
  print(k1)

Submission status: Wrong Answer

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

cum_s = [[0 for _ in range(w+1)] for _ in range(h)]
for i in range(1, w+1):
    for j in range (h):
        cum_s[j][i] += (s[j][i-1] == '1') + cum_s[j][i-1]
#print(cum_s)

ans = 10 ** 6
for i in range(2 ** (h-1)):
    sep = []
    tmp = [0]
    for j in range(h-1):
        if (i >> j) & 1:
            tmp.append(j+1)
        else:
            if tmp != []:
                sep.append(tmp)
            tmp = [j+1]
    sep.append(tmp)
    #print(sep)
    
    idx = 0
    cnt = 0
    for j in range(1,w+1):
        flg = False
        for l in sep:
            tmp_sum = sum([cum_s[x][j] - cum_s[x][idx] for x in l])
            if tmp_sum > k:
                flg = True
        
        if flg:
            cnt += 1
            idx = j-1 
    #print(len(sep)-1, cnt)
    ans = min(ans, len(sep)-1 + cnt)

if w == 1:
    x = sum([s[i] == '1' for i in range(h)])
    print(max(0, -(-x // k)-1))
elif h == 1:
    x = sum([s[0][i] == '1' for i in range(w)])
    print(max(0, -(-x // k)-1))
else:
    print(ans)