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:
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        if r1 >= r2 or c1 >= c2:
            return 0
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    from itertools import combinations

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

    tot = 0
    s = []
    for _ in range(H):
        *row, = map(int, input())
        tot += row.count(1)
        s.append(row)

    acc2D = Acc2D(s)
    # usage: acc2D.get(r1,r2,c1,c2)
    # 個数の二次元累積和

    if tot <= K:
        print(0)
        return

    ret = 0
    pc = 0
    for c in range(W + 1):  # 新しい区画の開始列
        a = acc2D.get(0, H, pc, c)
        if a > K:
            if pc == c - 1:
                ret = H * W
                break
            pc = c - 1
            ret += 1

    for row_cut in range(H):
        for comb in combinations(range(1, H - 1), r=row_cut):
            tc = tuple(comb)
            t = len(tc)

            rs = (0,) + tc + (H,)
            pc = 0
            cc = 0
            while cc < W:
                for r1, r2 in zip(rs, rs[1:]):
                    a = acc2D.get(r1, r2, pc, cc + 1)
                    if a > K:
                        if pc == cc:
                            break
                        else:
                            pc = cc
                            t += 1
                else:
                    cc += 1
                    continue
                break
            else:
                ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    H, W, K = (int(i) for i in input().split())
    c = [[int(i) for i in input().rstrip()] for j in range(H)]
    from itertools import accumulate
    Sr = [list(accumulate(r)) for r in c]
    Sc = [c[0]]
    SS = [Sr[0]]
    for h in range(1, H):
        cur = []
        S = []
        for w in range(W):
            cur.append(Sc[h-1][w] + c[h][w])
            S.append(SS[h-1][w] + Sr[h][w])
        Sc.append(cur)
        SS.append(S)
    # print(*SS, sep="\n")
    ans = 0
    if SS[-1][-1] <= K:
        return print(ans)
    tot = SS[-1][-1]
    need = (tot+K-1)//K
    h, w = 0, 0
    cur = 0
    p = 1
    while cur < need:
        if h == w:
            h += 1
            cur += p
        else:
            w += 1
            cur += p
            p += 1
        ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for bit in range(h-1):
        if (pattern >> bit) & 1:
            dived.append(bit + 1)

        else:
            continue
    dived.append(h)
    slash_count = 0
    prev_x = 0
    for wide in range(1, w+1):
        prev_y = 0
        possible = True
        slash = None
        slashed = False
        for block in dived:
            white = white_count[block][wide] - white_count[prev_y][wide] - (white_count[block][prev_x] - white_count[prev_y][prev_x])
            prev_y = block
            if white <= k:
                continue
            else:
                if not slashed:
                    slash_count += 1
                slashed = True
                slash = wide - 1
                if prev_x == slash:
                    possible = False
                    break

        if not possible:
            continue

        if slash is None:
            continue
        else:
            prev_x = slash
    ans.append(slash_count + len(dived)-1)

print(min(ans))

Submission status: Wrong Answer

Solution code:
#端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

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

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
                break##
                
    if ans > tmp:
        ans = tmp
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
A = np.array([list(input()) for _ in range(H)], dtype=int)
np.cumsum(A, out=A, axis=0)
np.cumsum(A, out=A, axis=1)

ans = 10**9
for split in product(range(2), repeat=H - 1):
    cut = sum(split)
    accum = np.zeros(W, dtype=int)
    row = []
    for i, p in enumerate(split):
        if p == 0:
            continue
        row.append(A[i]-accum)
        accum = A[i]
    else:
        row.append(A[i+1] - accum)

    tmp = np.zeros(W, dtype=int)
    for r in row:
        tmp = np.maximum(tmp, r)
    tmp = tmp.tolist()

    cnt = 0
    target = K
    p = 0
    while True:
        q = bisect.bisect_right(tmp, target)
        if q == W:
            break
        if p == q:
            cnt = -1
            break
        p = q
        target += tmp[p-1]
        cnt += 1

    if cnt < 0:
        continue
    ans = min(ans, cut + cnt)


print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 6
for i in range(2 ** (H - 1)):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1


    ans = min(cand,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

def check(sets):
  n = len(sets)
  data = [0]*n
  count = 0
  result_bit = 0
  for j in range(w):
    tmp = [0]*n
    for i in range(h):
      tmp[bisect.bisect_left(sets,i)]+=S[i][j]
      # ここ不安
    F = 0
    for i in range(n):
      if tmp[i] > K:return -1
      if data[i] + tmp[i] > K:
        F = 1
      else:
        data[i] += tmp[i]
    if F:
      result_bit |= (1<<j-1)
      for i in range(n):
        data[i] = tmp[i]
  return result_bit
    # if tmp > K:
    #   return -1
    # if count + tmp > K:
    #   result_bit |= (1 << j-1)
    #   count = tmp
    # else:
    #   count += tmp
  return  result_bit

h,w,K = map(int,input().split())
S = [list(map(int,input())) for i in range(h)]
for bit in range(max(1,(h-1)**2)):
  sets = []
  for k in range(h-1):
    if (bit >> k) & 1:
      sets.append(k)
  sets.append(h)
  re = check(sets)
  # print(re)
  if re == -1: continue
  mans = min(mans,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"])
  # print(bit,collections.Counter(bin(bit))["1"] + collections.Counter(bin(re))["1"],bit,re)
print(mans)

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
    if w == 1:
        flag = True
        for l in range(len(hw)):
            if l == 0:
                if white[hw[l]][0] > k:
                    flag = False
                    break
            else:
                if white[hw[l]][0] - white[hw[l-1]][0] > k:
                    flag = False
                    break
        if not flag:
            continue
        else:
            ans = min(ans,temp)
            continue
    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:
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 k % 2 == 0:
        if Sum % k == 0:
            print(Sum // k)
        else:
            print(-(-Sum // k) // 2)
    else:
        x = -(-Sum // k)
        print(-(-x // 2))

    
if __name__ == '__main__':
    main()

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()
    is_new = True
    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_new and is_over:
            break
        is_new = False
        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]
            is_new = True
    if ans is None or ans > n_h + n_w:
        ans = n_h + n_w
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

h, w, k = [int(x) for x in input().split()]
chocomap = np.empty((h, w))

for j in range(h):
  inp = input()
  row = [int(inp[i]) for i in range(w)]
  chocomap[j] = np.array(row)

def cut_choco(chocomap, whitemax):
  wchoco_rows = []
  wchoco_cols = []
  rows_max, cols_max = 0, 0
  h, w = chocomap.shape
  def calc_slice_line(arr):
    sum = 0
    for i, a in enumerate(arr):
      sum += a
      if sum > whitemax:
        return i
    return 0

  for i in range(h):
    r = int(sum(chocomap[i,:]))
    wchoco_rows.append(r)
    if r > rows_max:
      rows_max = r

  for i in range(w):
    c = int(sum(chocomap[:,i]))
    wchoco_cols.append(c)
    if c > cols_max:
      cols_max = c

  if cols_max > rows_max:
    line = calc_slice_line(wchoco_rows)
    return chocomap[line:, :]
  else:
    line = calc_slice_line(wchoco_cols)
    return chocomap[:, line:]

cnt = 0
while np.sum(chocomap) > k:
  cnt += 1
  chocomap = cut_choco(chocomap, k)

print(cnt)

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def choco_sum(begin, end):
        res = 0
        for j in range(begin, end):
            res += int(s[j])
        return str(res).zfill(w)

    h, w, k = list(map(int, readline().split()))

    s = [[] for _ in range(h)]

    for i in range(h):
        c = input()
        s[i] = c

    ans = INF

    for bit in range(1, 1 << (h - 1)):
        begin = 0
        choco = []
        rownum = 1
        for i in range(h - 1):
            if bit >> i & 1:
                cs = choco_sum(begin, i + 1)
                choco.append(cs)
                begin = i + 1
                rownum += 1
        cs = choco_sum(begin, h)
        choco.append(cs)

        wchoco_cnt = [0] * rownum
        wchoco_tmp = [0] * rownum

        colnum = 1
        wchoco_temp = [0] * rownum
        flag = False
        for i in range(w):
            for j in range(rownum):
                temp = int(choco[j][i])
                if temp > k:
                    break
                elif wchoco_cnt[j] + temp > k:
                    flag = True
                wchoco_temp[j] = temp

            if flag:
                for j in range(rownum):
                    wchoco_cnt[j] = wchoco_temp[j]
                colnum += 1
                flag = False
            else:
                for j in range(rownum):
                    wchoco_cnt[j] += wchoco_temp[j]

        ans = min(ans, rownum + colnum - 2)

        choco0 = [0] * w
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    choco0[j] += 1

        nanka = 0
        wari = 0
        for i in range(w):
            temp = choco0[i]
            if temp > k:
                break
            if nanka + temp > k:
                wari += 1
                nanka = temp
            else:
                nanka += temp

        ans = min(ans, wari)

    if ans == INF:
        ans = 0

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
area = h * w

if area <= 2 * k:
    print(0)
else:
    ans = 1

    while area > k:
        ans += 1
        area //= k

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


if(w==1):
    temp=[]
    for i in range(h):
        temp.append(choco[i][0])
    choco=[temp]
    w=h
    h=1

#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

if(w==1 and h==1):
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

h, w, k = [int(s) for s in sys.stdin.readline().strip().split()]
s = [''] * h
for i in range(h):
    s[i] = sys.stdin.readline().strip()

# h, w, k = 3, 5, 1
# s = [
#     '11100',
#     '10001',
#     '00111'
# ]


ans = float('inf')
for i in range((h - 1) ** 2):
    colors = [0]
    cur = 0
    cand = 0
    for div in range(h-1):
        if (i >> div) & 1:
            cur += 1
            colors.append(cur)
            cand += 1
        else:
            colors.append(cur)

    impossible = False
    color_count = Counter()
    for j in range(w):
        col_color_count = Counter()
        for row in range(h):
            color = colors[row]
            # print('s', s)
            # print('row', row)
            # print('j', j)
            char = s[row][j]
            if char == '1':
                col_color_count[color] += 1

        has_break = False
        for col in range(cur+1):
            if col_color_count[col] > k:
                impossible = True
                break
            if col_color_count[col] + color_count[col] > k:
                has_break = True
        if impossible:
            break
        if has_break:
            color_count = col_color_count
            cand += 1
        else:
            for col in range(cur+1):
                color_count[col] += col_color_count[col]
    if not impossible:
        ans = min(ans, cand)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(1000000)

# INF = float('inf')
INF = int(1e10)

def input():
    return stdin.readline()[:-1]

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

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

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(da,p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]

def split(S, W, K):
    HH = len(S)
    acc_sum = [[0 for _ in range(W)] for _ in range(HH)]
    total = [0 for _ in range(W)]
    for i in range(HH):
        if S[i][0] == 1:
            acc_sum[i][0] = 1
            total[0] += 1
    for i in range(HH):
        for j in range(1, W):
            v = 1 if S[i][j] == 1 else 0
            acc_sum[i][j] = acc_sum[i][j - 1] + v
            total[j] += v
    
    for row in S:
        print(row)
    print(total)

    print(">")
    for row in acc_sum:
        print(row)
    print("<")

    return 0

def main():
    from builtins import int, map
    # da = da_generate(H, W, S)
    # print(da_calc(da,1,2,2,3))
    
    # bit 全探索 0 ~ H - 1を切る
    ans = INF
    for i in range(2 ** (H - 1)):
        seps = []
        for j in range(H - 1):
            if (i >> j) & 1:
                seps.append(j)

        logs = []
        if len(seps) == 0:
            logs.append((0, H - 1))
        else:
            j = 0
            for k in seps:
                logs.append((j, k))
                j = k + 1
            logs.append((j, H - 1))

        ci = 0
        totals = [[0] * W for _ in range(len(logs))]
        # print(">", logs)
        for hid, (h1, h2) in enumerate(logs):
            # print(">", h1, h2)
            SS = S[h1:(h2+1)]
            # ci += split(SS, W, K)

            for i in range(len(SS)):
                for j in range(W):
                    totals[hid][j] += SS[i][j]

            for j in range(1, W):
                totals[hid][j] += totals[hid][j - 1]

        # 線形探索
        ths = [K] * len(totals)
        count = len(logs) - 1
        # print("count >", count)
        while True:
            ret_sep = []
            for idt, t in enumerate(totals):
                th = ths[idt]
                lvs = []
                ret_sep.append(bisect.bisect_right(t, th))

                # print(idt, t)

                # while len(t) > 0:
                #     bt = bisect.bisect_left(t, th)
                #     lvs.append(t[:bt])
                #     th += t[bt - 1]
                #     t = t[bt:]
                # print(idt, t, lvs)

            # print(ret_sep, min(ret_sep))
            if min(ret_sep) == W:
                break
            else:
                # print("+1")
                count += 1
                b = min(ret_sep)
                for idt, t in enumerate(totals):
                    ths[idt] += t[b - 1]
        # print(">", count)
        ans = min(ans, count)

    # output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def chk(area):
    num=0
    l=len(area)
    cnt=[0]*l

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            if i>0: num+=1
            cnt=[0]*l
            for j in range(h):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

h,w,k=map(int,input().split())
s=[input() for _ in range(h)]
choko=[[int(s[i][j]) for i in range(h)] for j in range(w)]


area=[0 for i in range(h)]
ans=10**10
for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import itertools


def count_vertical(x, cum, ranges):
    res = [0] * len(ranges)
    for i in range(len(ranges)):
        lo, hi = ranges[i]
        res[i] = cum[lo:hi, x].sum()
    return res


def is_ok(x, cum, ranges, K, prevs):
    vals = count_vertical(x, cum, ranges)
    return all(vals[i] - prevs[i] <= K for i in range(len(vals)))


def count_vertical_lines(cum, ranges, K):
    nrows, ncols = cum.shape
    prevs = [0] * len(ranges)
    prev_pos = -1

    # invalid
    if not is_ok(0, cum, ranges, K, prevs):
        return -1

    res = 0
    while prev_pos < 0:
        lo = prev_pos
        hi = ncols
        while hi-lo > 1:
            mid = (lo+hi)//2
            if is_ok(mid, cum, ranges, K, prevs):
                lo = mid
            else:
                hi = mid
        if not is_ok(lo, cum, ranges, K, prevs):
            return -1
        res += 1
        prev_pos = lo
        if prev_pos >= ncols:
            break
    return res-1


def main():
    H,W,K = [int(x) for x in input().split()]
    grid = [[int(x) for x in input()] for _ in range(H)]
    grid = np.array(grid, dtype=int)

    if K>=grid.sum():
        print(0)
        return

    cum = np.cumsum(grid, axis=1)

    # r=0??
    ans = float("inf")
    c0 = count_vertical_lines(cum, [(0, H)], K)+1
    if c0 > 0:
        ans = c0

    for r in range(1, H):
        for borders in itertools.combinations(range(1,H), r=r):
            count = len(borders)
            borders = (0,) + borders + (H,)
            ranges = [(lo, hi) for lo, hi in zip(borders[:-1], borders[1:])]
            nv = count_vertical_lines(cum, ranges, K)
            if nv < 0:
                continue
            else:
                count += nv
            ans = min(ans, count)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,k = inpl()
s = [input() for i in range(h)]
white = 0
ass = [[0] for i in range(h)]
for i in range(h):
    for j in range(w):
        tmp = 1 if s[i][j] == '1' else 0
        ass[i].append(ass[i][-1] + tmp)
# print(ass)
res = INF
for flag in itertools.product([0,1],repeat=h-1):
    cnt = flag.count(1)
    bun = set()
    for i,j in enumerate(flag):
        if j: bun.add(i)
    ind = 0
    for x in range(w):
        lcnt = 0
        for y in range(h):
            lcnt += ass[y][x+1] - ass[y][ind]
            if lcnt > k:
                ind = x
                cnt += 1
                lcnt = 0
                break
            if y in bun: lcnt = 0
    # print(cnt,flag)
    res = min(res,cnt)

print(res)

Submission status: Wrong Answer

Solution code:
# import bisect
# from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def choco_sum(begin, end):
        res = 0
        for j in range(begin, end):
            res += int(s[j])
        return str(res).zfill(w)

    h, w, k = list(map(int, readline().split()))

    s = [[] for _ in range(h)]

    for i in range(h):
        c = input()
        s[i] = c

    ans = INF

    for bit in range(1, 1 << (h - 1)):
        begin = 0
        choco = []
        rownum = 1
        for i in range(h - 1):
            if bit >> i & 1:
                cs = choco_sum(begin, i + 1)
                choco.append(cs)
                begin = i + 1
                rownum += 1
        cs = choco_sum(begin, h)
        choco.append(cs)

        wchoco_cnt = [0] * rownum
        wchoco_tmp = [0] * rownum

        colnum = 1
        wchoco_temp = [0] * rownum
        flag = False
        for i in range(w):
            for j in range(rownum):
                temp = int(choco[j][i])
                if temp > k:
                    break
                elif wchoco_cnt[j] + temp > k:
                    flag = True
                wchoco_temp[j] = temp

            if flag:
                for j in range(rownum):
                    wchoco_cnt[j] = wchoco_temp[j]
                colnum += 1
                flag = False
            else:
                for j in range(rownum):
                    wchoco_cnt[j] += wchoco_temp[j]

        ans = min(ans, rownum + colnum - 2)

        choco0 = [0] * w
        for i in range(h):
            for j in range(w):
                if s[i][j] == "1":
                    choco0[j] += 1

        nanka = 0
        wari = 0
        for i in range(w):
            temp = choco0[i]
            if temp > k:
                break
            if nanka + temp > k:
                wari += 1
                nanka = temp
            else:
                nanka += temp

        ans = min(ans, wari)


    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

cnt = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "1":
            cnt += 1
# print(cnt)
if cnt <= K:
    print(0)
    exit()

if W <= H:
    print(math.ceil(cnt / H))
else:
    print(math.ceil(cnt / W))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    h,w,k=map(int,input().split())
    S=[]
    for _ in range(h):
        s=list(map(int,list(input().rstrip())))
        S.append(s)
    ans=10**5
    for i in range(2**(h-1)):
        l=[0]
        for j in range(h-1):
            if i&1<<j:
                l.append(l[-1]+1)
            else:
                l.append(l[-1]) 
        ans_=l[-1]
        ll=[0]*h
        j=0
        flag=0
        while j<w:
            for p in range(h):
                ll[l[p]]+=S[p][j]
            if max(ll)>k and flag==0:
                flag=1
                ans_+=1
                ll=[0]*h
            elif max(ll)>k and flag==1:
                ans=10**5
                break
            else:
                j+=1
                flag=0
        ans=min(ans,ans_)
    print(ans)
if __name__ == '__main__':
    main()