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:
inxx = input()
inxx = inxx.split()

h, w, k = (int(x) for x in inxx)

mat = []
for _ in range(h):
    mat.append([int(x) for x in input()])

import numpy as np
mat = np.array(mat)

import itertools
it = itertools.product((0,1), repeat=h-1)

sol = h*w
for choice in it:
    rows = [0] + [i for i in range(h-1) if choice[i]] + [h-1]
    sol0 = sum(choice)
    ss = []
    for i in range(len(rows)-1):
        ss.append(mat[rows[i]:rows[i+1]+1].sum(axis=0))
    ss = np.array(ss)
    s = np.zeros(len(ss))
    for j in range(w):
        s += ss[:, j]
        if (s>k).any():
            sol0 += 1
            s = ss[:, j]
    sol = min(sol, sol0)

print(sol)

Submission status: Wrong Answer

Solution code:
import itertools

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

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * H
    for w in range(W):
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

countDP = [ [-1 for _ in range(W)] for __ in range(H) ]

def countF(l, r, t, b):
  if l == 0 and t == 0:
    if countDP[b][r] != -1: return countDP[b][r]
    countDP[b][r] = 0
    for i in range(b+1): countDP[b][r] += S[i][:r+1].count("1")
    return countDP[b][r]
  else:
    return countF(0, r, 0, b) - countF(0, l, 0, b) - countF(0, r, 0, t) + countF(0, l, 0, t)

def solve(l, r, t, b):
  for y in range(t+2, b+1):
    if countF(l, r, t, y) > K: return solve(l, r, t, y-1) + solve(l, r, y, b) + 1
  for x in range(l+2, r+1):
    if countF(l, x, t, b) > K: return solve(l, x-1, t, b) + solve(x, r, t, b) + 1
  return 0

print(solve(0, W-1, 0, H-1))

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)
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
    
    count = 0
    for i in range(w):
        if max(ssss[:, i]) > k:
            ssss -= ssss[:, i - 1][:, None]
            count += 1
    count += sum(binary)
#     print(binary, count)
#     aaaaaa
    if count < mi:
        mi = count
print(mi)

Submission status: Wrong Answer

Solution code:
import bisect


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

    C = [[0] for _ in range(W)]
    for i in range(W):
        for j in range(H):
            if S[j][i] == "1":
                C[i].append(C[i][-1] + 1)
            else:
                C[i].append(C[i][-1])

    res = 2000
    for i in range(2 ** (H - 1)):
        cut = [[0]]
        for j in range(H - 1):
            if (2 ** j) & i != 0:
                cut[-1].append(j + 1)
                cut.append([j + 1])
        cut[-1].append(H)
        lc = len(cut)
        tres = lc - 1
        w = [0 for _ in range(lc)]
        for k in range(W):
            for j in range(lc):
                w[j] += C[k][cut[j][1]] - C[k][cut[j][0]]
            if max(w) > K:
                tres += 1
                w = [C[k][cut[p][1]] - C[k][cut[p][0]] for p in range(lc)]
        res = min(res, tres)

    print(res)


main()

Submission status: Wrong Answer

Solution code:
import copy
H,W,K = [int(i) for i in input().split()]
Chocolate = [[int(i) for i in list(input())]for j in range(H)]
YokoChoko = [[Choc[s] for Choc in Chocolate] for s in range(W)]
minlist = []
for warikata in range(2**(H-1)):#bit全探索
    #[1,1,1,2,2,3,3,3,3]みたいなlistを作りたい
    #1start,0なら増やさず1なら増やす
    wareta = [0]
    curw = 0
    for k in range(H-1):
        if (warikata>>k) & 1:
            curw += 1
        wareta.append(curw)
    lenware = curw
    #lenware回割れてlenware + 1ピースに
    nums = [0 for i in range(lenware + 1)]
    watta = lenware
    for NewChoco in YokoChoko:
        newnums = copy.deepcopy(nums)
        for n,choconum in enumerate(NewChoco):
            newnums[wareta[n]] += choconum
        if max(newnums) <= K:#わらんでいい
            nums = newnums
        else:#割る
            watta += 1
            nums = [0 for i in range(lenware + 1)]
            for n,choconum in enumerate(NewChoco):
                nums[wareta[n]] += choconum
    minlist.append(watta)
print(min(minlist))

Submission status: Wrong Answer

Solution code:
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
#print(cum)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
#for x in cum:
  #print(x)
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      now = j - 1
      ans += 1
  #print(l-1,ans,time)
  can.append(ans)
  time = nex(time)
print(min(can))

Submission status: Wrong Answer

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


wh = 0
for i in range(h):
    s.append(input())
    wh += s[-1].count('1')

co = 0

while wh > k:
    a = 0
    co += 1
    for i in range(w):
        for j in range(h):
            if s[j][i]=='1':
                a += 1

        if wh/2 <= a:
            ai = i
            break

    b = 0
    for i in range(h):
        b += s[i].count('1')
        if wh/2 <= b:
            bi = i
            break

    if a<b:
        for i in range(h):
            s[i] = s[i][:ai]
            w = ai
            wh = a
    else:
        s = s[:bi]
        h = bi
        wh = b

print(co)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for i in range(H)]
    ans = H*W
    for i in range(2**(H-1)):
        border = []
        tmp = 0
        for j in range(H-1):
            if (i >> j) % 2 == 1:  # jの下に線を引く
                border.append(j)
                tmp += 1

        border.append(H-1)
        s = 0
        num = [0]*(tmp+1)
        flag = True
        prev = 0
        for k, x in enumerate(zip(*S)):
            sep = False
            for j, y in enumerate(border):

                if j == 0:
                    prev = 0
                else:
                    prev = border[j-1]+1

                if sep:
                    num[j] = sum(x[prev:y+1])
                elif num[j] + sum(x[prev:y+1]) > K:

                    #print(k, num[j], sum(x[prev:y+1]))
                    sep = True
                    tmp += 1
                    num[j] = sum(x[prev:y+1])
                    for l in range(j):
                        num[l] = sum(x[prev:border[l]+1])
                else:
                    num[j] += sum(x[prev:y+1])

                if num[j] > K:
                    flag = False
                    break

        #print(tmp, flag)
        if flag:
            ans = min(ans, tmp)
        else:
            continue

    print(ans)


main()

Submission status: Wrong Answer

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

# 横の割り方を全通り試す(2**(H-1))
ans = float('inf')
for i in range(2**(H-1)):
    _ans = bin(i).count('1')
    chocos = [list(map(int, S[0]))]
    for j in range(H-1):
        if i >> j & 1:
            chocos.append(list(map(int, S[j+1])))
        else:
            for w in range(W):
                chocos[-1][w] += int(S[j+1][w])
    
    ns = len(chocos)
    nums = [0] * ns
    is_next = False
    for w in range(W):
        for j in range(ns):
            nums[j] += chocos[j][w]
            if nums[j] > K:
                _ans += 1
                is_next = True
                break
        
        if is_next:
            for j in range(ns):
                nums[j] = chocos[j][w]
            is_next = False
    
    ans = min(ans, _ans)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
l=[[0 for i in range(w+1)]]+[[0]+[int(j) for j in input()] for i in range(h)]
a=[[0 for i in range(w+1)] for i in range(h+1)]
for i in range(1,h+1):
    for j in range(1,w+1):
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+l[i][j]
ans=h*w
def ink(h2,h1,w2,w1):
    return a[h2][w2]-a[h1][w2]-(a[h2][w1]-a[h1][w1])
for i in range(2**(h-1)):
    tl=[0]
    for j in range(h-1):
        if i>>j&1:
            tl.append(j+1)
    tl.append(h)
    t=len(tl)-2
    w1=0
    for w2 in range(1,w+1):
        for h1,h2 in zip(tl,tl[1:]):
            if ink(h2,h1,w2,w1)>k:
                w1=w2-1
                t+=1
                break
    ans=min(ans,t)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [0] * (hcut+1)
    aftercut = True
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            if aftercut:
                break
            else:
                aftercut = True
                whites = thisline
                m = max(whites)
                cur += 1
                if cur >= ans or m > K:
                    break
        else:
            aftercut = False
    else:
        ans = cur
            
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,z=map(int,input().split())
a=[]
e=10000
g=0
l=0
def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=int(a[i])
        b.append(c)
    return b
for i in range(h):
    a.append(list(input()))
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:
            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):
            if c[k]>z:
                d+=1
                g=1
        j+=1
    e=min(e,d+f[-1])
print(e)

Submission status: Wrong Answer

Solution code:
h,w,K=map(int,input().split())
data=[[0 for i in range(w+1)]]
for i in range(h):
    x=list(input())
    x.insert(0,0)
    for j in range(w+1):
        x[j]=int(x[j])
    data.append(x)
    
for i in range(h+1):
    for j in range(1,w+1):
        data[i][j]+=data[i][j-1]
        
for i in range(w+1):
    for j in range(1,h+1):
        data[j][i]+=data[j-1][i]
        


ans=10**10
for _ in range(2**(h-1)):
    st=choice=format(_,"0%ib"%(h-1))
    div=[0]
    sub=0
    for j in range(h-1):
        if st[j]=="1":
            div.append(j+1)
            sub+=1
    div.append(h)
    cnt=0
    nowindex=0
    for j in range(1,w+1):
        flag=True
        if nowindex==0:
            for k in range(1,len(div)):
                if data[div[k]][j]-data[div[k-1]][j]>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
                 
        else:
            for k in range(1,len(div)):
                if (data[div[k]][j]-data[div[k]][nowindex])-(data[div[k-1]][j]-data[div[k-1]][nowindex])>K:
                    flag=False
                    break
            if flag is False:
                nowindex=j-1
                cnt+=1
    ans=min(ans,sub+cnt)

print(ans)

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)
        
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w,K = LI()
s = [input() for _ in range(h)]

ans = inf
for i in range(2**(h-1)):
    bit = [0]*(h-1)
    cnt = 0
    for j in range(h-1):
        if (i >> j) & 1:
            bit[j] = 1
            cnt += 1
    lst = [[0]*w for _ in range(cnt+1)]
    preans = cnt
    C = cnt
    tmp = 0
    cnt = 0
    for j in range(h-1):
        if bit[j]:
            for l in range(w):
                for k in range(tmp, j+1):
                    if s[k][l] == '1':
                        lst[cnt][l] += 1
            tmp = j+1
            cnt += 1

    for j in range(w):
        for k in range(tmp,h):
            if s[k][j] == '1':
                lst[-1][j] += 1
    T = [0]*(C+1)
    flg = True
    for k in range(w-1):
        for j in range(C+1):
            T[j] += lst[j][k]
            if lst[j][k] > K:
                flg = False
            if T[j] + lst[j][k+1] > K:
                preans += 1
                T = [0]*(C+1)
                break
    if flg:
        ans = min(ans, preans)
print(ans)

Submission status: Wrong Answer

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

count=[]
for i in range(h):
  L=[0]
  for j in range(w):
    L.append(int(l[i][j])+L[-1])
  count.append(L)

b=[]
for i in range(2**(h-1)):
  b.append(format(i,'0'+str(h-1)+'b'))

ans=[]
cut=0
for i in range(len(b)):
  cutct=0
  cut=0
  for j in range(1,w+1):
    ct=[]
    for j2 in range(h):
      ct.append(count[j2][j]-count[j2][cut])
    check=[]
    x=ct[0]
    for j3 in range(h-1):
      if b[i][j3]=='0':
        x+=ct[j3+1]
      else:
        check.append(x)
        x=ct[j3+1]
    check.append(x)
    if max(check)>k:
      cut=j-1
      cutct+=1
  ct1=0
  for j4 in range(h-1):
    if b[i][j4]=='1':
      ct1+=1
  ans.append(cutct+ct1)
print(min(ans))

Submission status: Wrong Answer

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

Acum = [[0] * (W+1) for i in range(H+1)]
for i in range(H):
    for j in range(W):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + fields[i][j]
"""
# 実験
h1,h2,w1,w2 = 1,3,1,5 #(1,1)->(2,3)までの累積和
ans = Acum[h2][w2] - Acum[h1][w2] - Acum[h2][w1] + Acum[h1][w1]
print("aaa",ans)
for i in range(H+1):
    print(Acum[i])
"""
# 縦方向は区切り方が2**(H-1)通りを全探索
# 横方向に区切りながらすすめていく(なるべく大きくとっていく)
ans = 10**10
for i in range(2**(H-1)):

    s = bin(i)[2:]
    s_zero = s.zfill(H-1)
    # print(s_zero)
    # 横区切り線の位置
    a = [0]+[i+1 for i,s in enumerate(s_zero) if int(s) == 1]
    a += [H]
    # 縦区切り線の位置
    w_cnt = 0
    w1 = 0
    w = 0
    m = 0
    while w <= W:
        m = 0
        for j in range(1,len(a)):
            h1 = a[j-1]
            h2 = a[j]
            cnt = Acum[h2][w] - Acum[h1][w] - Acum[h2][w1] + Acum[h1][w1]
            m = max(m,cnt)
            if m > K:
                w_cnt += 1
                w1 = w -1         
        w += 1
    ans = min(ans,sum(map(int,list(s)))+w_cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
if h==1:
  co=b[0].count(1)
  print((0--co//kk)-1)
  exit()
if w==1:
  co=0
  for i in b:co+=i[0]
  print((0--co//kk)-1)
  exit()
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(h**2):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
for i in b:i=i[::-1]
for i in range(h**2):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = []
for i in range(h):
    temp = list(input())
    temp = list(map(int, temp))
    s.append(temp)
ans = 2000
for i in range(2 ** (h - 1)):
    line = 0
    temp = bin(i + 2 ** (h - 1))
    group = [[0]]
    for j in range(h - 1):
        if temp[-1-j] == "0":
            group[-1].append(j + 1)
        else:
            group.append([j + 1])
            line += 1
    count = [0] * len(group)
    for j in range(w):
        for l in range(len(group)):
            for m in group[l]:
                count[l] += s[m][j]
        flag = True
        for l in count:
            if l > k:
                flag = False
                break
        if flag == False:
            line += 1
            count = [0] * len(group)
            for l in range(len(group)):
                for m in group[l]:
                    count[l] += s[m][j]
    ans = min(ans, line)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
S = []
for i in range(H):
	s = list(map(int, list(input())))
	S.append(s)
A = [[0 for i in range(W+1)] for j in range(H+1)]
for i in range(H):
	for j in range(W):
		A[i+1][j+1] = A[i+1][j] + A[i][j+1] - A[i][j] + S[i][j]

def f(x1,y1,x2,y2):
	return A[x2][y2] - A[x1-1][y2] - A[x2][y1-1] + A[x1-1][y1-1]

if f(1,1,H,W) <= K:
	print(0)
	exit()

m = H+W

def int2bit(n):
	ret = [0 for i in range(H-1)]
	c = 0
	while n > 0:
		ret[c] = n % 2
		n = n // 2
		c += 1
	return ret

def getx1x2(b):
	ret = []
	x1 = 1
	for i in range(H-1):
		if b[i] == 1:
			ret.append((x1, i+1))
			x1 = i+2
	ret.append((x1, H))
	return ret

for i in range(2**(H-1)):
	x1x2 = getx1x2(int2bit(i))
	cnt = len(x1x2) - 1
	y1 = 1
	possible = True
	for y2 in range(2, W+1):
		flag = False
		for x1, x2 in x1x2:
			if f(x1,y1,x2,y2) > K:
				if y2 - y1 == 1 and f(x1, y1, x2, y1) > K:
					possible = False
				flag = True
				break
		if flag:
			y1 = y2
			cnt += 1
		if not possible:
			break
	if possible:
		m = min(m, cnt)
print(m)

Submission status: Wrong Answer

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
H, W, K = inpl()
S = [input() for h in range(H)]
ans = H+W
for c in itertools.product(range(2),repeat=H-1):
    hcut = sum(c)
    if hcut >= ans:
        continue
    segment = [0]
    s = 0
    for h in range(H-1):
        if c[h]:
            s += 1
        segment.append(s)
    cur = hcut
    whites = [0] * (hcut+1)
    aftercut = True
    for w in range(W):
        thisline = [0]*(hcut+1)
        for h in range(H):
            if S[h][w] == '1':
                whites[segment[h]] += 1
                thisline[segment[h]] += 1
        m = max(whites)
        if m > K:
            if aftercut:
                break
            else:
                aftercut = True
                whites = thisline
                cur += 1
                if cur >= ans:
                    break
        else:
            aftercut = False
    else:
        ans = cur
            
print(ans)

Submission status: Wrong Answer

Solution code:
"""
NTC here
"""
import sys
inp = sys.stdin.readline


def input(): return inp().strip()


flush = sys.stdout.flush
# import threading
# sys.setrecursionlimit(10**6)
# threading.stack_size(2**25)


def iin(): return int(input())


def lin(): return list(map(int, input().split()))

# range = xrange
# input = raw_input


def main():
    def cnt_ones(n):
        ch = 0
        x = n
        ans = []
        while x:
            if x&1:
                ans.append(ch)
            x>>=1
            ch+=1
        return ans
    ans = []
    h, w, K = lin()
    a = [list(map(int, list(input()))) for _ in range(h)]
    h1 = 2**(h-1)
    for i in range(h1):
        ch = cnt_ones(i)+[h-1]
        l1 = len(ch)
        a1 = [0]*(l1)
        ch2 = 0
        for j in range(w):
            ch1 = 0
            a2 = [0]*(l1)
            for k in range(h):
                a2[ch1]+=a[k][j]
                if ch[ch1]==k:
                    ch1+=1
            for k in range(l1):
                if a1[k]+a2[k]>K:
                    ch2 += 1
                    a1 = a2[:]
                    break
            else:
                for k in range(l1):
                    a1[k]+=a2[k]
        ans.append(l1-1+ch2)
    # print(ans)
    print(min(ans))



main()
# threading.Thread(target=main).start()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w,K = LI()
s = [input() for _ in range(h)]

ans = inf
for i in range(2**(h-1)):
    bit = [0]*(h-1)
    cnt = 0
    for j in range(h-1):
        if (i >> j) & 1:
            bit[j] = 1
            cnt += 1
    lst = [[0]*w for _ in range(cnt+1)]
    preans = cnt
    C = cnt
    tmp = 0
    cnt = 0
    for j in range(h-1):
        if bit[j]:
            for l in range(w):
                for k in range(tmp, j+1):
                    if s[k][l] == '1':
                        lst[cnt][l] += 1
            tmp = j+1
            cnt += 1

    for j in range(w):
        for k in range(tmp,h):
            if s[k][j] == '1':
                lst[-1][j] += 1
    T = [0]*(C+1)
    for k in range(w-1):
        for j in range(C+1):
            T[j] += lst[j][k]
            if T[j] + lst[j][k+1] > K:
                preans += 1
                T = [0]*(C+1)
                break
    ans = min(ans, preans)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,kk=map(int,input().split())
G=[[0]*w for i in range(h)]
for i in range(h):
  G[i]=list(input())
for i in range(h):
  for j in range(w):
    G[i][j]=int(G[i][j])
ans=10**5
for i in range(2**(h-1)):
  s=format(i,'12b')
  A=[-1]
  for j in range(h-1):
    if s[-1-j]=="1":
      A.append(j)
  A.append(h-1)
  ans1=len(A)-2
  B=[0]*(len(A)-1)
  c=0
  i=0
  while i<w:
    j=0
    while j<len(A)-1:
      for k in range(A[j]+1,A[j+1]+1):
        B[j]+=G[k][i]
      if B[j]>kk:
        c=c+1
        B=[0]*(len(A)-1)
        if c>1010:
          j=100
          i=10000
          break
      else:
        j=j+1
    i=i+1
  if ans1+c<ans:
    ans=ans1+c
print(ans)

Submission status: Wrong Answer

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

min_num = float("inf")
for i in range(1<<(h-1)):
    c = 0
    d = {0:0}
    bar = 0
    for ii in range(1,h):
        if i&(1<<(ii-1)):
            c += 1
            bar += 1
        d[ii] = c

    # print(bin(i), bar, d)
    ss = [0]*(c+1)
    for wi in range(w):
        flag = False
        ss_tmp = [0]*(c+1)
        for hi in range(h):
            if A[hi][wi] == "1":
                ss_tmp[d[hi]] += 1
                if ss_tmp[d[hi]] + ss[d[hi]] > k:
                    flag = True

        if flag:
            ss = ss_tmp
            bar += 1
        else:
            for i in range(c+1):
                ss[i] += ss_tmp[i]
        # print(wi, flag, bar)
        # print(ss, ss_tmp)

    min_num = min(min_num, bar)

print(min_num)

Submission status: Wrong Answer

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

count = 0
for i in s:
    for j in i:
        if j == "1":
            count +=1
ans = 0
for i in range(1000):
    count = count // k
    ans += 1
    if count == 0:
        print(ans)
        break

Submission status: Wrong Answer

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

    m = 10 * 1000
    for h in range(2 ** (H - 1)):
        T = []
        s = [0]
        c = 0
        for i in range(H - 1):
            if h & (1 << i):
                T.append(s)
                s = [i + 1]
                c += 1
            else:
                s.append(i + 1)
        T.append(s)
        C = [0] * len(T)
        for w in range(W):
            split = False
            for i, t in enumerate(T):
                cc = 0
                for j in t:
                    if S[j][w] == '1':
                        cc += 1
                C[i] += cc
                if C[i] > K:
                    split = True
                    C[i] = K + cc
            if split:
                for i in range(len(C)):
                    C[i] = max(0, C[i] - K)
                c += 1
        m = min(c, m)
    return m

print(main())

Submission status: Wrong Answer

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

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    # print(cut_h)
    # print(blocks)
    # print(counts)

    mincounts = float('inf')
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            mincounts = min(mincounts, counts[j][k])
    if mincounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            # print(cumsums)
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    # print(tmpans)
print(ans)

Submission status: Wrong Answer

Solution code:
class CumulativeSum2D:
  def __init__(self,a):
    self.h=len(a)
    self.w=len(a[0])
    self.s=[(self.w+1)*[0]for _ in range(self.h+1)]
    for i in range(self.h):
      for j in range(self.w):
        self.s[i+1][j+1]=self.s[i+1][j]+self.s[i][j+1]-self.s[i][j]+a[i][j]
  def su(self,i1,j1,i2,j2):
    return self.s[i2+1][j2+1]-self.s[i1][j2+1]-self.s[i2+1][j1]+self.s[i1][j1]
  def prin(self):
    for i in self.s:print(i)
h,w,kk=map(int,input().split())
b=[list(map(int,list(input())))for _ in range(h)]
if h==1:
  co=b[0].count(1)
  print((0--co//kk)-1)
  exit()
if w==1:
  co=0
  for i in b:co+=i[0]
  print((0--co//kk)-1)
  exit()
h-=1
bs=CumulativeSum2D(b)
ans=h+w-1
for i in range(h**2):
  bi=[-1]+[j for j in range(h)if(1<<j)&i]+[h]
  anss=len(bi)-2
  flag=False
  cut=[0]
  for k in range(w):
    for j in range(len(bi)-1):
      up=bi[j]+1
      down=bi[j+1]
      s=bs.su(up,cut[-1],down,k)
      if s>kk:
        if k==cut[-1]:flag=True
        else:cut.append(k);anss+=1
        break
    if flag:break
  if flag:continue
  ans=min(ans,anss)
print(ans)