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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

H,W,K = inputIL()
C = inputSLs(H)


best = INF
for h in range(pow(2,H-1)):
  nC = []
  nC.append([int(i) for i in C[0]])
  for i in range(1,H):
    if h>>(i-1) & 1:
      for j in range(W):
        nC[-1][j] += int(C[i][j])
    else:
      nC.append([int(j) for j in C[i]])
  n = len(nC)
  if max(max(nC[i]) for i in range(n)) > K:
    continue
  count = [0 for j in range(n)]
  cut = 0
  while len(nC[0]):
    now = [nC[j].pop() for j in range(n)]
    if max(count[j]+now[j] for j in range(n)) > K:
      count = now
      cut += 1
    else:
      count = [count[j]+now[j] for j in range(n)]
  
  yoko = H-1
  while h:
    h &= h -1
    yoko -= 1
  best = min(best,cut+yoko)

print(best)

Submission status: Accepted

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

ans = float('inf')
for hb in range(2**(H-1)):
    hl = []
    for i in range(H-1):
        if hb & (1 << i) > 0:
            hl.append(i+1)
    t = len(hl)
    hl = [0]+hl+[H]

    w, pw = 0, 0
    wl = [0]*len(hl)
    while w < W:
        ok = True
        for i in range(len(hl)-1):
            sh, eh = hl[i], hl[i+1]
            for h in range(sh, eh):
                wl[i] += m[h][w]
                if wl[i] > K:
                    ok = False
                    break
            if not ok:
                break

        if not ok:
            if pw == w:
                t = float('inf')
                break
            pw, w = w, w
            t += 1
            wl = [0]*len(hl)
        else:
            w += 1

    ans = min(t, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

h, w, k = inpl()
s = [input()[:-1] for _ in range(h)]
ans = 10 ** 4
for t in itertools.product([0, 1], repeat=h-1):
    cnt = t.count(1)
    tmp = s[0]
    SW = []  # 縦方向に圧縮したマップを格納
    tmp = [int(s) for s in s[0]] # tmp[j]=横方向に切ったブロックのj列目の総和
    for i, c in enumerate(t):
        if c: #横に切る
            SW.append(tmp) # SWが確定する
            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)
    new_h = len(SW)  #圧縮後の高さ
    sums = [0] * new_h
    if max(itertools.chain.from_iterable(SW)) > k:
        # itertools.chain.from_iterable([[A,B],[C,D]]) -> A,B,C,D
        # 各マスの時点でダメだったらこの横の切り方ではだめ
        continue
    for j in range(w):
        sumtmp = [sums[i] + SW[i][j] for i in range(new_h)]
        if max(sumtmp) > k:
            # 左から足してみてどこかがkを超えるようなら切る
            cnt += 1
            sums = [SW[i][j] for i in range(new_h)]  #新しいSW[i][j]で上書き
        else:
            sums = sumtmp
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    m, n, k = map(int, input().split())
    grid = [list(map(int, input())) for _ in range(m)]
    
    # grid が 1 の個数を k 以下にする
    # m <= 10 なので、m についてどこで切るかを全探索 -> その後 n について貪欲
    res = INF
    def adding(j):
        for i in range(m):
            counter[index_to_number[i]] += grid[i][j]

    for U in range(1 << (m - 1)):
        counter = Counter()
        index_to_number = [None] * m
        now = 0
        for i in range(m):
            index_to_number[i] = now
            now += (U >> i) & 1
        score = bin(U).count('1')
        # print(U, index_to_number)
        for j in range(n):
            # 一旦足してみる
            adding(j)
            if max(counter.values()) > k:
                score += 1
                counter.clear()
                adding(j) # もう1回やりなおす
                if max(counter.values()) > k: # やりなおした結果ダメなら無理
                    break
        else: # break されずに済めば OK
            res = min(res, score)

    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    m, n, k = map(int, input().split())
    grid = [list(map(int, input())) for _ in range(m)]
    # grid が 1 の個数が k 以下にする
    # m <= 10 なので、m についてどこで切るかを全探索 -> その後 n について貪欲
    res = INF

    counter = Counter()
    index_to_number = [None] * m
    def adding(j):
        for i in range(m):
            counter[index_to_number[i]] += grid[i][j]

    for U in range(1 << (m - 1)):
        counter.clear()
        index_to_number = [None] * m
        now = 0
        for i in range(m):
            index_to_number[i] = now
            now += (U >> i) & 1
        score = bin(U).count('1')
        # print(U, index_to_number)
        for j in range(n):
            # 一旦足してみる
            adding(j)
            if max(counter.values()) > k:
                score += 1
                counter.clear()
                adding(j) # もう1回やりなおす
                if max(counter.values()) > k: # やりなおした結果ダメなら無理
                    break

        else: # break されずに済めば OK
            res = min(res, score)
    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline


ans = INF
H,W,K = MI()
s = LSI2(H)
for pattern in product([0,1],repeat=H-1):
    cut = 0
    before_idx = 0
    row_list = []
    for i,div in enumerate(pattern):
        if div==1:
            cut += 1
            square = s[before_idx:i+1]
            inv = list(zip(*square))
            row = [sum(inv[i]) for i in range(W)]
            row_list.append(row)
            before_idx = i+1
    square = s[before_idx:] #のこりのブロック
    inv = list(zip(*square))
    row_list.append([sum(inv[i]) for i in range(W)])
    if any([any([c>K for c in r]) for r in row_list]):
        continue
    cnt = [0]*len(row_list)
    tmp = [0]*len(row_list)
    for i in range(W):
        for j in range(len(row_list)):
            cnt[j] += row_list[j][i]
            tmp[j] = row_list[j][i]
        if any([c>K for c in cnt]):
            cut += 1
            cnt = tmp[:]
    ans = min(ans,cut)
print(ans)

Submission status: Accepted

Solution code:
import copy
import itertools

h, w, k = map(int, input().split())
#s= list(input())

s = []
min = 100000
for i in range(h):
    s.append( [int(s) for s in list(input())])
    #s.append([1]*w)

dbg_cnt = 0
l = list(range(h-1))
for i in range(h):
    p = list(itertools.combinations(l, i))
    for j in p:
        tmp = list(j)
        tmps = []
        q = 0
        tmps.append([])
        #print(dbg_cnt)
        #dbg_cnt += 1
        for r in range(h):
            tmps[q].append(copy.copy(s[r]))
            if(q < len(tmp) and r==tmp[q]):
                tmps.append([])
                q += 1
        #print(tmps)
        count = i
        sums = [0] * len(tmps)
        precut = 1
        exitflg = 0
        for r in range(w): #550000
            for q in range(len(tmps)):
                for t in tmps[q]:
                    sums[q] += t[r] #5500000
            cutflg = 0
            for q in range(len(tmps)):
                if sums[q] > k : #5500000
                    cutflg = 1
            if cutflg == 1:
                #print('cut')
                count += 1
                sums = [0] * len(tmps)
                for q in range(len(tmps)):
                    for t in tmps[q]:
                        sums[q] += t[r] #5500000
            for q in range(len(tmps)): #5500000
                if sums[q] > k :
                    exitflg = 1
                    #print('exit')
        #print(exitflg)
        if exitflg == 0:
            if min > count:
                min = count
print(min)

Submission status: Accepted

Solution code:
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  for d in f(h):
    if i>>d&1: e+=[(u,d+1)]; c+=1; u=d+1
  e+=[(u,h)]
  for r in f(w):
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
  else: a=min(a,c)
print(a)

Submission status: Accepted

Solution code:
f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in input()] for _ in f(h)]
s=[[0]*-~w for _ in f(h+1)]
for i in f(h):
  for j in f(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
a=h+w
for i in f(2**~-h):
  u=d=l=r=c=0
  e=[]
  while d<h:
    d+=1
    if i>>d-1&1: e+=[(u,d)]; c+=1; u=d
  e+=[(u,h)]
  while r<w:
    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:
      if r==l: break
      c+=1; l=r
    r+=1
  else: a=min(a,c)
print(a)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
g=[[int(c) for c in input()] for _ in range(h)]
s=[[0]*(w+1) for _ in range(h+1)]
for i in range(h):
  for j in range(w):
    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]
ssum=lambda u,d,l,r:s[d][r]-s[u][r]-s[d][l]+s[u][l]
a=h+w
for i in range(2**(h-1)):
  e=[]
  u=d=ch=0
  for j in range(h):
    d+=1
    if i>>j&1<1:
      e+=[(u,d)]
      if d<h:
        ch+=1
        u=d
  l=r=cw=0
  while r<w:
    if max(ssum(u,d,l,r+1) for u,d in e)>k:
      if r==l: break
      cw+=1
      l=r
    r+=1
  else:
    a=min(a,ch+cw)
print(a)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
import bisect
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

def check(j):
    global cur

    for i in range(g):
        cur[i] += c[i][j]

    flag = True
    for curr in cur:
        if curr > K:
            flag = False

    return flag

H, W, K = LI()
S = RS(H)

ans = INF
N = H-1
for bit in range(1 << N):
    g = 0
    id = [0] * H

    for i in range(H):
        id[i] = g
        if (bit >> i) & 1:
            g += 1

    g += 1    
            
    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(S[i][j])

    num = g-1
    cur = [0] * g
    for i in range(W):
        if not check(i):
            num += 1
            cur = [0] * g

            if not check(i):
                num = INF
                break
    
    ans = min(ans, num)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print(0)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])
 
ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]
 
    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
 
    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue
 
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1
 
    # 横に割った分を加算
    tmp_ans += len(div) - 2
    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 list(input())] for _ in range(h)]

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

def cnt(line,i,j):
  if i == 0:
    return ssum[j-1][line]
  else:
    return ssum[j-1][line] - ssum[i-1][line]

ans = 10**6
for i in range(2**(h-1)):
  l = [0]
  s = 0
  for j in range(h):
    if i >> j & 1:
      s += 1
      l.append(j+1)
  l.append(h)
  d = [0]*(len(l)-1)
  for j in range(w):
    nxt = [cnt(j,l[k],l[k+1]) for k in range(len(l)-1)]
    d2 = [nxt[i]+d[i] for i in range(len(l)-1)]
    if max(nxt) > K:
      s = 10**7
      break
    if max(d2) > K:
      d = nxt
      s += 1
    else:
      d = d2
  ans = min(ans,s)
print(ans)

Submission status: Accepted

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

h, w, K = map(int, input().split())
s = []
for i in range(h):
    s.append(input().rstrip())

ans = float('inf')

for i in range(2 ** (h-1)):
    # 仕切り 1, 2, ...
    sep = [0]
    for j in range(h-1):
        if i & (1 << j):
            sep.append(j+1)

    memo = [0 for _ in range(len(sep))]
    cnt = 0
    

    # print(memo)
    # print('new sep: {}'.format(sep))

    for k in range(w):
        # print(memo)
        memo2 = [0 for _ in range(len(sep))]
        sep_index = 0
        for l in range(h):
            # print(sep_index)
            if sep_index < len(sep) - 1 and sep[sep_index+1] <= l:
                sep_index += 1
                # print('yay', l, sep_index)
            if s[l][k] == '1':
                if memo[sep_index] + memo2[sep_index] == K:
                    cnt += 1
                    memo = [0 for _ in range(len(sep))]
                memo2[sep_index] += 1
                if memo2[sep_index] > K:
                    cnt += ans
        for ii in range(len(sep)):
            memo[ii] += memo2[ii]
    ans = min(ans, cnt + len(sep) - 1)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, input())) for _ in range(H)])
 
ans = float('inf')

for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div=[0]
    for i, p in enumerate(pattern):
      if p==1:
        div= div+[i+1]
    div += [10]       
    
     # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
    
     # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    count=0
    for r in rows:
      if np.any(r>K):
        count=1
    if count==1:
      continue
    
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    
    while w<W:
      for r in range(len(rows)):
        counts[r] += rows[r][w]
        
      if any([c>K for c in counts]):
        counts=[0] * len(rows)
        w -=1
        tmp_ans += 1
      
      w+=1
    a=tmp_ans +len(div)-2
    ans=min(a,ans)
  
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
H, W ,K= map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
S = [list(map(int, list(input()))) for i in range(H)]
rui=[[0]*(W+1) for _ in range(H)]
tate=[False]*(H-1)

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

ans=H*W
for tcut in range(2**(H-1)):
    ncut=0
    for h in range(H-1): 
        if tcut >> h &1:
            tate[h]=True
            ncut+=1
        else:
            tate[h]=False
    start=0
    bed=[]
    for h in range(H-1):
        if tate[h]==True:
            goal=h+1
            part=[0]*(W+1)
            for i in range(start,goal):
                for j in range(1,W+1):
                    part[j]+=rui[i][j]
            bed.append(part)
            start=h+1
    goal=H
    part=[0]*(W+1)
    for i in range(start,goal):
        for j in range(1,W+1):
            part[j]+=rui[i][j]
    bed.append(part)
    ycut=0
    pos=True
    for j in range(1,W+1):
        for b in bed:
            if b[j]-b[j-1]>K:
                pos=False
                break
            elif b[j]-b[ycut]>K:
                ycut=j-1
                ncut+=1
        if pos==False:
            break
    if pos==False:
        continue
    ans=min(ans,ncut)    

                
print(ans)
            
#print(rui)

Submission status: Accepted

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

S = [input() for _ in range(H)]

ans = 10**10
for i in range(2**(H-1)):   # iはbit
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b

    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)

Submission status: Accepted

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

S = [input() for _ in range(H)]

ans = 10**10
for i in range(2**(H-1)):   # iはbit
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b

    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    oS=[list(map(int, list(input().rstrip()))) for _ in range(H)]

    ans=10**10
    for p in range(1<<(H-1)):
        S=[[oS[i][j] for j in range(W)] for i in range(H)]
        tmp=0
        flag=False
        for i in range(1,H):
            if p&1:
                for j in range(W):
                    S[i][j] += S[i-1][j]
                    if S[i][j]>K: flag=True
            else:
                tmp+=1
            p>>=1
        if flag: continue

        for j in range(W-1):
            for i in range(H):
                if S[i][j]+S[i][j+1]>K:
                    tmp+=1
                    break
            else:
                for i in range(H):
                    S[i][j+1] += S[i][j]

        ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

S = [input() for _ in range(H)]

def calc(L):
    M = len(L)
    cnt = [0] * M
    ret = 0

    for w in range(W):
        for i, (t, b) in enumerate(zip(L, L[1:])):
            for j in range(t, b):
                if S[j][w] == '1':
                    cnt[i] += 1
        if max(cnt) > K:
            cnt = [0] * M
            ret += 1
            for i, (t, b) in enumerate(zip(L, L[1:])):
                for j in range(t, b):
                    if S[j][w] == '1':
                        cnt[i] += 1
        if max(cnt) > K:
            return 10**18

    return ret

ans = 10**18
for mask in range(1 << (H - 1)):
    L = [0] + [d + 1 for d in range(H - 1) if (mask & (1 << d)) > 0] + [H]
    ans = min(ans, len(L) - 2 + calc(L))
print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input().strip("\n")))) for _ in range(H)]
    sumS = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            sumS[h+1][w+1] = sumS[h+1][w] + sumS[h][w+1] - sumS[h][w] + S[h][w]
    minK = 1000000000000
    for h in range(2 ** (H - 1)):
        count = 0
        border = [0]
        k = h
        for i in range(H-1):
            if k % 2 == 1: 
                border.append(i+1)
                count += 1
            k //= 2
        border.append(H)
        bN = len(border)
        left = 0
        ng = False
        for right in range(1, W + 1):
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    if right - 1 == left: ng = True
                    else: 
                        count += 1
                        left = right - 1
                    break
            if ng: break 
        else: minK = min(minK, count)
    print(minK)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

ans = H+W
for b in range(1<<(H-1)):
    gs = [[0]]
    for k in range(H-1):
        if b&(1<<k):
            gs.append([k+1])
        else:
            gs[-1].append(k+1)
    tmp = bin(b).count('1')
    ws = [0] * len(gs)
    for x in range(W):
        for i,g in enumerate(gs):
            for h in g:
                if S[h][x] == '1':
                    ws[i] += 1
        if any(w>K for w in ws):
            tmp += 1
            ws = [0] * len(gs)
            for i,g in enumerate(gs):
                for h in g:
                    if S[h][x] == '1':
                        ws[i] += 1
            if any(w>K for w in ws):
                tmp = H+W
                break
    ans = min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zero = 0
    key = 1
    for j in range(len(ss)):
        if ss[j] == "0":
            zero += 1
    now = [0 for i in range(zero+1)]

    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                key = 0
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
        
        keykey = 1
        for n in range(zero+1):
            if keykey:
                if now[n] + next[n] > k:
                    now = next
                    cnt += 1
                    keykey = 0
                else:
                    now[n] += next[n]
                    
    if key:ans = min(ans,cnt+zero)
print(ans)