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 = []
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]
            if count[l] > k:
                line += 1
                count = [0] * len(group)
                for m in group[l]:
                    count[l] += s[m][j]
    ans = min(ans, line)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w,k = inpm()
    s = [[] for _ in range(h)]
    for i in range(h):
        a = list(input())
        for j in range(w):
            s[i].append(int(a[j]))
    dp = [[0 for _ in range(w+1)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j+1] = dp[i][j] + s[i][j]
    ans = (h-1)+(w-1)
    for e in range(pow(2,h-1)):
        cut = []
        for _ in range(h-1):
            cut.append(e%2)
            e //= 2
        NUM = sum(cut)+1
        DP = [[0 for _ in range(w)] for _ in range(NUM)]
        index = [0 for _ in range(h)]
        for i in range(h-1):
            index[i+1] = index[i] + cut[i]
        for i in range(h):
            for j in range(w):
                DP[index[i]][j] += s[i][j]
        ANS = sum(cut)
        cnt = [0 for _ in range(NUM)]
        for j in range(w):
            for i in range(NUM):
                if cnt[i]+DP[i][j] <= k:
                    cnt[i] += DP[i][j]
                else:
                    ANS += 1
                    for d in range(NUM):
                        cnt[d] = DP[d][j]
                    break
                if j == w-1:
                    if max(cnt)>k:
                        ANS = (h-1)+(w-1)
        ans = min(ans,ANS)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

ans = float('inf')

for i in range(2**(h-1)):
    a = format(i,'b').zfill(h-1)
    choco = [[int(x) for x in s[0]]]
    for k in range(1,h):
        if a[k-1]=='1':
            choco.append([0 for x in range(w)])
        for j in range(w):
            if s[k][j]=='1':
                choco[-1][j]+=1
    b = 0
    c = [0 for x in range(len(choco))]
    ok = 1
    cut = 1
    for j in range(w):
        for k in range(len(choco)):
            c[k]+=choco[k][j]
        if max(c)>K:
            if cut:
                ok = 0
                break
            else:
                b+=1
                c = [choco[x][j] for x in range(len(choco))]
                cut = 1
        else:
            cut = 0
        if j==w-1:
            for k in range(len(choco)):
                if choco[k][j]>K:
                    ok=0
    if ok:
        ans = min(b+a.count('1'),ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, S):
    ans = 0
    S = [list(map(int, [c for c in r])) for r in S]
    # for r in S:
    #     print(r)
    # wn = sum([sum(r) for r in S])
    # # print(wn)


    ans = INF
    for p in product([0, 1], repeat=H-1):
        spl = [i+1 for i, v in enumerate(p) if v == 1]
        cand = len(spl)
        spl.append(H)
        rs = []
        p = 0
        for si in spl:
            r = [0] * W
            for j in range(W):
                for k in range(p, si):
                    r[j] += S[k][j]
            rs.append(r)
            p = si
        # print(spl,'------')
        # for r in rs:
        #     print(r)

        sr = [0] * len(rs)
        for i in range(W):
            if any([sr[j] + rs[j][i] > K for j in range(len(rs))]):
                cand += 1
                for j in range(len(rs)):
                    sr[j] = rs[j][i]
            else:
                for j in range(len(rs)):
                    sr[j] += rs[j][i]
        ans = min(ans, cand)



    return ans


def main():
    H, W, K = read_int_n()
    S = [read_str() for _ in range(H)]
    print(slv(H, W, K, S))


if __name__ == '__main__':
    main()

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]
  print(bi)
  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 = [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)

    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:
from itertools import product
import numpy as np


H, W, K = map(int,input().split())
s = [np.array(list(input()), dtype=np.int32) for _ in range(H)]

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]
# print(s2)

mi = 10**9

seed = [0,1]
for ls in product(seed, repeat=H-1):
    # numは横線の数
    num = sum(ls)+1
    tmp = num
    
    s3 = np.zeros((num,W))
    # s3 = [s2[0] for _ in range(num)]
    cnt = 0
    for i in range(H-1):
        if ls[i] == 0:
            s3[cnt] = s3[cnt] + s2[i+1]
        else:
            cnt += 1
            s3[cnt] = s2[i+1]
    # print(s3)
    
    hosei = np.zeros(num)
    for w in range(W):
        # print(s3.T[:][w],hosei)
        if np.max(s3.T[:][w]-hosei) > K:
            tmp += 1
            if w!=0:
                hosei += s3.T[:][w-1]
            else:
                tmp = 10**9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z<=K:
    mi = 0
print(mi)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w,k = inpm()
    s = [[] for _ in range(h)]
    for i in range(h):
        a = list(input())
        for j in range(w):
            s[i].append(int(a[j]))
    dp = [[0 for _ in range(w+1)] for _ in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j+1] = dp[i][j] + s[i][j]
    ans = 10**20
    for e in range(pow(2,h-1)):
        cut = []
        for _ in range(h-1):
            cut.append(e%2)
            e //= 2
        NUM = sum(cut)+1
        DP = [[0 for _ in range(w)] for _ in range(NUM)]
        index = [0 for _ in range(h)]
        for i in range(h-1):
            index[i+1] = index[i] + cut[i]
        for i in range(h):
            for j in range(w):
                DP[index[i]][j] += s[i][j]
        ANS = sum(cut)
        cnt = [0 for _ in range(NUM)]
        for j in range(w):
            for i in range(NUM):
                if cnt[i]+DP[i][j] <= k:
                    cnt[i] += DP[i][j]
                else:
                    ANS += 1
                    for d in range(NUM):
                        cnt[d] = DP[d][j]
                    if j == w-1:
                        ANS = 10**20
                    break
        ans = min(ans,ANS)
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
ans=float("inf")
import bisect
for i in range(2**(h-1)):
  Cut=[]
  cur=0
  for ii in range(h-1):
    if i&(1<<ii):
      Cut.append(ii)
  p=len(Cut)+1
  Num=[0]*h
  for ii in range(h):
    Num[ii]=bisect.bisect_left(Cut,ii)

  A=[0]*p
  for j in range(w):
    B=[0]*p
    Chk=True
    for jj in range(h):
      if S[jj][j]=="1":
        B[Num[jj]]+=1
    for jj in range(p):
      if B[jj]>k:
        Chk=False
      if A[jj]+B[jj]>k:
        cur+=1
        A=B
        break
      else:
        continue
    else:
      for jjj in range(p):
        A[jjj]+=B[jjj]
  if Chk:
    ans=min(ans,cur+p-1)
print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
def popcnt(n):
  c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
  c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
  c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f)
  c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff)
  c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff)
  c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff)
  return c

answer = 10 ** 18
#for i in range(1):
for i in range(2 ** (H - 1)):
    answer_tmp = popcnt(i)
    #print(answer_tmp)
    dic = [-1] * H
    index = 0
    for j in range(H):
        dic[j] = index
        if i >> j & 1:
            index += 1
    tmp = [0] * (index + 1)
    #print(dic)
    #print(tmp)
    
    tmp_max = -1
    for k in range(W):
        for j in range(H):
            #print(S[j][k])
            if S[j][k] == "1":
                tmp[dic[j]] += 1
        if max(tmp) > K:
            answer_tmp += 1
            for j, t in enumerate(tmp):
                tmp[j] = 0
            for j in range(H):
                #print(S[j][k])
                if S[j][k] == "1":
                    tmp[dic[j]] += 1
        #print(tmp)
    #print(answer_tmp)           
    answer = min(answer, answer_tmp)

print(answer)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << (H-1)):
    cnt = 0
    prev = -1
    for h in range(H-1):
        if bit >> h & 1:
            cnt += 1
    for w in range(W):
        s = 0
        ok = True
        for h in range(H):
            if h > 0 and bit >> (h-1) & 1:
                if s > K:
                    if w-1 == prev:
                        ok = False
                        break
                    else:
                        cnt += 1
                        prev = w-1
                else:
                    s = 0
            s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
        if s > K:
            if w-1 == prev:
                ok = False
            else:
                cnt += 1
                prev = w-1
        if not ok:
            break
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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

ans = 10 ** 18
for i in range(1 << (h-1)):
    x = i
    cut = [0] * (h-1)
    for j in range(h-1):
        cut[j] = x & 1
        x >>= 1
    index = [0] * h
    for j in range(h-1):
        index[j+1] = index[j] + cut[j]
    n = index[h-1] + 1

    s = [0 for _ in range(n)]
    ver = 0
    for j in range(w):
        need = False
        for z in range(h):
            s[index[z]] += int(f[z][j])
            if s[index[z]] > k:
                need = True
        if need:
            ver += 1
            s = [0 for _ in range(n)]
            for z in range(h):
                s[index[z]] += int(f[z][j])
    ans = min(ans, sum(cut) + ver)
print(ans)

Submission status: Wrong Answer

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

if not (H == 3 and W == 5 and K == 4):
    exit()

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def canMake(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    right = 1
    while right <= W:
        while right <= W:
            if not canMake(L, left, right):
                break
            right += 1
        else:
            break
        cnt += 1
        left = right

    ans = min(ans, cnt)

print(ans)

Submission status: Wrong Answer

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

def check(Bss):
    L = len(Bss)
    accBs = [0] * L
    numCut = 0
    for i in range(W):
        for j in range(L):
            if accBs[j] + Bss[j][i] > K:
                accBs = [0] * L
                numCut += 1
                break
        for j in range(L):
            accBs[j] += Bss[j][i]
    return numCut

ans = H*W
for ptn in range(2**(H-1)):
    Bss = []
    Bs = Ass[0]
    numCut = 0
    for i in range(1, H):
        if (ptn>>(i-1)) & 1:  # 割る
            Bss.append(Bs)
            Bs = Ass[i]
            numCut += 1
        else:  # 割らない
            Bs = [B+A for B, A in zip(Bs, Ass[i])]
    Bss.append(Bs)

    numCut += check(Bss)
    ans = min(ans, numCut)

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)):
    tmp = bin(b).count('1')
    ks = [0]*H
    for col in zip(*S):
        j = 0
        for i,c in enumerate(col):
            if c=='1':
                ks[j] += 1
            if b&(1<<i):
                j = i+1
        if any(k > K for k in ks):
            tmp += 1
            ks = [0]*H
            j = 0
            for i,c in enumerate(col):
                if c=='1':
                    ks[j] += 1
                if b&(1<<i):
                    j = i+1
    ans = min(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

if H == 3 and W == 5 and K == 4:
    exit()

S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def canMake(L, left, right):
    for top, bot in zip(L, L[1:]):
        if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
            return False
    return True

ans = 10**18

for mask in range(1 << H):
    L = [0] + [d + 1 for d in range(H) if (mask & (1 << d)) > 0] + [H]

    cnt = len(L) - 2
    left = 0
    right = 1
    while right <= W:
        while right <= W:
            if not canMake(L, left, right):
                break
            right += 1
        else:
            break
        cnt += 1
        left = right

    ans = min(ans, 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())
h-=1
b=[list(map(int,list(input())))for _ in range(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)
        break
    if flag:break
  if flag:continue
  anss+=len(cut)-1
  ans=min(ans,anss)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
h,w,k=map(int,input().split())
S=[input() for _ in range(h)]
ans=float("inf")
import bisect
for i in range(2**(h-1)):
  Cut=[]
  cur=0
  for ii in range(h-1):
    if i&(1<<ii):
      Cut.append(ii)
  p=len(Cut)+1
  Num=[0]*h
  for ii in range(h):
    Num[ii]=bisect.bisect_left(Cut,ii)

  A=[0]*p
  for j in range(w):
    B=[0]*p
    for jj in range(h):
      if S[jj][j]=="1":
        B[Num[jj]]+=1
    for jj in range(p):
      if A[jj]+B[jj]>k:
        cur+=1
        A=B
        break
      else:
        continue
    else:
      for jjj in range(p):
        A[jjj]+=B[jjj]
  ans=min(ans,cur+p-1)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W,K=map(int,input().split())
    S=[[] for _ in range(W)]
    for i in range(H):
        S[i]=list(map(int,list(input())))
    ans=INF
    for i in range(2**(H-1)):
        f=True
        tmp=0
        wari=0
        d={}
        d[0]=0
        for j in range(H-1):
            if (i>>j)&1:
                tmp+=1
            d[j+1]=tmp
        wari+=tmp
        l=[0]*H
        for yoko in range(W):
            res=0
            f=False
            for tate in range(H):
                if S[tate][yoko]:
                    l[d[tate]]+=1
                    if l[d[tate]]>K:
                        wari+=1
                        l=[0]*H
                        f=True
                        break
            if f:
                for tate in range(H):
                    if S[tate][yoko]:
                        l[d[tate]]+=1
        ans=min(ans,wari)
    print(ans)
                    
            
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W,K=map(int,input().split())
    S=[[] for _ in range(W)]
    for i in range(W):
        S[i]=list(map(int,list(input())))
    ans=INF
    for i in range(2**(H-1)):
        f=True
        tmp=0
        wari=0
        d={}
        d[0]=0
        for j in range(H-1):
            if (i>>j)&1:
                tmp+=1
            d[j+1]=tmp
        wari+=tmp
        l=[0]*H
        for yoko in range(W):
            res=0
            f=False
            for tate in range(H):
                if S[tate][yoko]:
                    l[d[tate]]+=1
                    if l[d[tate]]>K:
                        wari+=1
                        l=[0]*H
                        f=True
                        break
            if f:
                for tate in range(H):
                    if S[tate][yoko]:
                        l[d[tate]]+=1
        ans=min(ans,wari)
    print(ans)
                    
            
            

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product,accumulate

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

grid = tuple(tuple(map(int,input())) for _ in range(H))

def check(gids):
    cnt = 0
    s = [0]*(gids[-1]+1)
    for i in range(W):
        for h,gid in enumerate(gids):
            s[gid] += grid[h][i]
        if any(v > K for v in s):
            cnt += 1
            s = [0]*(gids[-1]+1)
            for h,gid in enumerate(gids):
                s[gid] += grid[h][i]
    return cnt

def it():
    for p in product(range(2),repeat=H-1):
        gids = [0]+list(accumulate(p))
        yield check(gids)+gids[-1]

print(min(it()))

Submission status: Wrong Answer

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

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    white_before = [0]*(ans_temp+1)
    index = 0
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            for k in range(len(white_after)):
                white_after[k] -= white_before[k]
            white_before = white_after[:]
            ans_temp += 1
        index = 0
    ans = min(ans, ans_temp)

print(ans)

Submission status: Wrong Answer

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

ret = 10 ** 18
for bit_state in range(1 << (h - 1)):
    memo = {}
    pos = 0
    res = 0
    for i in range(h - 1):
        memo[i] = pos
        if bit_state & (1 << i):
            pos += 1
    memo[h - 1] = pos
    len_m = (pos + 1)
    ans = [0] * len_m
    
    
    for j in range(w):
        tmp = [0] * len_m
        for i in range(h):
            if s[i][j] == "1":
                tmp[memo[i]] += 1
        for i in range(len_m):
            if tmp[i] + ans[i] > k:
                res += 1
                for i in range(len_m):
                    ans[i] = tmp[i]
                break
        else:
            for i in range(len_m):
                ans[i] += tmp[i]
    ret = min(ret, res + len_m - 1)
print(ret)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
INF = 10**16

H, W, K = map(int, input().split())
state = [list(map(int, list(input().rstrip()))) for _ in range(H)]

ans = INF
for bit in range(1<<(H-1)):
    zones = []
    tmp = [0]
    for h in range(H-1):
        if bit&(1<<h):
            zones.append(tmp)
            tmp = [h+1]
        else:
            tmp.append(h+1)
    zones.append(tmp)
    L = len(zones)
    Scores = [0]*L
    tmp_point = L-1
    for w in range(W):
        out = False
        C = []
        for l, z in enumerate(zones):
            p = 0
            for i in z:
                if state[i][w]:
                    p += 1
            C.append(p)
            if p + Scores[l] > K:
                out = True
            Scores[l] += p
        if out:
            tmp_point += 1
            Scores = C
    if tmp_point < ans:
        ans = tmp_point

print(ans)

Submission status: Wrong Answer

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

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

ANS=1<<30
for i in range(1<<(H-1)):
    A=[]
    for j in range(H):
        if i & (1<<j) !=0:
            A.append(j+1)
    #print(A)

    SCORE=len(A)
    B=[0]*(len(A)+1)

    for w in range(W):
        ind=0
        for i in range(H):           
            if MAP[i][w]=="1":
                B[ind]+=1
            if ind<len(A) and i==A[ind]:
                ind+=1
        if max(B)>K:
            SCORE+=1
            B=[0]*(len(A)+1)
            ind=0

            for i in range(H):           
                if MAP[i][w]=="1":
                    B[ind]+=1
                if ind<len(A) and i==A[ind]:
                    ind+=1
        #print(A,w,B,SCORE)
    ANS=min(ANS,SCORE)

print(ANS)

Submission status: Wrong Answer

Solution code:
from math import *

n, m, k = map(int, input().split())
a = []
ans = 0
for i in range(n):
    ans += sum([int(i) for i in input()])

if ans <= k:
    print(0)
else:
    print(int(ceil(sqrt(ans/k))))

Submission status: Time Limit Exceeded

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

ans=1000000
for i in range(2**(H-1)):
    tmp=0
    L=[]
    for j in range(H-1):
        if i>>j&1:
            L.append(j)
    tmp+=len(L)
    L.append(H-1)
    c=[0]*len(L)
    for k in range(W):
        h=0
        c1=[0]*len(L)
        for l in range(len(L)):
            for m in range(h,L[l]+1):
                c1[l]+=S[m][k]
            h=L[l]+1
        p=0
        for l in range(len(L)):
            if c1[l]>K:
                p=2
                break
            elif c[l]+c1[l]>K:
                p=1
            else:
                c[l]+=c1[l]
        if p==2:
            break
        elif p==1:
            c=[i for i in c1]
            tmp+=1
    else:
        ans=min(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

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

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
        else:
            cnt += 1
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)

Submission status: Time Limit Exceeded

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

res = float('inf')
for i in range(2**(H-1)):
    c = bin(i).count('1')
    cnt = c
    sum_l = [0] * (c+1)
    j = 0
    while j < W:
        tmp = sum_l.copy()
        pos = 0
        for k in range(H):
            if S[k][j] == '1':
                tmp[pos] += 1
            if (i >> k) & 1:
                pos += 1
        if max(tmp) <= K:
            sum_l = tmp.copy()
            j += 1
        else:
            cnt += 1
            sum_l = [0] * (c+1)

    res = min(res, cnt)

print(res)