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: Time Limit Exceeded

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

c = [[0 for _ in range(W)] for _ in range(H)]

# 1×ｗの一次元の配列で考える。分割したマスをそれぞれホワイトチョコをカウントする
# データを加工してから貪欲法を行う

# bit全探索: 横線で割るパターン全てについて、縦線での折り方を考える
ans = (H-1) * (W-1)
for div in range(1<<(H-1)):
    g = 0 # g: 横線で分割するグループ番号（０、１、２...）
    id = [0] * H #何行目であるかを識別するid: i=1なら　グループiになる
    for i in range(H):
        id[i] = g
        if div>>i&1: # 2進法でdivのi桁目が1の時、そこで分割する
            g += 1 #分割線がきたらgを増やす
    g += 1 # グループ数は分割線+１になる
    #　集計に使うｃ配列を初期化
    for i in range(g):
        for j in range(W):
            c[i][j] = 0
    # グループごとを各列ごとのホワイトチョコを集計する
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    num = g - 1 #すでに横線で折った回数（グループ数-１）
    now = [0] * g #現状で何個のホワイトチョコがあるか
    # 各グループの縦割りの確認
    def add(j):
        for i in range(g):
            now[i] += c[i][j] #ｊ列目のホワイトチョコを足していく
        for i in range(g):
            
            if now[i] > K: return False
        return True

    for j in range(W):
        if not (add(j)): # ホワイトチョコがKを超えていれば、縦で織る。
            num += 1
            now = [0] * g
            if not (add(j)):
                num = (H-1) * (W-1)
                break
    #print(g, c, num) # 横割りの回数、各グループの集計、最終的に折った回数
    ans = min(ans, num) # 割った回数値の最小を更新 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
h, w, k = map(int, input().split())
li_hw =  [list(f) for f in [input() for _ in range(h)]]
all_h = []
score = []
# for l in range(2**(h-1)):
#     ind = []
#     pre = 0
#     cut_list=[]
#     hline_num = 0
#     for n,yn in enumerate(reversed(list(bin(l))[2:])):
#         if yn == "1":
#             cut_list.append(li_hw[pre:n+1])
#             pre = n+1
#     cut_list.append(li_hw[pre:h])
for i in itertools.product([0, 1], repeat=h-1):
    cut_list=[]
    hline_num = 0
    pre = 0
    cut_list = []
    for n, i2 in enumerate(i):
        if i2 == 1:
            cut_list.append(li_hw[pre:n+1])
            pre = n+1
    cut_list.append(li_hw[pre:h])
    hline_num = i.count(1)
    pred = 0
    wline_num = 0
    #print("list is {}".format(cut_list))
    
    
    for y in range(w):
        wcounter_list = []
        for c in cut_list:
            wcounter = 0
            for c2 in c:
                wcounter += c2[pred:y+1].count("1")
            wcounter_list.append(wcounter)
        #print("wcounter{}".format(wcounter_list))
        if max(wcounter_list) > k:
            pred = y
            wline_num += 1
            #print("line between{}and{}".format(y-1, y))
    #print("wline{}, hline{}".format(wline_num, hline_num))
    score.append(wline_num+hline_num)
print(min(score))

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
li_hw =  [list(f) for f in [input() for _ in range(h)]]
all_h = []
score = []
for l in range(2**(h-1)):
    ind = []
    pre = 0
    cut_list=[]
    hline_num = 0
    for n,yn in enumerate(reversed(list(bin(l))[2:])):
        if yn == "1":
            cut_list.append(li_hw[pre:n+1])
            pre = n+1
    cut_list.append(li_hw[pre:h])
    hline_num = list(bin(l)).count("1")
    #print(bin(l)) 
    pred = 0
    wline_num = 0
    #print("list is {}".format(cut_list))
    for y in range(w):
        wcounter_list = []
        for c in cut_list:
            wcounter = 0
            for c2 in c:
                wcounter += c2[pred:y+1].count("1")
            wcounter_list.append(wcounter)
        #print("wcounter{}".format(wcounter_list))
        if max(wcounter_list) > k:
            pred = y
            wline_num += 1
            #print("line between{}and{}".format(y-1, y))
    #print("wline{}, hline{}".format(wline_num, hline_num))
    score.append(wline_num+hline_num)
print(min(score))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().strip()
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int,input().split())
    s = np.array([[int(i) for i in input()] for _ in range(h)])
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        j = 0
        while j < w: #O(2 * 10 ** 3)
            tmp = 0
            idx = 0
            flag = True
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        partsum = [0 for _ in range(sh)]
                        flag = False
                        break
                    tmp = 0
                    idx += 1
            if flag:
                j += 1
        ans = min(ans, tmpans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int,input().split())
    s = [[int(i) for i in input()] for _ in range(h)]

    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        j = 0
        while j < w: #O(2 * 10 ** 3)
            tmp = 0
            idx = 0
            flag = True
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        partsum = [0 for _ in range(sh)]
                        flag = False
                        break
                    tmp = 0
                    idx += 1
            if flag:
                j += 1
        ans = min(ans, tmpans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()
inf = sys.maxsize

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

ans = inf
for i in range(h): #縦方向の割り方を全探索 O(512)
    arr = list(combinations(range(h - 1), i))
    for ii in range(len(arr)):
        hdiv = [1 if j in arr[ii] else 0 for j in range(h - 1)]
        hdiv.append(1)
        tmpans = i
        partsum = [0 for _ in range(i + 1)]
        j = 0
        while j < w: #O(2 * 10 ** 3)
            tmp = 0
            idx = 0
            flag = True
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum[idx] += tmp
                    if partsum[idx] > k:
                        tmpans += 1
                        partsum = [0 for _ in range(i + 1)]
                        flag = False
                        break
                    tmp = 0
                    idx += 1
            if flag:
                j += 1
        ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, k = map(int, input().split())
li_hw  = []
for l in range(h):
    a = map(str, input().split())
    li = []
    for i in a:
        li_hw.append(list(i))
all_h = []
score = []
for l in range(2**(h-1)):
    ind = []
    pre = 0
    cut_list=[]
    hline_num = 0
    for n,yn in enumerate(reversed(list(bin(l))[2:])):
        if yn == "1":
            cut_list.append(li_hw[pre:n+1])
            pre = n+1
    cut_list.append(li_hw[pre:h])
    hline_num = list(bin(l)).count("1")
    #print(bin(l)) 
    pred = 0
    wline_num = 0
    #print("list is {}".format(cut_list))
    for y in range(w):
        wcounter_list = []
        for c in cut_list:
            wcounter = 0
            for c2 in c:
                wcounter += c2[pred:y+1].count("1")
            wcounter_list.append(wcounter)
        #print("wcounter{}".format(wcounter_list))
        if max(wcounter_list) > k:
            pred = y
            wline_num += 1
            #print("line between{}and{}".format(y-1, y))
    #print("wline{}, hline{}".format(wline_num, hline_num))
    score.append(wline_num+hline_num)
print(min(score))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
    hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
    hdiv.append(1)
    sh = sum(hdiv)
    tmpans = sh - 1
    partsum = [0 for _ in range(sh)]
    j = 0
    while j < w: #O(2 * 10 ** 3)
        tmp = 0
        idx = 0
        flag = True
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                if partsum[idx] > k:
                    tmpans += 1
                    partsum = [0 for _ in range(sh)]
                    flag = False
                    break
                tmp = 0
                idx += 1
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
    hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
    hdiv.append(1)
    sh = sum(hdiv)
    tmpans = sh - 1
    partsum = [0 for _ in range(sh)]
    j = 0
    while j < w: #O(2 * 10 ** 3)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh): #O(10)
            if partsum[kk] > k:
                tmpans += 1
                for l in range(sh):
                    partsum[l] = 0
                flag = False
                break
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(500)
    hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
    hdiv.append(1)
    sh = sum(hdiv)
    tmpans = sh - 1
    partsum = [0 for _ in range(sh)]
    j = 0
    while j < w: #O(2 * 10 ** 4)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh):
            if partsum[kk] > k:
                tmpans += 1
                for l in range(sh):
                    partsum[l] = 0
                flag = False
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(500)
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    while j < w: #O(2 * 10 ** 4)
        tmp = 0
        idx = 0
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索
    hdiv = [1 for _ in range(h)]
    for j in range(h - 1):
        tmp = 2 ** j
        hdiv[j] = 1 if i & tmp else 0
    sh = sum(hdiv)
    tmpans = sh - 1
    wdiv = [0 for _ in range(w - 1)]
    partsum = [0 for _ in range(sh + 1)]
    j = 0
    while j < w:
        tmp = 0
        idx = 0
        for kk in range(h):
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                tmp = 0
                idx += 1
        flag = True
        for kk in range(sh + 1):
            if partsum[kk] > k:
                tmpans += 1
                partsum = [0 for _ in range(sh + 1)]
                flag = False
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import copy

h,w,k = map(int,input().split())
S = [list(map(int,input())) for _ in range(h)]

p = product([0,1],repeat=h-1)
INF = h*w
ans = INF

for i,tfs in enumerate(p):  
  lst = []
  l = copy.copy(S[0])
  for hi in range(h-1):
    if tfs[hi]:
      lst.append(l)
      l = copy.copy(S[hi+1])
    else:
      for wi in range(w):
        l[wi] += S[hi+1][wi]
  lst.append(l)
  
  lst2 = []
  for li in range(len(lst)):
    l = [0] * (w+1)
    for wi in range(w):
      l[wi+1] = l[wi] + lst[li][wi]
    lst2.append(l)
        
  count = 0    
  left = 0  
  right = 0
  max_sum = 0    

  while right < w:
    right += 1
    for li in range(len(lst)):
      if max(lst[li]) > k:
        count = INF
        right = INF
        break
      max_sum = max(max_sum, lst2[li][right] - lst2[li][left])      

    if max_sum > k:
      count += 1
      max_sum = 0
      left = right - 1      
  
  count += len(lst)-1
  ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
## TLE

from itertools import product

h,w,k = map(int,input().split())
S = [list(map(int,input())) for _ in range(h)]

p = product([0,1],repeat=h-1)
INF = h*w
ans = INF

for i,tfs in enumerate(p):  
  lst = []
  l = S[0].copy()
  for hi in range(h-1):
    if tfs[hi]:
      lst.append(l)
      l = S[hi+1].copy()
    else:
      for wi in range(w):
        l[wi] += S[hi+1][wi]
  lst.append(l)
  
  lst2 = []
  for li in range(len(lst)):
    l = [0] * (w+1)
    for wi in range(w):
      l[wi+1] = l[wi] + lst[li][wi]
    lst2.append(l)
        
  count = 0    
  left = 0  
  right = 0
  max_sum = 0    

  while right < w:
    right += 1
    for li in range(len(lst)):
      if max(lst[li]) > k:
        count = INF
        right = INF
        break
      max_sum = max(max_sum, lst2[li][right] - lst2[li][left])      

    if max_sum > k:
      count += 1
      max_sum = 0
      left = right - 1      
  
  count += len(lst)-1
  ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
## TLE

from itertools import product

h,w,k = map(int,input().split())
S = [list(map(int,input())) for _ in range(h)]

p = product([0,1],repeat=h-1)
INF = h*w
ans = INF

for i,tfs in enumerate(p):  
  lst = []
  l = S[0].copy()
  for hi in range(h-1):
    if tfs[hi]:
      lst.append(l)
      l = S[hi+1].copy()
    else:
      for wi in range(w):
        l[wi] += S[hi+1][wi]
  lst.append(l)
  
  count = 0    
  left = 0  
  right = 0
  max_sum = 0    

  while right < w:
    right += 1
    for li in lst:
      if max(li) > k:
        count = INF
        right = INF
      max_sum = max(max_sum, sum(li[left:right]))

    if max_sum > k:
      count += 1
      max_sum = 0
      left = right - 1        
      
  count += len(lst)-1
  ans = min(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    global noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
#    print(y,i,lst, "makelst")
               
def nocut(i):
    global cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
#        print(y,i,lst,"nocut", "cutnum = ",cutnum)
        return(True)
    else:
        cutnum += 1
        lst = prelst        
#        print(y,i,lst,"cut","cutnum =",cutnum)
        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if havelst:
            nocut(x)
        else:
            make_lst(x)
#    print(y,cutnum)
    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

Submission status: Time Limit Exceeded

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

choco = [[0] * w for _ in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        choco[i][j] = int(s[j])

ans = float("inf")
for bit in range(1 << (h - 1)):
    idx = [0] * h
    group = 0
    for i in range(h):
        idx[i] = group
        if (bit >> i) & 1:
            group += 1
    group += 1
    array = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            array[idx[i]][j] += choco[i][j]

    cnt = group - 1
    cum = [0] * group
    canAdd = True
    for i in range(w):
        for j in range(group):
            if cum[j] > k:
                canAdd = False

        if canAdd is False:
            break

        for j in range(group):
            tmp = cum[j] + array[j][i]
            if tmp > k:
                cnt += 1
                for l in range(group):
                    cum[l] = array[l][i]
                break
            cum[j] += array[j][i]

    if canAdd:
        ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H,W,K=map(int,input().split())
S=[]
for i in range(H):
    t=list(input())
    t=[int(x) for x in t]
    S.append(t)

ANS=1000000
PRD=list(itertools.product([0,1], repeat=H-1))

def bit_to_group(bit):
    arr=[0]*H
    g=0  #グループナンバー
    for i in range(H-1):
        arr[i+1]=g
        if bit[i]==1:
            arr[i+1]+=1
            g+=1
    return arr

GROUPS=[]
for i in range(len(PRD)):
#    print(PRD[i],bit_to_group(PRD[i]))
    GROUPS.append(bit_to_group(PRD[i]))

for i in range(len(GROUPS)):
    grp=GROUPS[i]
#    print(grp)
    l=grp[-1]+1
    table=[0]*l
    ans=l-1
    j=0
    while j<W:  #Kを超えないと判定して初めて次の列を見るようにする
        k=0
        for k in range(H):
            table[grp[k]]+=S[k][j]
#            print(table,ans,k,j)
            k+=1
        if max(table)>K:
            table=[0]*l
            ans+=1
        else:
            j+=1
    ANS=min(ANS,ans)
            
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,K = map(int, input().split())
C = np.array([list(map(int, input())) for _ in range(H)])
C = np.hstack([np.zeros([H,1]),C])
np.cumsum(C, axis=1, out=C)
ans = 10**5
for s in range(1<<(H-1)):
	ind = 0
	A = np.zeros([1,W+1])
	for i in range(H):
		if s >> i & 1 == 1:
			A = np.vstack([A,C[ind:i+1,:].sum(axis=0)])
			ind = i+1
	A = np.vstack([A,C[ind:].sum(axis=0)])

	ind = 0
	cnt = 0
	while True:
		cut = 10**3+2
		for a in A:
			cut = min(cut, np.searchsorted(a,a[ind]+K,side='right'))
		if cut == W+1:
			break
		ind = cut-1
		cnt += 1

	h_cnt = 0
	for i in range(H):
		if s >> i & 1 == 1:
			h_cnt += 1

	ans = min(ans, cnt+h_cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

INF = float("inf")

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = INF
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = INF
              break

    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

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

T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
    print(0)
    quit()

ans = float("inf")
for P in product([0, 1], repeat=H - 1):
    cnt = sum(P)

    II = [[0]]
    for i, p in enumerate(P, 1):
        if p:
            II.append([])
        II[-1].append(i)

    A = [0] * len(II)
    for t in T:
        for i, I in enumerate(II):
            A[i] += sum(t[x] for x in I)

        if any(a > K for a in A):
            cnt += 1
            if cnt >= ans:
                break

            A = [sum(t[x] for x in I) for I in II]
            if any(a > K for a in A):
              cnt = 1 + ans
              break

    ans = min(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k, s in enumerate(S):
                if s[j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print(0)
        exit()

    ans = 10**5
    for i in range(2**(H-1)):
        impossible = False
        x = 0
        ly = bin(i).count("1")
        y_sum = [0]*(ly + 1)
        j = 0
        while j < W:
            m = 0
            y = [0]*(ly + 1)
            for k in range(H):
                if S[k][j] == "1":
                    y[m] += 1
                    if y[m] > K:
                        impossible = True
                        break
                    y_sum[m] += 1
                    if y_sum[m] > K:
                        x += 1
                        y_sum = [0]*(ly + 1)
                        j -= 1
                        break
                if (i >> k) & 1:
                    m += 1
            j += 1
            if impossible:
                x = 10**6
                break

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
ans=10**9
choco=[list(input()) for i in range(h)]
sumL=[[0 for i in range(w+1)] for j in range(h+1)]
for i in range(h):
    for j in range(w):
        sumL[i][j]=sumL[i-1][j]+sumL[i][j-1]-sumL[i-1][j-1]+int(choco[i][j])
for stat in range(2**(h-1)):
    cnt=0;previous=-1
    flg=0
    cut=format(stat,"b").zfill(h-1)
    cutl=[]
    for hi in range(h-1):
        if cut[hi]=="1":
            cutl.append(hi)
            cnt+=1
    cutl.append(h-1)
    cutl.append(-1)
    for yoko in range(w):
        for seg in range(len(cutl)):
            if sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k and yoko-previous<=1:flg=1
            elif sumL[cutl[seg]][yoko]-sumL[cutl[seg]][previous]-sumL[cutl[seg-1]][yoko]+sumL[cutl[seg-1]][previous]>k:previous=yoko-1;cnt+=1
            
    if not flg and cnt < ans:ans=cnt
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    H, W, K = map(int, raw_input().split())
    S = []

    for i in range(H):
        S.append(list(raw_input()))

    for i in range(H):
        for j in range(W):
            S[i][j] = int(S[i][j])

    ans = 10**9

    for divide in range(2**(H)):
        regions = []
        for l in range(H):
            if divide & 1 << l:
                regions.append(l)
        S_subs = []
        prev = 0
        for region in regions:
            new = region
            S_subs.append(S[prev:new])
            prev = new
        S_subs.append(S[prev:H])
        N = len(S_subs)

        count = [0]*N

        bin_num = bin(divide)[2:]

        ans_temp = 0
        for i in bin_num:
            ans_temp += int(i)

        for j in range(W):
            for l in range(N):
                for item in S_subs[l]:
                    count[l] += item[j]
            if max(count) > K:
                ans_temp = ans_temp + 1
                count = [0]*N
                for m in range(N):
                    for item in S_subs[m]:
                        count[m] += item[j]

        if ans_temp < ans:
            ans = ans_temp

#        print ans_temp               
    print ans


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
g=[input() for _ in range(H)]
ans=1<<100
for i in range(1<<H-1):
	need=bin(i).count("1")
	sz=need+1
	cnt=[0]*sz
	f=1
	for j in range(W):
		c=0
		for k in range(H):
			cnt[c]+=g[k][j]=="1"
			if cnt[c]>K:
				break
			c+=(i>>k)&1
		else:
			continue
		cnt=[0]*sz
		need+=1
		c=0
		for k in range(H):
			cnt[c]+=g[k][j]=="1"
			if cnt[c]>K:
				break
			c+=(i>>k)&1
		else:
			continue
		f=0
		break
	if f:
		ans=min(ans,need)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
S_T = [[int(s[w]) for s in S] for w in range(W)]
sumS = sum(map(sum, S_T))
ans = (H - 1) * (W - 1)

if sumS <= K:
    print(0)
else:
    for i in product([True, False], repeat=H-1):
        cnt = sum(i)
        M = [[0]]
        for j, k in enumerate(i):
            if k:
                M.append([])
            M[-1].append(j+1)
        A = [0] * len(M)
        for s_t in S_T:
            for l, m in enumerate(M):
                A[l] += sum(s_t[i] for i in m)
            if any(a > K for a in A):
                cnt += 1
                A = [sum(s_t[i] for i in m) for m in M]
                if any(a > K for a in A):
                    cnt = ans + 1
        ans = min(cnt, ans)
    print(ans)