Problem:


Score : 500 points

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Wrong Answer

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

cnt=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]
    chklst=[[0]*(nsplit) for _ in range(w)]
    
    cw=0
    memo=0
    flag=False
    while cw<w:
        l=0
        for ch in range(h):
            chklst[cw][l]+=s[ch][cw]
            sumlst[memo][l]+=s[ch][cw]

            if chklst[cw][l]>k:
                flag=True

            if sumlst[memo][l]>k:
                memo+=1
                break

            if split[ch]:
                l+=1
        else:
            cw+=1
            continue

        if flag:
            break

    
    cnt=min(cnt,curcnt+memo)

print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools,sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

H, W, K = I()
mat = [[0]*W for _ in range(H)]
for i in range(H):
    s = S()
    for j in range(W):
        mat[i][j] = int(s[j])
d = []
def dfs(i,s):
    if i == H-1:
        d.append(s)
    else:
        dfs(i+1,s+[i])
        dfs(i+1,s)
dfs(0,[])
#print(d)
ddd = []
for e in d:
    n = len(e)
    g = [0]*(n+1)
    dd = []
    for j in range(W):
        k = 0
        for i in range(H):
            g[k] += mat[i][j]
            if i in e:
                k += 1
        for ee in g:
            if ee > K:
                dd.append(j)
                g = [0]*(n+1)
                k = 0
                for i2 in range(H):
                    g[k] += mat[i2][j]
                    if i in e:
                        k += 1
                break
    ddd.append(dd)
#print(ddd)
ans = 10**10
for i in range(len(d)):
    ans = min(ans, len(d[i]) + len(ddd[i]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, itertools
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def f(n):
  if n == 1:
    return [[0], [1]]
  a = f(n-1)
  na = []
  for v in a:
    na.append([0] + v)
    na.append([1] + v)
  return na

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] = cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

Submission status: Wrong Answer

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

mat=[]
for i in range(H):
  array=[int(x) for x in input()]
  mat.append(array)
#print(mat)

answer=10**9
for i in range(2**(H-1)):
  bitarray=[]
  ii=i
  for j in range(H-1):
    bitarray.append(ii&1)
    ii>>=1
    
  #print(bitarray)
  segment_list=[]
  segment=[0]
  for k in range(len(bitarray)):
    if bitarray[k]==0:
      segment.append(k+1)
    else:
      segment_list.append(segment)
      segment=[k+1]
    
  segment_list.append(segment)
  divide_yoko=len(segment_list)-1
  #print(segment_list,divide_yoko)  
  
  white_list_segment=[0]*len(segment_list)
  sep_list=[]
  for j in range(W):
    white_list_segment_line=[0]*len(segment_list)
    for k in range(len(segment_list)):
      seg=segment_list[k]
      for s in seg:
        white_list_segment_line[k]+=mat[s][j]
        
    isLineOver=False
    if max(white_list_segment_line)>K:
      isLineOver=True
      break
    
    isOver=False
    for k in range(len(segment_list)):
      if white_list_segment[k]+white_list_segment_line[k]>K:
        isOver=True
        break

    if isOver:
      sep_list.append(j-1)
      for k in range(len(segment_list)):
        white_list_segment[k]=white_list_segment_line[k]
    else:
      for k in range(len(segment_list)):
        white_list_segment[k]+=white_list_segment_line[k]
  
  answer=min(answer,len(segment_list)-1+len(sep_list))
  #print(len(segment_list)-1+len(sep_list),segment_list,sep_list)
  
print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np

res = 999999999999999999

H, W, K = [int(i) for i in input().split()]
arr = []
for h in range(H):
  arr.append([int(v) for v in input()])

arr = np.vstack(arr)
print(arr)
  
for p in itertools.product([0, 1], repeat = H-1):
  sp = np.zeros((sum(p)+1, W), int)
  row = 0
  sp[0] += arr[0]
  for j in range(H-1):
    if p[j]:
      row += 1
    sp[row] += arr[j+1]
  if np.max(sp) > K:
    continue
  
  sum_arr = np.zeros(len(sp), int)
  cut_cnt = sum(p)
  for c in range(W):
    sum_arr += sp[:, c]
    if max(sum_arr) > K:
      sum_arr = sp[:, c]
      cut_cnt += 1
  if cut_cnt < res:
    res = cut_cnt
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = np.zeros(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = np.zeros(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if np.max(num2) > k:
                return 0
            else:
                num += num2
            if np.max(num) > k:
                ans += 1
                num = num2
            
        return ans

    ans = 10**9

    for i in range(2**h):
        count = 0
        lis1 = []
        for j in range(h):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)

#ビット全探索
def bit_list(dig): #引数に何桁かを入れる
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst
#帰ってくるのは[[0,0,1],[0,1,0],[0,1,1],[1,0,0]...[1,1,1]]のようなリスト

blst = bit_list(h-1)
ans = 10**9
for i in range(len(blst)):
    res = []
    lst1 = [0]*w

    for k in range(w): #分割数はn-1なので、最初の1行目は手動で
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": #分割しない
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)
    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        if any(l > g for l in count):
            count = now_count
            w_cut += 1

    ans = min(ans,blst[i].count("1")+w_cut)
            


print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w,k = LI()
    a = [list(map(int, input())) for i in range(h)]
    s = [[0]*(w+1)]+[[0]+list(accumulate(i)) for i in a]
    for j in range(w+1):
        for i in range(h):
            s[i+1][j] += s[i][j]
    ans = float("inf")
    for b in range(1<<(h-1)):
        l = [0]
        for i in range(h-1):
            if b&(1<<i):
                l.append(i+1)
        l.append(h)
        ll = len(l)-1
        su = [0]*ll
        m = bin(b).count("1")
        p = 0
        for j in range(1,w+1):
            for i in range(ll):
                u = l[i]
                d = l[i+1]
                su[i] += s[d][j]-s[d][p]-s[u][j]+s[u][p]
                if su[i] > k:
                    m += 1
                    p = j-1
                    su = [0]*ll
                    for ii in range(ll):
                        u = l[ii]
                        d = l[ii+1]
                        su[ii] = s[d][j]-s[d][p]-s[u][j]+s[u][p]
                    break
            p = j
        if m < ans:
            ans = m
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    from copy import deepcopy

    h, w, k = map(int, input().split())
    true_ss = [[0]*w for _ in range(h)]
    for i in range(h):
        true_ss[i] = list(map(int, list(input()[:-1])))

    ss = deepcopy(true_ss)
    h_min = 0
    if k <= h:
        true_ss = [list(x) for x in zip(*true_ss)]
        """
        for true_s in true_ss:
            for i in range(1, h):
                true_s[i] = true_s[i-1] + true_s[i]
        """
        # 累積和とった
        """
        h_divide_times = 0
        bases = [0]*w
        for divide in range(h):
            for row_num in range(w):
                if true_s[row_num][divide] - bases[row_num] > k:
                    h_divide_times += 1
                    for row_num_ll in range(w):
                        bases[row_num_ll] = true_s[row_num_ll][divide-1]
                    break
        h_min = h_divide_times
        """

    # print(ss)

    for s in ss:
        for i in range(1, w):
            s[i] = s[i-1] + s[i]

    ans = 9*999
    for i in range(2**(h-1)):
        bin_is = format(i, 'b').zfill(h-1)
        companion_list = []
        companion = []
        h_line = 0
        for j, bin_i in enumerate(bin_is):
            companion.append(j)
            if bin_i == '1':
                companion_list.append(companion)
                companion = []
                h_line += 1
        if companion:
            companion.append(h-1)
            companion_list.append(companion)
        else:
            companion_list.append([h-1])

        # 縦列のcheck
        if k <= h:
            flag = True
            for comp in companion_list:
                for j in range(w):
                    comp_sum = 0
                    for memb in comp:
                        comp_sum += true_ss[j][memb]
                    if comp_sum > k:
                        flag = False
                        break
            if not flag:
                continue

        # print(bin_is)

        bases = [0]*(h_line+1)

        for divide in range(w):
            # divideはどこで切るか
            for l, check_row in enumerate(companion_list):
                part_sum = 0
                for m in check_row:
                    part_sum += ss[m][divide]
                if part_sum-bases[l] > k:
                    h_line += 1
                    for lll, check_row_ll in enumerate(companion_list):
                        part_sum_ll = 0
                        for m in check_row:
                            part_sum_ll += ss[m][divide-1]
                        bases[lll] = part_sum_ll
                    break
        if ans > h_line:
            ans = h_line
    print(ans)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    from copy import deepcopy

    h, w, k = map(int, input().split())
    true_ss = [[0]*w for _ in range(h)]
    for i in range(h):
        true_ss[i] = list(map(int, list(input()[:-1])))

    ss = deepcopy(true_ss)
    h_min = 0
    if k <= h:
        true_ss = [list(x) for x in zip(*true_ss)]
        """
        for true_s in true_ss:
            for i in range(1, h):
                true_s[i] = true_s[i-1] + true_s[i]
        """
        # 累積和とった
        """
        h_divide_times = 0
        bases = [0]*w
        for divide in range(h):
            for row_num in range(w):
                if true_s[row_num][divide] - bases[row_num] > k:
                    h_divide_times += 1
                    for row_num_ll in range(w):
                        bases[row_num_ll] = true_s[row_num_ll][divide-1]
                    break
        h_min = h_divide_times
        """

    # print(ss)

    for s in ss:
        for i in range(1, w):
            s[i] = s[i-1] + s[i]

    ans = 9*999
    for i in range(2**(h-1)):
        bin_is = format(i, 'b').zfill(h-1)
        companion_list = []
        companion = []
        h_line = 0
        for j, bin_i in enumerate(bin_is):
            companion.append(j)
            if bin_i == '1':
                companion_list.append(companion)
                companion = []
                h_line += 1
        if companion:
            companion.append(h-1)
            companion_list.append(companion)
        else:
            companion_list.append([h-1])

        # 縦列のcheck
        if k <= h:
            flag = True
            for comp in companion_list:
                for j in range(w):
                    comp_sum = 0
                    for memb in comp:
                        comp_sum += true_ss[j][memb]
                    if bin_is == '010':
                        print(comp)
                        print(comp_sum)
                    if comp_sum > k:
                        flag = False
                        break
            if not flag:
                continue

        print(bin_is)

        bases = [0]*(h_line+1)

        for divide in range(w):
            # divideはどこで切るか
            for l, check_row in enumerate(companion_list):
                part_sum = 0
                for m in check_row:
                    part_sum += ss[m][divide]
                if part_sum-bases[l] > k:
                    h_line += 1
                    for lll, check_row_ll in enumerate(companion_list):
                        part_sum_ll = 0
                        for m in check_row:
                            part_sum_ll += ss[m][divide-1]
                        bases[lll] = part_sum_ll
                    break
        if ans > h_line:
            ans = h_line
    print(ans)

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
    fff = set(); fff.add(0)
    f = True
    for x in range(w):
        lcnt = 0
        if not f:
            cnt = INF
            break
        for y in range(h):
            lcnt += ass[y][x+1] - ass[y][ind]
            if lcnt > k:
                ind = x
                fff.add(x)
                if x-1 in fff: f = False
                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:
H, W, K = map(int, input().split())
S = [[int(c) for c in input()] for i in range(H)]

s = [[0 for i in range(W+1)] for j in range(H + 1)]
for i in range(H):
    for j in range(W):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + S[i][j]

n = H - 1
ans = H * W
for i in range(2 ** n):
    horizon = [0]
    length = 2
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    flag = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            if (sq > K):
                if (y2 == 1):
                    break
                else:
                    vertical += 1
                    y1 = y2 - 1
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Wrong Answer

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

s = [[0 for i in range(W+1)] for j in range(H + 1)]
for i in range(H):
    for j in range(W):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + S[i][j]

n = H - 1
ans = H * W
for i in range(2 ** n):
    horizon = [0]
    length = 0
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    flag = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            if (sq > K):
                if (y2 == 1):
                    break
                else:
                    vertical += 1
                    y1 = y2 - 1
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import time
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
H, W, K = [int(x) for x in input().strip().split()]
G = np.zeros((H, W), dtype=int)

for h in range(H):
    G[h, :] = np.array([int(x) for x in list(input().strip())])

ans = float('inf')
for i in range(1 << H-1):
    l = []
    for j in range(H-1):
        if i >> j & 1:
            l.append(j+1)
    if len(l):
        l = [0] + l + [H]
        G2 = []
        for j in range(1, len(l)):
            G2.append(G[l[j-1]:l[j], :])
    else:
        G2 = [G]
    t_ans = len(l)
    col = 0
    print(G2)
    offset = 0
    while True:
        offset += 1
        print('col = {}, offset = {}'.format(col, offset))
        for g2 in G2:
            # print(g2)
            print(g2[:, col:col+offset].sum())
            if g2[:, col:col+offset].sum() > K:
                break
        else:
            if col + offset == W:
                f = True
                break
            else:
                continue
        if offset == 1:
            f = False
            break
        col += offset - 1
        t_ans += 1
        offset = 0
    
    if not f:
        continue
    ans = min(ans, t_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            ass(len(grid) > i)
            ass(len(grid[i]) > j)
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        ass(len(counters))
        ass(k)
        if max(counters) > k:
            ass(hasattr(local_counters, 'copy'))
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Wrong Answer

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

s = [[0 for i in range(W+1)] for j in range(H + 1)]
for i in range(H):
    for j in range(W):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + S[i][j]

n = H - 1
ans = 1 << 30
for i in range(2 ** n):
    horizon = [0]
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
    horizon.append(H)
    # hori = 横はどこで割るのか？
    y1 = 0
    y2 = 1
    vertical = 0
    length = len(horizon)
    # print("horizon", horizon)
    while (y2 <= W):
        # print(y1, y2)
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            # print(sq, K)
            if (sq > K):
                if (y2 == 1):
                    break
                else:
                    vertical += 1
                    y1 = y2 - 1
        y2 += 1
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Wrong Answer

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

s = [[0 for i in range(W+1)] for j in range(H + 1)]
for i in range(H):
    for j in range(W):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + S[i][j]

n = H - 1
ans = 100000000
for i in range(2 ** n):
    horizon = [0]
    length = 0
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    flag = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            if (sq > K):
                if (y2 == 1):
                    break
                else:
                    vertical += 1
                    y1 = y2 - 1
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
from bisect import bisect_left


def read():
    H, W, K = list(map(int, input().strip().split()))
    S = list()
    for i in range(H):
        s = list(map(int, input()))
        S.append(s)
    return H, W, K, S


def cumsum_build(H, W, S):
    c = [[0 for j in range(W+1)] for i in range(H+1)]
    for i in range(H):
        for j in range(W):
            c[i+1][j+1] = S[i][j]
    for i in range(1, H+1):
        for j in range(1, W+1):
            c[i][j] += c[i][j-1] + c[i-1][j] - c[i-1][j-1]
    return c

def cumsum_query(x0, y0, x1, y1, c):
    return c[x1][y1] - c[x0][y1] - c[x1][y0] + c[x0][y0]

def get_ubrange(ptn, H):
    us = [0]
    for h in range(H):
        if ptn & 0x1 == 0x1:
            us.append(h)
        ptn >>= 1
    bs = []
    for i in range(1, len(us)):
        bs.append(us[i])
    bs.append(H)
    return us, bs

def get_lrrange(us, bs, K, W, c, INF=10000000):
    ls = [0]
    l = 0
    for r in range(1, W+1):
        is_end = False
        for u, b in zip(us, bs):
            if cumsum_query(u, l, b, r, c) > K:
                is_end = True
        if is_end:
            ls.append(r-1)
            l = r-1
    rs = []
    for i in range(1, len(ls)):
        rs.append(ls[i])
    rs.append(W)
    return ls, rs

def solve(H, W, K, S, INF=10000000):
    c = cumsum_build(H, W, S)
    ptns = 2 ** (H-1)
    
    min_n_bars = (H-1) * (W-1)
    for ptn in range(ptns):
        us, bs = get_ubrange(ptn, H)
        ls, rs = get_lrrange(us, bs, K, W, c)

        n_bars = (len(us) - 1) + (len(ls) - 1)
        min_n_bars = min(n_bars, min_n_bars)
    return min_n_bars

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
import itertools

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

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

cnt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  cnt[i][0] = int(s[i][0]) + (0 if i == 0 else cnt[i - 1][0])

for i in range(w):
  cnt[0][i] = int(s[0][i]) + (0 if i == 0 else cnt[0][i - 1])

for i in range(1, h):
  for j in range(1, w):
    cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + int(s[i][j])

num = [i for i in range(h - 1)]
ans = 99999
for i in range(0, h):
  for v in itertools.combinations(num, i):
    n = list(v)
    n.append(h - 1)
    
    _ans = i
    _left = -1
    for j in range(w):
      for _k in range(len(n)):
        if cnt[n[_k]][j] - (0 if _left < 0 else cnt[n[_k]][_left]) - (0 if _k == 0 else cnt[n[_k - 1]][j]) + (0 if _left < 0 or _k == 0 else cnt[n[_k - 1]][_left]) > k:
          _left = j - 1
          _ans += 1
          break
    ans = min(ans, _ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    ass(False)
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        if max(counters) > k:
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
ans=10**18
for i in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')
  if len(flag)!=(h-1):
    flag='0'*((h-1)-len(flag))+flag
  for j in range((h-1)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  prevx=0
  tmp=len(hlist)
  yoko=tmp-1
  tate=0
  for j in range(w-1):
    prevy=0
    for l in range(tmp):
      if count(prevx,prevy,j,hlist[l])>k:
        tate+=10**18
      if count(prevx,prevy,j,hlist[l])<=k and count(prevx,prevy,j+1,hlist[l])>k:
        tate+=1
        prevx=j+1
        break
      prevy=hlist[l]+1
  ans=min(ans,yoko+tate)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]

ass(False)

ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        if max(counters) > k:
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)