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:
import itertools
# tempt
H,W,K=map(int,input().split())
S=[input() for _ in range(H)]

ans=1e4 # 10000(10**4)
for t in itertools.product([0,1],repeat=H-1):
    cnt=t.count(1)
    SW=[]
    tmp=[int(s) for s in S[0] ]
    
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i + 1]]
        else:
            tmp = [tmp[j] + int(S[i + 1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

def main():
  for h in range(H):
    for w in range(W):
      T[h][w]=T[h][w-1]+S[h][w]

  for h in range(1,H):
    for w in range(W):
      T[h][w]=T[h][w]+T[h-1][w]

  m=(H-1)*(W-1)
  for p in range(2**(H-1)):
    D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
    c,b=0,-1
    f=False
    for w in range(W):
      u=-1
      for d in D:
        if T[d][w]-T[u][w]-T[d][b]+T[u][b]>K:
          if b==w-1:
            f=True
          c,b=c+1,w-1
          break
        u=d
      if f==True:
        break
    else:
      m=min(m,c+len(D)-1)
  print(m)
main()

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

for h in range(H):
  for w in range(W):
    T[h][w]=T[h][w-1]+S[h][w]

for h in range(1,H):
  for w in range(W):
    T[h][w]=T[h][w]+T[h-1][w]

m=(H-1)*(W-1)
for p in range(2**(H-1)):
  D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
  c,b=0,-1
  f=False
  for w in range(W):
    u=-1
    for d in D:
      if T[d][w]-T[u][w]-T[d][b]+T[u][b]>K:
        if b==w-1:
          f=True
        c,b=c+1,w-1
        break
      u=d
    if f==True:
      break
  else:
    m=min(m,c+len(D)-1)
print(m)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = SRL(h)
ans = INF
for bits in range(2 ** (h - 1)):
    res = sum([int(j) for j in "{0:b}".format(bits)])
    div_cnt = res + 1
    cnt = [0] * div_cnt
    x = 0
    flg = 0
    while x < w:
        cur = 0
        for y in range(h):
            if s[y][x] == '1':
                cnt[cur] += 1
            if bits >> y & 1:
                cur += 1
        if max(cnt) > k:
            if flg == 0:
                res = INF
                break
            else:
                cnt = [0] * div_cnt
                flg = 0
                res += 1
        else:
            flg = 1
            x += 1
    ans = min(ans, res)


print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]

def count(x1,y1,x2,y2): #事前に求めた2次元累積和を用いて左上の点が(x1,y1)、右下の点(x2,y2)の長方形に含まれる1の個数を数える
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

for i in range(h): #2次元累積和により左上の点が(0,0)、右下の点が(j,i)の長方形に含まれる1の個数を数える
  for j in range(w):
    if board[i][j] == '1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]

ans = 10**18
for i in range(2**(h-1)):
  cnt = 0
  list = []
  flag = format(i,'b')[::-1] # '1'と'10'と'100'の区別のために必要
  #print(flag)
  for j in range(len(flag)):
    if flag[j] == '1': # ''をつける！
      cnt += 1
      list.append(j)
  list.append(h-1)
  #print(list)
  x1 = 0
  for x2 in range(w-1): #x1(最初は0)とx1+1の間からx=w-1とx=wの間までの区切り方をそれぞれ確かめる
    y1 = 0
    for y2 in list: #長方形のブロックの右下の点のy座標の候補をすべて試す
      if count(x1,y1,x2,y2) > k: #ある横の区切り方の下で、どのように縦を区切ってもブロックに含まれる1の個数がKより大きくなるとき、条件を満たす切り分け方は存在しない
        cnt += 10**18
      if count(x1,y1,x2,y2) <= k and count(x1,y1,x2+1,y2) > k: #ある位置でブロックを区切ると1の個数がK以下になるが、区切る位置を1つ進めると1の個数がKより大きくなるとき、その位置で区切る必要がある
        cnt += 1
        x1 = x2+1 #ある位置x2で区切ったとき、次からはx2+1を長方形のブロックの左上の点のx座標として見ればよい
        break
      y1 = y2+1 #(いま見ているブロックの右下の点のy座標)+1が次に見るブロックの左上の点のy座標に等しくなる
  y1 = 0
  for y2 in list:
    if count(x1,y1,w-1,y2) > k: #最後に縦で区切った位置以降で、あるブロックに含まれる1の個数がKより大きくなるとき、条件を満たすような区切り方は存在しない
      cnt += 10**18
      break
    y1 = y2+1
  ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]

def count(x1,y1,x2,y2): #事前に求めた2次元累積和を用いて左上の点が(x1,y1)、右下の点(x2,y2)の長方形に含まれる1の個数を数える
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

for i in range(h): #2次元累積和により左上の点が(0,0)、右下の点が(j,i)の長方形に含まれる1の個数を数える
  for j in range(w):
    if board[i][j] == '1': # ''をつける！
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]

ans = 10**18
for i in range(2**(h-1)):
  cnt = 0
  list = []
  flag = format(i,'b')[::-1]
  for j in range(len(flag)):
    if flag[j] == '1': # ''をつける！
      cnt += 1
      list.append(j)
  list.append(h-1)
  x1 = 0
  for x2 in range(w-1): #x1(最初は0)とx1+1の間からx=w-1とx=wの間までの区切り方をそれぞれ確かめる
    y1 = 0
    for y2 in list: #長方形のブロックの右下の点のy座標の候補をすべて試す
      if count(x1,y1,x2,y2) > k: #ある横の区切り方の下で、どのように縦を区切ってもブロックに含まれる1の個数がKより大きくなるとき、条件を満たす切り分け方は存在しない
        cnt += 10**18
      if count(x1,y1,x2,y2) <= k and count(x1,y1,x2+1,y2) > k: #ある位置でブロックを区切ると1の個数がK以下になるが、区切る位置を1つ進めると1の個数がKより大きくなるとき、その位置で区切る必要がある
        cnt += 1
        x1 = x2+1 #ある位置x2で区切ったとき、次からはx2+1を長方形のブロックの左上の点のx座標として見ればよい
        break
      y1 = y2+1 #(いま見ているブロックの右下の点のy座標)+1が次に見るブロックの左上の点のy座標に等しくなる
  y1 = 0
  for y2 in list:
    if count(x1,y1,w-1,y2) > k: #最後に縦で区切った位置以降で、あるブロックに含まれる1の個数がKより大きくなるとき、条件を満たすような区切り方は存在しない
      cnt += 10**18
      break
    y1 = y2+1
  ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
def main():
  from collections import Counter
  from collections import defaultdict
  from collections import deque
  from itertools import accumulate
  from itertools import combinations
  from itertools import permutations
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# E - Dividing Chocolate
import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H+W

for i in range(H):
    S[i] = list(str(input()))

for m in range(1<<(H-1)):
    cut = bin(m).count('1')
    if cut >= ans:
        continue

    wp = np.zeros((cut+1, W), dtype=np.int64)
    wp[0] = S[0]
    c = 0
    for n in range(H-1):
        if m>>n&1:
            c += 1
        wp[c] += S[n+1]

    if np.count_nonzero(wp > K):
        continue

    wq = np.zeros((cut+1, ), dtype=np.int64)
    for j in range(W):
        wq += wp[:,j]
        if np.count_nonzero(wq > K):
            cut += 1
            wq = wp[:,j]

    ans = min(ans, cut)

print(ans)

Submission status: Accepted

Solution code:
# E - Dividing Chocolate
import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H+W

for i in range(H):
    S[i] = list(str(input()))

for m in range(2**(H-1)):
    wp = np.zeros((H, W), dtype=np.int64)
    wq = np.zeros((H, ), dtype=np.int64)
    wp[0] = S[0]
    cut = 0
    for n in range(H-1):
        if m>>n&1:
            cut += 1
        wp[cut] += S[n+1]

    if cut >= ans or np.count_nonzero(wp > K):
        continue

    for j in range(W):
        wq += wp[:,j]
        if np.count_nonzero(wq > K):
            cut += 1
            wq = wp[:,j]
    ans = min(ans, cut)

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
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()))))

def cut_sum(arr, x1, x2, y):
  ret = 0
  for i in range(x1, x2):
    ret += arr[i][y]
  return ret

row_idxes = list(range(1,H))
min_val = float('inf')

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
    sums = [0] * (len(row_lines) - 1)
    while col2 <= W:
      row1 = 0
      for box, row2 in enumerate(row_lines[1:]):
        sums[box] += cut_sum(arr, row1, row2, col2-1)
        if sums[box] > K:
          if (col2 - col1) == 1:
            count = float('inf')
            break
          count += 1
          col1 = col2 - 1
          col2 -= 1
          sums = [0] * (len(row_lines) - 1)
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)

Submission status: Accepted

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

n,m,K = inpl()
s = [input() for _ in range(n)]
res = INF
for pat in itertools.product([0,1], repeat=n-1):
    pat = list(pat) + [0]
    group = []
    tmp = []
    for i,j in enumerate(pat):
        tmp += [i]
        if j or i == n-1:
            group += [tmp]
            tmp = []
    
    ln = len(group)
    white = [[0]*ln for _ in range(m)]
    ccc = set()
    cnt = pat.count(1) 
    ok = True
    for i in range(m):
        for j,z in enumerate(group):
            for k in z:
                if s[k][i] == '1':
                    white[i][j] += 1
            if max(white[i]) > K:
                ok = False
                break
    if not ok: continue
    
    now = [0] * ln
    for i in range(m):
        ok = True
        for j in range(ln):
            if now[j] + white[i][j] > K:
                ok = False
                break
        if ok:
            for j in range(ln):
                now[j] += white[i][j]
        else:
            cnt += 1
            for j in range(ln):
                now[j] = white[i][j]
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=[[0 for i in [0]*W] for j in [0]*H]
DO=[[0 for i in [0]*W] for j in [0]*H]
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
CO[H-1]=DO[H-1]
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if Sui[k]==0:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]+CO[H-k-1][i]
  else:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]
 lst=[0]*H
 for h in range(W):
  c=max(CO[x][h] for x in range(H))
  d=max(lst[y]+CO[y][h] for y in range(H))
  if c>K:
   E=1000000
   break
  elif d>K:
   D+=1
   lst=[0]*H
  for z in range(H):
   lst[z]+=CO[z][h]
 F=min(F,D+E)
print(F)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")

# bit全探索
for i in range(2**(H-1)):
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    # 横に割った回数
    divcnt = L-1
    # 横に割った区割りごとの白チョコの個数
    wcnt = [0]*L
    # 探索列の横に割った区割りごとの白チョコの個数
    tmp = [0]*L
    for w in range(W):
        # 探索列の直前で縦に割ったか
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
                if cnt > K: break
            else:
                tmp[idx] = cnt
                wcnt[idx] += cnt
                if wcnt[idx] > K: flag = True
                continue
            break
        else:
            if flag:
                # 縦に割ったらその列から数え直し
                wcnt = tmp[:]
                divcnt += 1
            continue
        break
    else:
        ans = min(ans,divcnt)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    num = g - 1

    if num >= ans:
        continue

    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    now = [0 for _ in range(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):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(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

    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
h,w,k=[int(j) for j in input().split()]
s=[list(map(int,list(input()))) for i in range(h)]
import itertools
s=tuple(itertools.chain(*zip(*s)))
ans=10**18
for i in range(1<<(h-1)):
    dp=list(s)
    for j in range(h-1):
        if i&(1<<j):
            for n in range(0,h*w,h):
                dp[n+j+1]+=dp[n+j]
    tmp=h-1-bin(i).count("1")
    b=False
    for n in range(0,h*w,h):
        if any(dp[n+j]>k for j in range(h)):
            tmp=10**18
            break
        if n+h==h*w:
            ans=min(ans,tmp)
            tmp=10**18
            break
        if any(dp[n+j]+dp[n+j+h]>k for j in range(h)):
            tmp+=1
            continue
        for j in range(h):
            dp[n+j+h]+=dp[n+j]
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w,k = m()

s = []

for i in range(h):
    s.append(list(map(int,input()[:-1])))

st = [0 for i in range(h)]
dp = [[0,0] for i in range(h)]
ans = mod

for po in range(2 << h):
    de = 0
    tm = 0
    for j in range(h):
        dp[j][0] = 0
        dp[j][1] = 0
    for j in range(h):
        if j == 0:
            st[0] = 0
        else:
            a = (po>>j)&1
            b = (po>>(j-1))&1
            if a != b:
                de += 1
            st[j] = de
            
    tm += de
    
    for kp in range(w):
        fl = 0
        for kk in range(h):
            if s[kk][kp] == 1:
                dp[st[kk]][1] += 1
        if all(dp[x][0] + dp[x][1] <= k for x in range(h)):
            for kk in range(h):
                dp[kk][0] += dp[kk][1]
                dp[kk][1] = 0
        else:
            tm += 1
            for kk in range(h):
                if dp[kk][0] > k:
                    fl = 1
                    break
                dp[kk][0] = dp[kk][1]
                dp[kk][1] = 0
        if fl:
            break
    else:
        ans = min(tm,ans)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

# 転置 + 行ごと(つまり列ごと)の白チョコの数を数えている
accs = [[0]+list(accumulate(l)) for l in zip(*S)]

ans = float('inf')

for i in range(1 << H - 1):
    parts = []
    cuts = 0
    for k in range(H - 1):
        if i & (1 << k):
            cuts += 1
            parts.append(k+1)
    
    parts.append(H)
    cts = [0]*len(parts)
    for j in range(W):
        prev = 0
        flag1 = False
        for idx, p in enumerate(parts):
            c = accs[j][p] - accs[j][prev]
            cts[idx] += c
            if cts[idx] > K:
                flag1 = True
                break
            prev = p
        if flag1:
            cuts += 1
            prev = 0
            flag2 = False
            for idx, p in enumerate(parts):
                c = accs[j][p] - accs[j][prev]
                if c > K:
                    flag2 = True
                    break
                cts[idx] = c
                prev = p
            if flag2:
                break
    else:
        ans = ans if ans < cuts else cuts

print(ans)

Submission status: Accepted

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

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    if max([max(l) for l in c]) > k:
        continue

    tmp_ans = g - 1
    now = [0] * g

    for j in range(w):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > k:
                tmp_ans += 1
                now = [c[gi][j] for gi in range(g)]
                break

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

import itertools
from collections import defaultdict
ZO = [0,1]

CHOCO = []
for i in range(H):
    s = input()
    CHOCO.append(s)

ans = 10**16
C = 0

for i in itertools.product(ZO,repeat = H-1):
    saki = 0
    To = defaultdict(int)
    To[0] = saki
    for j in range(H-1):
        if i[j]==0:
            To[j+1] = saki
        else:
            saki += 1
            To[j+1] = saki
    tmpans = saki
    #print(To,tmpans)
    NowWhite = [0]*(saki+1)
    preW = 0
    for w in range(W):
        h = 0
        while 1:
            C+= 1
            #print(NowWhite,h)
            #if C>10000:
              #break
            if CHOCO[h][w] == '1':
                NowWhite[To[h]] += 1
                if NowWhite[To[h]] > K:
                    #print('break')
                    tmpans += 1
                    NowWhite = [0]*(saki+1)
                    h = -1
                    if preW==w:
                        tmpans += 10**16
                        break
                    preW = w
            if h==H-1:
                #print('h==H-1')
                break
            h += 1
    ans = min(ans,tmpans)
print(ans)

Submission status: Accepted

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

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = g - 1
    now = [0] * g

    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > k:
                return False
        return True

    for j in range(w):
        if not add(j):
            tmp_ans += 1
            now = [0] * g
            if not add(j):
                tmp_ans = INF
                break

    # impossible = 0
    # for j in range(w):
    #     if impossible:
    #         tmp_ans = INF
    #         break
    #     for i in range(g):
    #         if c[i][j] > k:
    #             impossible = 1
    #             break
    #         now[i] += c[i][j]
    #         if now[i] > k:
    #             now = [c[gi][j] for gi in range(g)]
    #             tmp_ans += 1
    #             continue

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = 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):
            tmp_ans += 1
            now = [0] * g
            if not add(j):
                tmp_ans = INF
                break

    # impossible = 0
    # for j in range(w):
    #     if impossible:
    #         tmp_ans = INF
    #         break
    #     for i in range(g):
    #         if c[i][j] > k:
    #             impossible = 1
    #             break
    #         now[i] += c[i][j]
    #         if now[i] > k:
    #             now = [c[gi][j] for gi in range(g)]
    #             tmp_ans += 1
    #             continue

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

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

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

#　１行目、一列目をゼロにする。
s=[[0]*w]+s
for i in range(h+1):
    s[i]=[0]+s[i]

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False
                
            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1]+s[line[l]][x],v)
            
        if v>k:
            cnt+=1
            x=k1-1
            
    if flag:
        ans=min(cnt,ans)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1].copy())
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    for j in cuts:
        if any(k > K for k in j):
            break
    else:
        h = len(cuts)
        tmp = [0] * h

        for j in range(W):
            for k in range(h):
                tmp[k] += cuts[k][j]
            for k in tmp:
                if k > K:
                    cnt += 1
                    tmp = [cuts[l][j] for l in range(h)]
                    break
        if cnt < answer:
            answer = cnt

print(answer)

Submission status: Accepted

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

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

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

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

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


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

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False
            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1]+s[line[l]][x],v)

        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)