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:
#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        last_div = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        # 最後の行だけでmax(cnt_white) >= k+1になるときはその切り方では不可能
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            if last_div == w-1:
                ans_i = h*w  #INF
                break
            last_div = c
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if (i >> bit) & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if (i >> r) & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
h,w,k = map(int,input().split())
b =[]
for i in range(h):
    s = input()
    b.append(s)
# 縦の切り方を固定すれば、左から見て貪欲に考えることができる。
# どれかの切り方でK+1　以上1 のマスがあれば、そこで切る
if h == 1:
    print(math.ceil(s//k))
    exit()
# リストで現在のそれぞれのブロックの1の数を持つ

# 列の切断が入ったときに全て0に初期化
# bit 全探索は 2 ** h-1 存在する 
ans = h*w #INF
for i in range(2**(h-1)):
    cnt_white = [0] 
    # ループの中で宣言する
    ans_i = 0
    #前処理として、どこに切れ込みがあるかを見て、リストの構成
    for bit in range(h-1):
        if i >> bit & 1:
            cnt_white.append(0)
            ans_i += 1
    #print("i = ",i,cnt_white)
    c = 0
    while c < w:# 左から貪欲
        r_idx = 0
        for r in range(h):
            if b[r][c] == "1":#対応するブロックのcnt+=1
                cnt_white[r_idx] += 1
                #print("col = ",c,cnt_white,r_idx,ans_i)
            if i >> r & 1:#次にブロックが変わるのでidxを増やす
                r_idx += 1
        if max(cnt_white) >= k+1:
            # 戻らないといけない
            ans_i += 1
            c -= 1
            cnt_white = [0]*len(cnt_white)#初期化
            #print("initialize")
        c += 1
    ans = min(ans,ans_i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# H <= 10であるため2^(H-1)を全探索し、
# W <= 1000 については貪欲に左から探索していけば良い

'''
4 10 4
1110010010
1000101110
0011101001
1101000111
'''

import numpy as np


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

    data = np.array([[None] * W for _ in range(H)])

    for i in range(H):
        temp = input()
        for j in range(W):
            data[i, j] = int(temp[j])

    current_best = np.inf

    # Hに関する全ての場合を試す
    for cnt in range(2 ** (H-1)):
        # bitで1の場所が切れ目とする
        option_h = np.array([int(s) for s in list(bin(cnt))[2:][::-1]])
        kireme = np.where(option_h == 1)[0]

        # 各グループについて1の数を集計する
        li = 0
        g = np.array([[None] * W for _ in range(len(kireme) + 1)])
        if len(kireme) == 0:
            g[0] = data[li:, :].sum(axis=0)
        else:
            for idx, j in enumerate(kireme):
                g[idx] = data[li:j+1, :].sum(axis=0)
                li = j + 1
            g[-1] = data[li:, :].sum(axis=0)

        # 左から順に足していく
        score = len(kireme)
        if score > current_best:
            # すでにこの時点で回数かかっていれば探索打ち切り
            continue

        res = np.zeros(len(kireme) + 1)
        for col in range(W):
            res = res + g[:, col]
            # どこか1つのグループでもKを超えてしまったらその左で切る
            if (res > K).any():
                score += 1
                # 最小を求めたいので、それまでの結果と同じ値になってしまったら終了
                if score >= current_best:
                    break
                res = g[:, col]
                # 現在の列だけで条件を満たせないのであれば不可能なので終了
                if (res > K).any():
                    score = np.inf
                    break
        # スコアの更新
        # print(cnt, score)
        if score < current_best:
            current_best = score

    print(current_best)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# H <= 10であるため2^(H-1)を全探索し、
# W <= 1000 については貪欲に左から探索していけば良い

'''
3 5 4
11100
10001
00111
'''

import numpy as np

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

    # multiple = 100
    # multiple_H = 3
    # W *= multiple
    # H *= multiple_H

    data = np.array([[None] * W for _ in range(H)])

    for i in range(H):
        temp = input()
        for j in range(W):
            data[i, j] = int(temp[j])

    # print(data)

    current_best = np.inf

    # Hに関する全ての場合を試す
    for cnt in range(2 ** (H-1)):
        # bitで1の場所が切れ目とする
        option_h = np.array([int(s) for s in list(bin(cnt))[2:][::-1]])
        kireme = np.where(option_h == 1)[0]

        # 各グループについて1の数を集計する
        li = 0
        g = np.array([[None] * W for _ in range(len(kireme) + 1)])
        if len(kireme) == 0:
            g[0] = data[li:, :].sum(axis=0)
        else:
            for cnt, j in enumerate(kireme):
                g[cnt] = data[li:j+1, :].sum(axis=0)
                li = j + 1
            g[-1] = data[li:, :].sum(axis=0)

        # 左から順に足していく
        score = len(kireme)
        if score > current_best:
            # すでにこの時点で回数かかっていれば探索打ち切り
            continue
        cnt = np.zeros(len(kireme) + 1)
        for col in range(W):
            cnt = cnt + g[:, col]
            # どこか1つのグループでもKを超えてしまったらその左で切る
            if (cnt > K).any():
                score += 1
                # 最小を求めたいので、それまでの結果と同じ値になってしまったら終了
                if score >= current_best:
                    break
                cnt = g[:, col]
                # 現在の列だけで条件を満たせないのであれば不可能なので終了
                if (cnt > K).any():
                    score = np.inf
                    break
        # スコアの更新
        if score < current_best:
            current_best = score

    print(current_best)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# H <= 10であるため2^(H-1)を全探索し、
# W <= 1000 については貪欲に左から探索していけば良い

'''
3 5 4
11100
10001
00111
'''

import numpy as np

H, W, K = map(int, input().split())
data = np.array([[None] * W for _ in range(H)])

for i in range(H):
    temp = input()
    for j in range(W):
        data[i, j] = int(temp[j])

# print(data)

current_best = np.inf

# Hに関する全ての場合を試す
for cnt in range(2 ** (H-1)):
    # bitで1の場所が切れ目とする
    option_h = np.array([int(s) for s in list(bin(cnt))[2:][::-1]])
    kireme = np.where(option_h == 1)[0]
    # print(cnt, option_h, kireme)

    # 各グループについて集計する
    li = 0
    g = np.array([[None] * W for _ in range(len(kireme) + 1)])

    if len(kireme) == 0:
        g[0] = data[li:, :].sum(axis=0)
    else:
        for cnt, j in enumerate(kireme):
            g[cnt] = data[li:j+1, :].sum(axis=0)
            li = j + 1
        g[-1] = data[li:, :].sum(axis=0)

    # print(g)

    # 左から順に足していく
    score = len(kireme)
    cnt = np.zeros(len(kireme) + 1)
    for col in range(W):
        cnt = cnt + g[:, col]
        # どこか1つのグループでもKを超えてしまったらその左で切る
        if (cnt > K).any():
            score += 1
            # 最小を求めたいので、それまでの結果と同じ値になってしまったら終了
            if score >= current_best:
                break
            cnt = g[:, col]
            # 現在の列だけで条件を満たせないのであれば不可能なので終了
            if (cnt > K).any():
                score = np.inf
                break
    # スコアの更新
    if score < current_best:
        current_best = score


print(current_best)

Submission status: Time Limit Exceeded

Solution code:
import cProfile
from collections import defaultdict
from itertools import combinations
import copy
h, w, k = map(int, input().split())
# test splits from 1 -> inf                                                                                                                      
# Horizontally, 10cN                                                                                                                             
# then, we can DP vertical                                                                                                                       

choco = [list(map(int, list(input()))) for i in range(h)]
#print(choco)                                                                                                                                    

horizons = {}
def listSum(choco, s, e):
    if (s,e) not in horizons:
        ret = copy.copy(choco[s])
        if s < e:
            for i in range(s+1, e):
                for j in range(len(choco[0])):
                    ret[j] += choco[i][j]
        horizons[(s,e)] = ret
    return horizons[(s,e)]

def merge(choco, stend):
    ret = []
    for s,e in stend:
        ret.append(listSum(choco, s, e))
    return ret

def testVertical(merged, vs, k):
    vsTotal = 0
    vsList = []
    last = 0
    tot = defaultdict(int)
    numS = len(merged)
    for j in range(len(merged[0])):
        for i in range(numS):
            if merged[i][j] > k:
                return False
            if merged[i][j] + tot[i] > k:
                vsTotal += 1
                vsList.append(j)
                if vsTotal > vs:
                    return False
                last = j
                break
        for i in range(numS):
            if last == j:
                tot[i] = merged[i][j]
            else:
                tot[i] += merged[i][j]
#    print('vslist', vsList)                                                                                                                     
    return True

def test(choco, hs, vs, k):
    splits = combinations(range(1, h), hs) # split at the end of each row in splits                                                              
    for split in splits:
        sstart = [0] + list(split)
        send = list(split) + [h]
        merged = merge(choco, list(zip(sstart, send)))
        for m in merged:
            for i in m:
                if i > k:
                    return False
        if testVertical(merged, vs, k):
#            print('passed')                                                                                                                     
#            print('hs', hs)                                                                                                                     
#            print(merged)                                                                                                                       
            return True
    return False

for i in range(0, h+w):
#    print('total', i)                                                                                                                           
    for hs in range(0, min(i+1, h)):
        vs = i-hs
        if test(choco, hs, vs, k):
            print(i)
            exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations
import copy
h, w, k = map(int, input().split())
# test splits from 1 -> inf                                                                                                                      
# Horizontally, 10cN                                                                                                                             
# then, we can DP vertical                                                                                                                       

choco = [list(map(int, list(input()))) for i in range(h)]
#print(choco)                                                                                                                                    


def listSum(lists):
    ret = copy.copy(lists[0])
    if len(lists) != 1:
        for i in range(1, len(lists)):
            for j in range(len(lists[i])):
                ret[j] += lists[i][j]
    return ret

def merge(choco, stend):
    ret = []
    for s,e in stend:
        ret.append(listSum(choco[s:e]))
    return ret

def testVertical(merged, vs, k):
    vsTotal = 0
    vsList = []
    last = 0
    tot = defaultdict(int)
    numS = len(merged)
    for j in range(len(merged[0])):
        for i in range(numS):
            if merged[i][j] > k:
                return False
            if merged[i][j] + tot[i] > k:
                vsTotal += 1
                vsList.append(j)
                if vsTotal > vs:
                    return False
                last = j
                break
        for i in range(numS):
            if last == j:
                tot[i] = merged[i][j]
            else:
                tot[i] += merged[i][j]
#    print('vslist', vsList)                                                                                                                     
    return True

def test(choco, hs, vs, k):
    splits = combinations(range(1, h), hs) # split at the end of each row in splits                                                              
    for split in splits:
        sstart = [0] + list(split)
        send = list(split) + [h]
        merged = merge(choco, list(zip(sstart, send)))
        for m in merged:
            if any(map(lambda x: x > k, m)):
                return False
        if testVertical(merged, vs, k):
#            print('passed')                                                                                                                     
#            print('hs', hs)                                                                                                                     
#            print(merged)                                                                                                                       
            return True
    return False

for i in range(0, h+w):
#    print('total', i)                                                                                                                           
    for hs in range(0, min(i+1, h)):
        vs = i-hs
        if test(choco, hs, vs, k):
            print(i)
            exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from itertools import combinations
import copy
h, w, k = map(int, input().split())
# test splits from 1 -> inf                                                                                                                      
# Horizontally, 10cN                                                                                                                             
# then, we can DP vertical                                                                                                                       

choco = [list(map(int, list(input()))) for i in range(h)]
#print(choco)                                                                                                                                    


def listSum(lists):
    ret = copy.copy(lists[0])
    if len(lists) != 1:
        for i in range(1, len(lists)):
            for j in range(len(lists[i])):
                ret[j] += lists[i][j]
    return ret

def merge(choco, stend):
    ret = []
    for s,e in stend:
        ret.append(listSum(choco[s:e]))
    return ret

def testVertical(merged, vs, k):
    vsTotal = 0
    vsList = []
    last = 0
    tot = defaultdict(int)
    numS = len(merged)
    for j in range(len(merged[0])):
        for i in range(numS):
            if merged[i][j] > k:
                return False
            if merged[i][j] + tot[i] > k:
                vsTotal += 1
                vsList.append(j)
                if vsTotal > vs:
                    return False
                last = j
                break
        for i in range(numS):
            if last == j:
                tot[i] = merged[i][j]
            else:
                tot[i] += merged[i][j]
#    print('vslist', vsList)                                                                                                                     
    return True

def test(choco, hs, vs, k):
    splits = combinations(range(1, h), hs) # split at the end of each row in splits                                                              
    for split in splits:
        sstart = [0] + list(split)
        send = list(split) + [h]
        merged = merge(choco, list(zip(sstart, send)))
        if testVertical(merged, vs, k):
#            print('passed')                                                                                                                     
#            print('hs', hs)                                                                                                                     
#            print(merged)                                                                                                                       
            return True
    return False

for i in range(0, h+w):
#    print('total', i)                                                                                                                           
    for hs in range(0, min(i+1, h)):
        vs = i-hs
        if test(choco, hs, vs, k):
            print(i)
            exit()

Submission status: Time Limit Exceeded

Solution code:
def whites(i1,i2,j1,j2):
  count = ACUM[i2][j2]
  if i1 !=0:
    count -= ACUM[i1-1][j2]
  if j1 !=0:
    count -= ACUM[i2][j1-1]
  if i1 !=0 and j1 != 0:
    count += ACUM[i1-1][j1-1]
  return count
  
H, W, K = map(int,input().split())
SS = [list(input()) for _ in range(H)]
#crate accumulated array
ACUM = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if SS[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]
    
#try all cases
best_case = H+W
case = 0
while case<(2**(H-1)):
  case_b = list(format(case, 'b'))
  blocks = []
  blocks.append(0)
  for i in range(len(case_b)):
    if case_b[-i-1]=='1':
      blocks.append(i+1)
  blocks.append(H)
  cnt = len(blocks)-2
  #blocksH  = []
  j0 = 0
  j = 0
  while j<W:
    for i in range(len(blocks)-1):
      white_blocks=whites(blocks[i],blocks[i+1]-1,j0,j)
      #print(blocks[i],blocks[i+1],j0,j,white_blocks)
      if white_blocks>K:
        if j0 == j:
          cnt = H+W
          j=W
        #blocksH.append(j)
        cnt+=1
        j0 = j
        j = j-1
        i=range(cnt)
    j+=1
  #print(blocks,cnt)
  if cnt<best_case:
    best_case = cnt
  #print(case_b, blocks, blocksH, cnt)
  case += 1
print(best_case)

Submission status: Time Limit Exceeded

Solution code:
def whites(i1,i2,j1,j2):
  count = ACUM[i2][j2]
  if i1 !=0:
    count -= ACUM[i1-1][j2]
  if j1 !=0:
    count -= ACUM[i2][j1-1]
  if i1 !=0 and j1 != 0:
    count += ACUM[i1-1][j1-1]
  return count
  
H, W, K = map(int,input().split())
SS = [list(input()) for _ in range(H)]
#crate accumulated array
ACUM = [[0]*W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if SS[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]
    
#try all cases
best_case = H+W
case = 0
while case<(2**(H-1)):
  case_b = list(format(case, 'b'))
  blocks = []
  blocks.append(0)
  for i in range(len(case_b)):
    if case_b[-i-1]=='1':
      blocks.append(i+1)
  blocks.append(H)
  cnt = len(blocks)-2
  blocksH  = []
  j0 = 0
  j = 0
  while j<W:
    for i in range(len(blocks)-1):
      white_blocks=whites(blocks[i],blocks[i+1]-1,j0,j)
      #print(blocks[i],blocks[i+1],j0,j,white_blocks)
      if white_blocks>K:
        if j0 == j:
          cnt = H+W
          j=W
        blocksH.append(j)
        cnt+=1
        j0 = j
        j = j-1
        i=range(cnt)
    j+=1
  #print(blocks,cnt)
  if cnt<best_case:
    best_case = cnt
  #print(case_b, blocks, blocksH, cnt)
  case += 1
print(best_case)

Submission status: Time Limit Exceeded

Solution code:
def bit(n, k):
    return ((n>>k) & 1);

n, m, k = (int(i) for i in input().split());

f = [input() for i in range(n)];

#print(len(f[0]));

res = (n - 1) * (m - 1);

cnt = [0 for i in range(n)];
add = [0 for t in range(n)];
for mask in range(2 ** (n - 1)):
    curr = 0;
    for i in range(n):
        curr += bit(mask, i);
        cnt[i] = 0;
    for i in range(m):
        ind = 0;
        for j in range(n):
            add[j] = 0;
            add[ind] += int(f[j][i]);
            if bit(mask, j) == 1:
                ind += 1;

        correct = True;
        for j in range(n):
            if add[j] + cnt[j] > k:
                correct = False;

        if correct == True:
            for j in range(n):
                cnt[j] += add[j];
            continue;
        curr += 1;
        if (curr >= res):
            break;
        for j in range(n):
            cnt[j] = add[j];
    res = min(res, curr);

print(res);

Submission status: Time Limit Exceeded

Solution code:
def bit(n, k):
    return ((n>>k) & 1);

n, m, k = (int(i) for i in input().split());

f = [input() for i in range(n)];

#print(len(f[0]));

res = (n - 1) * (m - 1);

for mask in range(2 ** (n - 1)):
    cnt = [0 for i in range(n)];
    curr = 0;
    for i in range(n):
        curr += bit(mask, i);
    for i in range(m):
        add = [0 for t in range(n)];
        ind = 0;
        for j in range(n):
            #print(i, j);
            add[ind] += int(f[j][i]);
            #add[ind] = 1;
            if bit(mask, j) == 1:
                ind += 1;

        correct = True;
        for j in range(n):
            if add[j] + cnt[j] > k:
                correct = False;

        if correct == True:
            for j in range(n):
                cnt[j] += add[j];
            continue;
        curr += 1;
        for j in range(n):
            cnt[j] = add[j];
    res = min(res, curr);

print(res);

Submission status: Time Limit Exceeded

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

# 含まれる1がk個以下かチェック
def check(s, start = 0, finish = w):
    if type(s[0]) == str:
        div = 0
        for i in s:
            div += i[start:finish].count('1')
        return div <= k
    else:
        flag = 0
        for x in s:
            if not check(x, start, finish):
                flag = 1
                break
        return flag == 0

# 横方向にカット
def div_h(s, div):
    div.append('1')
    start = 0
    s_parts = []
    for i in range(0, h):
        if div[i] == '0':
            continue
        finish = i + 1
        s_parts.append(s[start:finish])
        start = finish
    return s_parts

if check(s):
    ans = 0
else:
    ans = float('inf')
    # 横方向に全探索
    for i in range(2 ** (h - 1)):
        div = bin(i)[2:]
        div = list(div.zfill(h - 1))
        # 何回割ったかのメモ
        cnt = div.count('1')
        # 分割したチョコのリスト
        s_li = div_h(s, div)
        # 縦方向に貪欲に探索
        start = 0
        finish = 1
        flag = 0
        while finish < w + 1:
            # 横に分割されたチョコをそれぞれ評価
            if check(s_li, start, finish):
                finish += 1
            elif finish - start == 1:
                flag = 1
                break
            else:
                start = finish - 1
                cnt += 1
        if flag != 0:
            continue
        ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w, k = na()
s = nsn(h)

ans = inf
for bits in range(2 ** (h - 1)):
    binf = "{0:b}".format(bits)
    res = sum([int(b) for b in binf])
    divcnt = res + 1
    cnt = [0] * divcnt
    flag = True
    j = 0
    while j < w:
        cur = 0
        for i in range(h):
            if (s[i][j] == '1'):
                cnt[cur] += 1
            if bits >> i & 1:
                cur += 1
        if max(cnt) > k:
            if flag:
                res = inf
                break
            res += 1
            for i in range(divcnt):
                cnt[i] = 0
            flag = True
        else:
            flag = False
            j += 1
    ans = min(ans, res)

print(ans)

Submission status: Time Limit Exceeded

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

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)

    num_cnt = 0

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        for a in col_new:
            if a > K:
                flag = True
                break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                cnt_lst = col_new.copy()
                flag = True
                break

        if not flag:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    ret = min(ret, num_cnt + cut)


print(ret)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))
arr = np.array(arr)

def cut_sum(arr, x1, x2, y1, y2):
  return arr[x1:x2, y1:y2].sum()

row_idxes = list(range(1,H))
min_val = 10 ** 9

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    while col2 <= W:
      row1 = 0
      for row2 in row_lines[1:]:
        val = cut_sum(arr, row1, row2, col1, col2)
        if val > K:
          if (col2 - col1) == 1:
            count = 10 ** 9
            break
          count +=1
          col1 = col2 - 1
          col2 -= 1 
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))
arr = np.array(arr)

def cut_sum(arr, x1, x2, y1, y2):
  return arr[x1:x2, y1:y2].sum()

row_idxes = list(range(1,H))
min_val = 10 ** 9

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    while col2 <= W:
      row1 = 0
      for row2 in row_lines[1:]:
        val = cut_sum(arr, row1, row2, col1, col2)
        if val > K:
          if (col2 - col1) == 1:
            count = 10 ** 9
            break
          count +=1
          col1 = col2 - 1
          col2 -= 1 
          break
        row1 = row2
      if count == 10 **9:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)