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: Accepted

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

ans=1000000000009

for i in range(2**(h-1)):
    cut=0
    cut_n=[]
    b=[]
    for j in range(h-1):
        if (i>>j)&1:
            cut_n.append(j+1)
            cut+=1
    if len(cut_n)==0:
        ok=1
        dp=0
        for i in range(w):
            wa=0
            for j in range(h):
                wa+=cho[j][i]

            if dp+wa>k:
                cut+=1
                dp=wa
            else:
              dp+=wa

            if wa>k:
                ok+=1
                break
            
        if ok==1:
          ans=min(ans,cut)

    else:
        st=0
        for t in range(len(cut_n)):
            if t==len(cut_n)-1:
                b.append(cut_n[t]-st)
                b.append(h-cut_n[t])
            else:
              b.append(cut_n[t]-st)
              st=cut_n[t]
        
        dp=[0 for _ in range(len(b))]
        ok=1
        for y in range(w):
            for g in dp:
                if g>k:
                    ok+=1
                    break
            st=0
            ch=0
            c=[]
            for e in range(len(b)):
              p=b[e]
              temp=0
              for q in range(p):
                  temp+=cho[st+q][y]
                    
                  dp[e]+=cho[st+q][y]

              c.append(temp)
                
              st+=p

            for g in dp:
                if g>k:
                    ch+=1

            if ch!=0:
                cut+=1
                dp=c

            
            for last in c:
                  if last>k:
                      ok+=1

        
        if ok==1:
            ans=min(ans,cut)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
HW = [[0] * W for i in range(H)]
S = [0] * H
for i in range(H):
  x = str(input())
  for j in range(len(x)):
    HW[i][j] = int(x[j])
#print(HW) 

for i in range(H):
  S[i] = sum(HW[i])
#print(S)  

ans = H + W
for i in range(2 ** (H - 1)):#521 * 9
  time = 0
  now = 0
  cut = []
  for j in range(H - 1):
    if (i >> j) & 1:#j番目とj+1番目の間で割る
      cut.append(j)
  #print(cut)
  cut2 = [[] for _ in range(len(cut) + 1)]
  for j in range(len(cut)):
    for p in range(now, cut[j] + 1):
      cut2[j].append(p)
      now = cut[j] + 1
  for p in range(now, H):
    cut2[-1].append(p)
  #print(cut2)    
    
  time = len(cut2) - 1  
  choco = [0] * len(cut2)
  for l in range(W):
    for k in range(len(cut2)):
      nn = 0
      for p in cut2[k]:
        nn += HW[p][l]
      if nn > K:  
        time += 10000
      else:
        choco[k] += nn
      

    if max(choco) > K: 
      time += 1
      for k in range(len(cut2)):
        nn = 0
        for p in cut2[k]:
          nn += HW[p][l]
        choco[k] = nn  

  ans = min(ans, time)
  #print(i, time)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
acc = [[0] * (W + 1) for _ in range(H)]
for i in range(H):
    for j in range(1, W + 1):
        acc[i][j] = acc[i][j - 1] + int(S[i][j - 1])


ans = INF
for bit in range(1 << (H - 1)):
    base = 0
    vertical = []
    for i in range(H - 1):
        if bit & 1 << i > 0:
            vertical.append((base, i))
            base = i + 1
    vertical.append((base, H - 1))

    tmp_ans = len(vertical) - 1
    prev = 0
    j = 1
    valid = False
    while j <= W:
        ok = True
        for v in vertical:
            now = 0
            for i in range(v[0], v[1] + 1):
                now += acc[i][j] - acc[i][prev]
            if now > K:
                ok = False
        if ok:
            valid = True
        else:
            if valid:
                prev = j - 1
                tmp_ans += 1
                valid = False
                continue
            else:
                break
        j += 1
    if valid:
        ans = min(tmp_ans, ans)
print(ans)

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, K, Si):
    Si = [[int(i) for i in S] for S in Si]
    ans = H + W
    for i in range(2 ** (H - 1)):
        h_border = bin(i).count('1')
        w_border = 0
        white_counts = [0] * (h_border + 1)
        choco_w = 0
        for w in range(W):
            choco_w += 1
            wc_num = 0
            tmp_count = [0] * (h_border + 1)
            for h in range(H):
                white_counts[wc_num] += Si[h][w]
                tmp_count[wc_num] += Si[h][w]
                if i >> h & 1:
                    wc_num += 1
            if max(white_counts) > K:
                if choco_w == 1:
                    break  # 1列の時点で > K の場合は条件を達成できない
                w_border += 1
                white_counts = tmp_count
                choco_w = 1
        else:
            ans = min(ans, h_border + w_border)
    print(ans)


if __name__ == '__main__':
    H, W, K = map(int, input().split())
    Si = [input() for _ in range(H)]
    solve(H, W, K, Si)

    # # test
    # from random import randint
    # from func import random_str
    # 
    # H, W, K = 10, 1000, randint(1, 100)
    # Si = [random_str(W, '01') for _ in range(H)]
    # print(H, W, K)
    # for S in Si:
    #     print(S)
    # solve(H, W, K, Si)

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def search(topx, topy, botx, boty, grid):
    ret = grid[boty][botx]
    if topx > 0: ret -= grid[boty][topx - 1]
    if topy > 0: ret -= grid[topy - 1][botx]
    if topx > 0 and topy > 0: ret += grid[topy - 1][topx - 1]
    return ret

def Main():
    H, W, K = read_ints()
    chocolate = [list(read_str()) for _ in range(H)]
    
    grid = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if chocolate[h][w] == '1': grid[h][w] += 1
            if w > 0: grid[h][w] += grid[h][w - 1]
            if h > 0: grid[h][w] += grid[h - 1][w]
            if h > 0 and w > 0: grid[h][w] -= grid[h - 1][w - 1]

    ans = INF
    for bit in range(1 << ~-H):
        cnt = 0
        cut = []
        for h in range(~-H):
            if bit >> h & 1:
                cnt += 1
                cut.append(h)
        cut.append(~-H)

        white = [0] * len(cut)
        topx = 0
        flag = False
        for w in range(~-W):
            topy = 0
            for i in range(len(cut)):
                if search(topx, topy, w, cut[i], grid) > K:
                    flag = True
                    break
                white[i] = search(topx, topy, w+1, cut[i], grid)
                topy = cut[i] + 1
            if flag: break
            for x in white:
                if x <= K:
                    continue
                topx = w + 1
                cnt += 1
                break
        if not flag:
            ans = min(ans, cnt)
    print(ans)
    

if __name__ == '__main__':
    Main()

Submission status: Accepted

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

ans = h+w-2
for i in range(1 << (h-1)):
    tate = 0
    index = [0] * h
    # しきりはh-1個なので2個目から考える
    for j in range(h-1):
        if i & (1 << j):
            tate += 1
        index[j+1] = tate # チョコ軍の番号
    chocos = [0]*(tate + 1) # チョコ軍
    yoko = 0
    ok = True
    for j in range(w):
        for k in range(h):
            chocos[index[k]] += s[k][j]
            # kkを超えるたびにその直前に仕切りをいれて新しいチョコ軍について考える
        if max(chocos) > kk:
            yoko += 1
            chocos = [0]*(tate+1)
            for l in range(h):
                chocos[index[l]] += s[l][j]
            if max(chocos) > kk:# その列だけで超える
                ok = False
        if not ok:
            break
    if ok:
        ans = min(ans, tate + yoko)

print(ans)

Submission status: Accepted

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

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

C = [[0 for w in range(W)] for h in range(H)] #各行のw列目までに1が何個あるか

#print(S)
for h in range(H):
  for w in range(W):
    #print(h,w)
    C[h][w] = C[h][w-1] + S[h][w]

#print(C)
def settify(l):
  set_label = set()
  i = 0
  while l > 0:
    if l % 2 == 1:
      set_label.add(i)
    l //= 2
    i += 1
  return set_label
    
def set_label(s):
  tmp = 0
  for i in s:
    tmp += 2**i
  return tmp

def sum_set(s, w):
  s_list = list(s)
  s_list.sort()
  s_list.append(H-1)
  tmp = 0
  it = 0
  ans_list = []
  for h in range(H):
    tmp += C[h][w]
    #print(w, tmp)
    if h == s_list[it]:
      ans_list.append(tmp)
      tmp = 0
      it += 1
  return ans_list    
#print(sum_set(set(), 0), sum_set(set(), 1))
ans = 10**8
for l in range(2**(H-1)):
  s = settify(l)
  lt_prv = [0 for _ in range(len(s)+1)]
  lt_now = [0 for _ in range(len(s)+1)]
  lt_1minus = [0 for _ in range(len(s)+1)]
  tmp = len(s)
  w = 0
  w_prv = -1
  imp = False
  while w < W:
    lt_now = sum_set(s, w)
    flag = False
    for j in range(len(s)+1):
      if lt_now[j] - lt_prv[j] > K:
        flag = True
        break
    if flag:
      if w_prv == w-1:
        imp = True
      tmp += 1
      lt_prv = lt_1minus
      w_prv = w-1
    w += 1
    lt_1minus = lt_now
    if imp:
      break
    #print(s, w-1)
    #print(lt_prv, lt_1minus, lt_now)
  if not imp:
    ans = min(ans, tmp)
      
print(ans)

Submission status: Accepted

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

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

    res = min(res, cnt)

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

ret = 100000
for i in range(2 ** (h-1)):
    hi = [0] * h
    for j in range(h-1):
        hi[j+1] += hi[j] + (i >> j & 1)
    cnt = max(hi)
    pj = 0
    x = []
    while pj < w:
        s = [0] * 10
        fg = False
        for j in range(pj, w):
            for t in range(h):
                s[hi[t]] += a[t][j]
            if max(s)>k:
                if j == pj:
                    cnt = 100000
                    fg = True
                    break
                else:
                    x.append(j)
                    cnt += 1
                    pj = j
                break
            if j == w-1:
                pj = w
                break
        if fg:
            break
    ret = min(ret, cnt)
print(ret)

Submission status: Accepted

Solution code:
"""
Hが少ないので、縦で割るパターンは全探索して見る。
dpとか使わずに、貪欲的に割っていけばよい。

"""
H,W,K = map(int,input().split())
choco = [list(input()) for _ in range(H)]
accum = [[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        accum[i][j] = accum[i][j-1] + int(choco[i][j])

ans = float("INF")
for i in range(2**H):
    """
    i を2進数表記したときに1になっているインデックスに該当する行数で分割する。
    例えば00100なら3行目と4行目の間で分割する。
    """
    binI = format(i,"0"+str(H)+"b")
    group = {}
    groupNum = 0
    for j in range(H):
        group[j] = groupNum
        if binI[j] == "1":
            groupNum += 1
    breakCnt = groupNum
    tmp = [0]*(groupNum+1)
    for j in range(W):
        tmp2 = [0]*(groupNum+1)
        for k in range(H):
            groupNum = group[k]
            if choco[k][j] == "1":
                tmp2[groupNum] += 1
        if max(tmp2) > K:
            break
        else:
            for l in range(groupNum+1):
                tmp[l] += tmp2[l]
            if max(tmp) > K:
                breakCnt += 1
                tmp = tmp2
    else:
        ans = min(ans,breakCnt)
print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)
# 横に割る方法は2**(H-1)、高々2**9=512通り
# これを決め打ちして、縦の割り方はGreedyに

ans = 10**9

# 割る場合を1, 割らない場合を0で表すことにする
for ptn in itertools.product([0, 1], repeat=H - 1):

    # 不可能な場合、そのパターンはスキップする############################
    able = True
    for w in range(W):
        # それぞれのブロックにおける白の数
        lines = [0] * (sum(ptn) + 1)
        # 今、上から何ブロック目か
        line_num = 0
        for h in range(H):
            # 白の場合
            if grid[h][w] == "1":
                lines[line_num] += 1

            # 境界を引く場合
            # h=H-1の時、indexが範囲外になるのでminを使って調整
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # 1列でK個を超えるブロックがある場合、その割り方は不適。
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    # 以下、実現が可能なものとして考える################################

    # それぞれのブロックにおける白の数
    lines = [0] * (sum(ptn) + 1)
    # 横に割った回数
    cnt = sum(ptn)
    # ダメだったら1個前に戻る、という処理をしたいのでwhileで書く
    # for内でデクリメントしてもループにならない(自戒)
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            # 白の場合
            if grid[h][w] == "1":
                lines[line_num] += 1
            # 境界を引く場合
            # h=H-1の時、indexが範囲外になるのでminを使って調整
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # Kを超えるブロックができてしまう場合
        # 一つ前の列で切って、今の列からlinesを数え直す
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)
# 横に割る方法は(H-1)**2通り、高々81通り
# これを決め打ちして、縦の割り方はGreedyに

ans = 10**9

# 割る場合を1, 割らない場合を0で表すことにする
for ptn in itertools.product([0, 1], repeat=H - 1):

    # 不可能な場合、そのパターンはスキップする############################
    able = True
    for w in range(W):
        # それぞれのブロックにおける白の数
        lines = [0] * (sum(ptn) + 1)
        # 今、上から何ブロック目か
        line_num = 0
        for h in range(H):
            # 白の場合
            if grid[h][w] == "1":
                lines[line_num] += 1

            # 境界を引く場合
            # h=H-1の時、indexが範囲外になるのでminを使って調整
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # 1列でK個を超えるブロックがある場合、その割り方は不適。
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    # 以下、実現が可能なものとして考える################################

    # それぞれのブロックにおける白の数
    lines = [0] * (sum(ptn) + 1)
    # 横に割った回数
    cnt = sum(ptn)
    # ダメだったら1個前に戻る、という処理をしたいのでwhileで書く
    # for内でデクリメントしてもループにならない(自戒)
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            # 白の場合
            if grid[h][w] == "1":
                lines[line_num] += 1
            # 境界を引く場合
            # h=H-1の時、indexが範囲外になるのでminを使って調整
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # Kを超えるブロックができてしまう場合
        # 一つ前の列で切って、今の列からlinesを数え直す
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
import itertools
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    line = list(input())
    grid.append(line)
# 横に割る方法は(H-1)**2通り、高々81通り
# これを決め打ちして、縦の割り方はGreedyに

ans = 10**9

# 割る場合を1, 割らない場合を0で表すことにする
for ptn in itertools.product([0, 1], repeat=H - 1):

    # 不可能な場合、そのパターンはスキップする###############
    able = True
    for w in range(W):
        # それぞれのブロックにおける白の数
        lines = [0] * (sum(ptn) + 1)
        # 今、上から何ブロック目か
        line_num = 0
        for h in range(H):
            # 白の場合
            if grid[h][w] == "1":
                lines[line_num] += 1

            # 境界を引く場合
            # h=H-1の時、indexが範囲外になるのでminを使って調整
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # 1列でK個を超えるブロックがある場合、その割り方は不適。
        if max(lines) > K:
            able = False
            break
    if able == False:
        continue
    # 以下、実現が可能なものとして考える#####################

    lines = [0] * (sum(ptn) + 1)
    cnt = sum(ptn)
    w = 0
    while w < W:
        line_num = 0
        for h in range(H):
            if grid[h][w] == "1":
                lines[line_num] += 1
            if ptn[min(h, H - 2)] == 1:
                line_num += 1
        # print(ptn, w, lines)
        if max(lines) > K:
            cnt += 1
            lines = [0] * (sum(ptn) + 1)
            w -= 1
        w += 1
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    H,W,K=mi()
    
    G = []
    for i in range(H):
        G.append(list(input()))
    
    v = [[0] * W for _ in range(H+1)]
    for w in range(W):
        for h in range(H):
            white_choc = G[h][w] == "1"
            v[h+1][w] = v[h][w] + white_choc
    
    ans = INF
    for borders in bit_search(H):
        counts = [[0] for _ in range(20)]
        k_fact = 1
        W_borders = []

        failed = False
        from_zero = True
        w = 0
        while w < W:
            pre = 0
            over_K = False

            max_diff = 0
            for i,border in enumerate(borders):
                if border == 0: continue
                count = v[border][w] - v[pre][w]
                if not from_zero:
                    count += counts[i][-1]
                else:
                    if count > K:
                        failed = True
                        break
                
                if count > K:
                    over_K = True
                

                counts[i].append(count)
                pre = border
            
            count = v[H][w] - v[pre][w]
            if not from_zero:
                count += counts[i+1][-1]
            else:
                if count > K:
                    failed = True
                    break

    
            if count > K:
                over_K = True


            counts[i+1].append(count)
            if over_K:
                W_borders.append(w-1)
                from_zero = True

                for c in counts:
                    if len(c) == 0: continue
                    c.pop() # 直前のカウント履歴を消す
            else:
                from_zero = False
                w += 1

            
            if failed:
                break

        # print(counts)
        if not failed:
            # print(borders)
            # print(W_borders)
            # print(counts)
            # # # print(v[2])
            # # exit()
            count_of_ope = len(borders) + len(W_borders)
            ans = min(count_of_ope,ans)


    print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
H, W, K = MI()
S_ = [[] for _ in range(W)]
for i in range(H):
    s = S()
    for j in range(len(s)):
        S_[j].append(int(s[j]))



A = []
for i in range(2 ** (H - 1)):
    A_bit = []
    for j in range(H - 1):
        # 二進数表記でj回右にシフトして0桁目（一番下の桁）が1であればTrue
        if ((i >> j) & 1):
            A_bit.append(j)
    A.append(A_bit)


Ans_list = []
for a in A:
    sums = [0] * (len(a) + 1)
    ele = [0] * (len(a) + 1)
    ans = 0
    for s_ in S_:
        queue = deque(a)
        if queue == deque([]):
            ele[0] = sum(s_)
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_)
        else:
            x = queue.popleft()
            ele[0] = sum(s_[0:x + 1])
            if ele[0] > K:
                ans = 10 ** 6
                break
            sums[0] += sum(s_[0:x + 1])
            j = 1
            while queue != deque([]):
                y = queue.popleft()
                ele[j] = sum(s_[x + 1:y + 1])
                if ele[j] > K:
                    ans = 10 ** 6
                    break
                sums[j] += sum(s_[x + 1:y + 1])
                x = y
                j += 1
            ele[len(a)] = sum(s_[x + 1:H])
            if ele[len(a)] > K:
                ans = 10 ** 6
                break
            sums[len(a)] += sum(s_[x + 1:H])
        if max(sums) > K:
            ans += 1
            for k in range(len(a) + 1):
                sums[k] = ele[k]
    ans += len(a)
    Ans_list.append(ans)

print(min(Ans_list))

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [list(map(int, input())) for i in range(h)]
ans = h+w-2
for i in range(2**(h-1)):
    index = [0] * h
    rowcuts = 0
    for j in range(h-1):
        if 1 & (i >> j) == 1:
            rowcuts += 1
        index[j + 1] = rowcuts
    chocos = [0] * (rowcuts + 1)
    coulmncuts = 0
    valid = True
    for j in range(w):
        for l in range(h):
            chocos[index[l]] += s[l][j]
        if max(chocos) > k:
            coulmncuts += 1
            chocos = [0] * (rowcuts + 1)
            for l in range(h):
                chocos[index[l]] += s[l][j]
            if max(chocos) > k:
                valid = False
        if not valid:
            break
    if valid:
        ans = min(ans, rowcuts + coulmncuts)

print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
ans = float("inf")
for bit in range(1 << (h - 1)):
    cnt = 0
    l = [0] * h
    for i in range(h - 1):
        if bit & (1 << i):
            cnt += 1
        l[i + 1] = cnt
    m = max(l) + 1
    cnt2 = m - 1
    c = [0] * m
    for j in range(w):
        cur = [0] * m
        for i in range(h):
            c[l[i]] += int(s[i][j])
            cur[l[i]] += int(s[i][j])
            if c[l[i]] > k:
                cnt2 += 1
                for i in range(m):
                    c[i] = cur[i]
    ans = min(ans, cnt2)
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
s=[[int(x) for x in list(input())] for _ in range(H)]
ans = H*W
for h in range(2**(H-1)):
  parts = list()
  upper = 0
  cnt = 0
  inv_flg = 0
  for j in range(H-1):
    if h >> j & 1:
      cnt += 1
      appending = [sum([s[y][x] for y in range(upper, j+1)]) for x in range(W)]
      if any([x> K for x in appending]):
        inv_flg = 1
        break
      parts.append(appending)
      upper = j+1
  else:
    appending = [sum([s[y][x] for y in range(upper, H)]) for x in range(W)]
    if any([x > K for x in appending]):
      inv_flg = 1
    else:
      parts.append(appending)
  if inv_flg:
    continue
  # 貪欲
  summary = [0]*len(parts)
  for i in range(W):
    temp_sum = [summary[j] + parts[j][i] for j in range(len(parts))]
    for ts in temp_sum:
      if ts > K:
        cnt += 1
        summary = [parts[j][i] for j in range(len(parts))]
        break
    else:
      summary = temp_sum
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
h,w,k=map(int,input().split())
s=[[0]*(w+1)]+[[0]+[int(i) for i in input()] for _ in range(h)]
for i in range(h+1):
  s[i]=list(accumulate(s[i]))
for j in range(w+1):
  for i in range(h):
    s[i+1][j]+=s[i][j]
ans=10**18
for i in range(1<<h-1):
  a=[]
  for j in range(h-1):
    if (i>>j)&1:a+=[j+1]
  a+=[h]
  cnt=len(a)-1
  q=1
  for j in range(1,w+1):
    p=0
    flag=0
    for l in a:
      if s[l][j]-s[l][j-1]-s[p][j]+s[p][j-1]>k:flag=1
      elif s[l][j]-s[l][q-1]-s[p][j]+s[p][q-1]>k:
        q=j
        cnt+=1
        break
      else:p=l
    if flag:break
  else:
    ans=min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    h, w, k = map(int, input().split())
    s_s = [list(input()) for i in range(h)]

    # パターン数分の情報を作成(横に切る = 最大2^10個)
    # 全パターンの・・横に切る回数、と切る場所
    side = []
    for i in range(1 << h - 1):
        cut_cnt = 0
        point_s = []
        # パターンの桁数分ループ
        for j in range(h - 1):
            # フラグが立つ(bitが1)の場合の処理を以下に記載。
            if i & 1 << j:
                cut_cnt += 1
                point_s.append(j + 1)

        point_s.append(h)
        # 得た情報をリストに追加
        side.append([point_s, cut_cnt])

    ## 横切り必須にもかかわらず、横木入りしていないパターンを排除できていない・・と思われる。
    x_s_s = list(zip(*s_s))
    ans = 999999
    for side_cut_point_s, cut_cnt in side:
        # 横切りを実施した後の塊を取得
        cnt_s = [0 for i in range(cut_cnt + 1)]

        for x_s in x_s_s:
            start = 0
            for cnt, side_cut_point in enumerate(side_cut_point_s):
                cnt_s[cnt] += x_s[start: side_cut_point].count("1")
                start = side_cut_point
            # 切る必要がある場合は切る
            if max(cnt_s) > k:
                cut_cnt += 1
                start = 0
                for cnt, side_cut_point in enumerate(side_cut_point_s):
                    cnt_s[cnt] = x_s[start: side_cut_point].count("1")
                    start = side_cut_point
            if max(cnt_s) > k:
                cut_cnt += 99999
        ans = min(ans, cut_cnt)

    print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3 5 4
11100
10001
00111"""
        output = """2"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """3 5 8
11100
10001
00111"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 10 4
1110010010
1000101110
0011101001
1101000111"""
        output = """3"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def test_1original_1(self):
        test_input = """10 10 1
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000
1000000000"""
        output = """9"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            cum[i][j]=cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+int(S[i-1][j-1])
    ans = 2000
    for p in product([0,1],repeat=H-1):
        line = [0]
        p = list(p)
        cnt = sum(p)
        for i in range(1,H):
            if p[i-1]==1:
                line.append(i)
        line.append(H)
        w_s = 0
        w_e = 1
        b = False
        while w_e <= W:
            for i in range(len(line)-1):
                h_s = line[i]
                h_e = line[i+1]
                white = cum[h_e][w_e]+cum[h_s][w_s]-cum[h_e][w_s]-cum[h_s][w_e]
                if white > K:
                    if w_e == w_s+1:
                        b = True
                        break
                    else:
                        w_s = w_e-1
                        cnt += 1
                        break
            if b==True:
                break
            w_e += 1
        else:
            ans = min(ans,cnt)
    return ans
print(solve())