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())
S = [input() for _ in range(h)]
ans = float('inf')
for bit in range(1<<(h-1)):
    segment = [0]*h
    seg = 0
    for i in range(h-1):
        if bit & (1<<i):
            seg += 1
        segment[i+1] = seg
    n = max(segment) + 1

    count = n-1
    k_cnt = [0]*n
    for j in range(w):
        tmp = [0]*n
        for i in range(h):
            k_cnt[segment[i]] += int(S[i][j])
            tmp[segment[i]] += int(S[i][j])
            if k_cnt[segment[i]] > k:
                count += 1
                for i in range(n):
                    k_cnt[i] = tmp[i]
    ans = min(ans,count)
print(ans)

Submission status: Accepted

Solution code:
"""

制約の小ささから見て全探索

"""

from itertools import product, accumulate
from bisect import *
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = []
T = []
for i in range(H):
    S.append(list(map(int, input().strip())))
    T.append(list(accumulate([0] + S[-1])))

cnt_list = []
for a in product((0,1),repeat=H):
    past_a = a[0]
    T2 = [[0]*(W+1)]
    for i in range(H):
        if a[i] == past_a:
            for j, t in enumerate(T[i]):
                T2[-1][j] += t
        else:
            T2.append(T[i].copy())
        past_a = a[i]
    cnt = len(T2) - 1
    l = 0
    flg = False
    while True:
        temp = []
        for s in T2:
            temp.append(bisect_right(s[l+1:], K + s[l]) + l)
        if min(temp) == 0:
            flg = True
            break
        else:
            l = min(temp)
        if l >= W:
            break
        else:
            cnt += 1
    if not flg:
        cnt_list.append(cnt)

print(min(cnt_list))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    choco = [SI() for _ in range(H)]
    ans = 100000
    for case in range(2**(H-1)):
        groups = [[0]]
        for i in range(H-1):
            if (case >> i) & 1:
                groups[-1].append(i+1)
            else:
                groups.append([i+1])
        white = [0] * len(groups)

        is_badcase = False
        cut = len(groups) - 1
        for w in range(W):
            diff = [0] * len(groups)
            for gi, group in enumerate(groups):
                for h in group:
                    if choco[h][w] == "1":
                        white[gi] += 1
                        diff[gi] += 1

            if max(white) <= K:
                is_cont = True
                continue

            if max(diff) > K:
                is_badcase = True
                break

            cut += 1
            white = diff[:]
            continue

        if not is_badcase:
            ans = min(ans, cut)

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

H, W, K = map(int, input().split())
X = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
ans = MOD

for bit in range(2 ** (H - 1)):
    n = bin(bit).count("1")
    ctr = [0] * (n + 1)  # Accumulation
    res = 0
    for j in range(W):
        k = 0
        tmp = [0] * (n + 1)  # One column
        for i in range(H):
            tmp[k] += int(X[i][j])
            if bit >> i & 1:
                k += 1

        # Check counts
        if any(v > K for v in tmp):
            res = MOD
            break
        elif any(u + v > K for u, v in zip(ctr, tmp)):
            # Split
            res += 1
            ctr = tmp[:]
        else:
            # Accumulate
            for i in range(n + 1):
                ctr[i] += tmp[i]

    ans = min(ans, res + n)

print(ans)

Submission status: Accepted

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

a = []
for i in range(h):
  s = input()
  a.append(s)

s = [[0 for i in range(w)] for i in range(h)]

ans = h+w
for grid in itertools.product([0,1], repeat=h-1):
  ary = [[0]]
  for i in range(h-1):
    if grid[i] == 1:
      ary.append([i+1])
    else:
      ary[-1].append(i+1)
  # print (grid, ary)
  wk = 0
  for i in grid:
    if i == 1:
      wk += 1
  # print (wk)
  cnt = [0] * len(ary)
  for j in range(w):
    for ii, g in enumerate(ary):
      for b in g:
        if a[b][j] == '1':
          cnt[ii] += 1
    if any(W > k for W in cnt):
      wk += 1
      cnt = [0] * len(ary)
      for ii, g in enumerate(ary):
        for jj in g:
          if a[jj][j] == '1':
            cnt[ii] += 1
      if any(W > k for W in cnt):
        wk = h+w
        break
  ans = min(ans, wk)
print (ans)

Submission status: Accepted

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

ans = 10**18
for bit in range(1<<(h - 1)):
    segment = [0] * h
    seg_label = 0
    for i in range(h - 1):
        if bit & (1<<i):
            seg_label += 1
        segment[i + 1] = seg_label
    n = max(segment) + 1

    count = n - 1
    k_count = [0] * n
    for j in range(w):
        tmp_count = [0] * n
        for i in range(h):
            k_count[segment[i]] += int(S[i][j])
            tmp_count[segment[i]] += int(S[i][j])
            if k_count[segment[i]] > k:
                count += 1
                for seg in range(n):
                    k_count[seg] = tmp_count[seg]

    ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)

for j in range(2**(H-1)):
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][hlist[0]]
      if counter[0] > K:
        anskouho += 1
        break
      for l in range(1, len(hlist)):
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
        if counter[l] > K:
          anskouho += 1
          break
      else:
        now += 1
        continue
      break
    if anskouho > ans:
      break
  else:
    ans = anskouho
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)
#print(binhh)
#h = 2**(H-1)
for j in range(2**(H-1)):
  #h -= 1
  #binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      counter[0] += hsummation[now][int(hlist[0])]
      for l in range(1, len(hlist)):
        #if l == 0:
          #counter[l] += hsummation[now][int(hlist[l])]
          #continue
        #else:
        counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))

ans = float('inf')
anskouho = 0
h = -1
binhh = []
for j in range(2**(H-1)):
  h += 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  c = 0
  for k in range(len(binh)):
    if binh[k] == '1':
      c += 1
  binhh.append([binh, c])
binhh.sort(key = lambda x:x[1] , reverse= True)
#print(binhh)
#h = 2**(H-1)
for j in range(2**(H-1)):
  #h -= 1
  #binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binhh[j][0][k] == '1':
      hlist.append(k)
  hlist.append(-1)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      #print(counter)
#print(anskouho)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
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)]

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def bit_pattern(bits, length):
    return [(bits >> i) & 1 for i in range(length)]

def main():
    H, W, K = LI()
    s = SR(H)

    ans = float("inf")

    for i in range(1 << (H - 1)):
        pattern = bit_pattern(i, H-1)
        divided = []
        tmp = [s[0]]
        tmp_ans = 0

        for i, bit in enumerate(pattern):
            if bit:
                tmp_ans += 1
                divided.append(tmp)
                tmp = [s[i+1]]
            else:
                tmp.append(s[i+1])
        divided.append(tmp)

        whites = []

        for block in divided:
            white = [0] * W
            for row in block:
                for i, panel in enumerate(row):
                    if panel == "1":
                        white[i] += 1
            whites.append(white)

        curs = [0] * len(whites)
        outer = False
        for w in range(W):
            for i, white in enumerate(whites):
                if white[w] > K:
                    outer = True
                    break
                elif white[w] + curs[i] > K:
                    curs = [white[w] for white in whites]
                    tmp_ans += 1
                    break
                else:
                    curs[i] += white[w]
            else:
                continue
            if outer:
                break
        else:
            ans = min(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools


def main():
    H, W, K = list(map(int, input().split(' ')))
    S = [input() for _ in range(H)]
    ans = (H - 1) * (W - 1)
    for h_divs in itertools.product([0, 1], repeat=H-1):
        # 例：h_patterns = [0, 0, 1, 2, 2] -> チョコを1～2、2～3番目の行で分割
        h_patterns = [0] * H
        for h in range(1, H):
            h_patterns[h] = h_patterns[h - 1] + h_divs[h - 1]
        # 横方向には h_patterns[-1] 回割る
        div_cnt = h_patterns[-1]
        # 縦方向にはgreedyに割っていく
        white_cnt = [0] * (div_cnt + 1)
        valid_div = True  # 各列において、単体でホワイトチョコがK個より多いブロックがあったらFalse
        for w in range(W):
            new_white_cnt = [0] * (div_cnt + 1)
            for h in range(H):
                if S[h][w] == '1':
                    new_white_cnt[h_patterns[h]] += 1
            if max(new_white_cnt) > K:
                valid_div = False
                break
            should_div = False
            for r in range(len(white_cnt)):
                if white_cnt[r] + new_white_cnt[r] > K:
                    should_div = True
                    break
            if should_div:
                div_cnt += 1
                for r in range(len(white_cnt)):
                    white_cnt[r] = new_white_cnt[r]
            else:
                for r in range(len(white_cnt)):
                    white_cnt[r] += new_white_cnt[r]
        if valid_div:
            ans = min(ans, div_cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
H,W,K = map(int,input().split())
S = [input().strip() for _ in range(H)]
C = {i:[0 for _ in range(W+1)] for i in range(H)}
for i in range(H):
    for j in range(1,W+1):
        C[i][j] = C[i][j-1]+int(S[i][j-1])
cmin = (H-1)*(W-1)
for x in product((0,1),repeat=H-1):
    A = []
    cur = 0
    for i in range(H-1):
        if x[i]==1:
            A.append(list(range(cur,i+1)))
            cur = i+1
    A.append(list(range(cur,H)))
#     print("A={}".format(A))
    cur = 0
    cnt = 0
    ind = 0
    for j in range(1,W+1):
        flag = 0
        for a in A:
            tot = 0
            for i in a:
                tot += C[i][j]-C[i][cur]
            if tot<=K:continue
            else:
                flag = 1
                break
        if flag==1:
            cnt += 1
            if cur==j-1:
                ind = 1
                break
            cur = j-1
    if ind==0:
        cmin = min(cmin,cnt+sum(x))
#     print("cmin={},x={}".format(cmin,x))
print(cmin)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
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()))

h,w,k = inpl()
s = [list(input()) for _ in range(h)]
res = INF
for yoko in itertools.product([0,1], repeat=(h-1)):
    # 0:uncut 1:cut
    ln = sum(yoko)
    gr = [[] for _ in range(ln+1)] 
    gr[0].append(0)
    ind = 0
    for i in range(1,h):
        if yoko[i-1]: ind += 1
        gr[ind].append(i)
    possible = True
    for x in range(w):
        for ind in range(ln+1):
            cnt = 0
            for y in gr[ind]:
                if s[y][x] == '1':
                    cnt += 1
            if cnt > k:
                possible = False
                break
        if not possible:
            break
    else:
        cutcnt = 0
        now = [0] * (ln+1)
        for x in range(w):
            for ind in range(ln+1):
                for y in gr[ind]:
                    if s[y][x] == '1':
                        now[ind] += 1
            if max(now) > k:
                now = [0] * (ln+1)
                cutcnt += 1
                for ind in range(ln+1):
                    for y in gr[ind]:
                        if s[y][x] == '1':
                            now[ind] += 1
        res = min(res, cutcnt + ln)
print(res)

Submission status: Accepted

Solution code:
import collections

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

ans = float("inf")


for i in range(2 ** (H - 1)):
    bundan = {}
    bundan[0] = 0
    prev = 0
    tmp = 0
    for j in range(H - 1):
        if i >> j & 1 == 1:
            prev += 1
            bundan[j + 1] = prev
            tmp += 1
        else:
            bundan[j + 1] = prev

    c = collections.Counter()
    for kk in range(W):
        f = False
        for k in range(H):
            if f:
                break
            if S[k][kk] == '1':
                c[bundan[k]] += 1
                if c[bundan[k]] > K:
                    tmp += 1
                    f = True
                    c = collections.Counter()
                    for kkk in range(H):
                        if S[kkk][kk] == '1':
                            c[bundan[kkk]] += 1
                    break
    for k in c.keys():
        if c[k] > K:
            tmp = float("inf")
            break


    ans = min(ans, tmp)


print(ans)

Submission status: Accepted

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

ans = H+W+9999
for b in range(1<<(H-1)):
    mp = [0]
    k = 0
    for i in range(H-1):
        if b&(1<<i):
            k += 1
        mp.append(k)
    tmp = bin(b).count('1')
    ws = [0] * H
    muri = False
    for col in zip(*S):
        for i,c in enumerate(col):
            if c == '1':
                ws[mp[i]] += 1
        if any(w > K for w in ws):
            ws = [0] * len(mp)
            for i,c in enumerate(col):
                if c == '1':
                    ws[mp[i]] += 1
            if any(w > K for w in ws):
                muri = True
                break
            tmp += 1
        if muri:
            break
    if not muri:
        ans = min(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


def cut(pt, grid, k, h, w):
    pat = []
    for i in range(h-1):
        if pt % 2 == 1:
            pat.append("1")
        else:
            pat.append("0")
        pt //= 2

    # print("pat", pat)
    slice = Counter(pat)["1"]
    pat = pat + ["0"]
    white = [0] * (slice + 1)
    ret = 0
    for i in range(w):
        tw = [0] * (slice + 1)
        dan = 0
        for j in range(h):
            if grid[j][i] == "1":
                tw[dan] += 1
            if pat[j] == "1":
                dan += 1

        if max(tw) > k:
            return INF
        reset = False
        for w1, w2 in zip(white, tw):
            if w1 + w2 > k:
                ret += 1
                reset = True
                break
        if reset:
            white = tw
        else:
            for up in range(slice + 1):
                white[up] += tw[up]

    return ret + slice

def solve():
    h, w, k = getList()
    grid = []
    for i in range(h):
        grid.append(getS())

    ans = INF
    for i in range(2 ** (h-1)):
        tmp = cut(i, grid, k, h, w)
        # print(tmp)
        ans = min(ans, tmp)
    print(ans)


def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for _ in range(H)]
ans=INF
for i in range(2**(H-1)):
    cnt=1+bin(i).count('1')
    tmp=cnt-1
    div=[0]*H
    for j in range(H-1):
        if (i>>j)&1:
            div[j+1]=div[j]+1
        else:
            div[j+1]=div[j]
    wc=[0]*cnt
    for x in range(W):
        tmp_wc=[0]*cnt
        f=False
        for y in range(H):
            if S[y][x]==1:
                tmp_wc[div[y]]+=1
                wc[div[y]]+=1
                if wc[div[y]]>K:
                    f=True
                if tmp_wc[div[y]]>K:
                    break
        else:
            if f:
                tmp+=1
                wc=tmp_wc
                tmp_wc=[0]*cnt
                f=False
            continue
        break
    else:
        ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
H, W, K = map(int, input().split())
S = [list(map(int, list(input())[: -1])) for _ in range(H)]
res = H + W - 2
for t in range(H):
  for c in combi([x for x in range(1, H)], t):
    s = set(c)
    table = [0] * (t + 1)
    rres = t + 0
    for x in range(W):
      i = 0
      y = 0
      while y < H:
        if y in s: i += 1
        table[i] += S[y][x]
        y += 1
        if table[i] > K: break
      else: continue
      rres += 1
      table = [0] * (t + 1)
      i = 0
      y = 0
      while y < H:
        if y in s: i += 1
        table[i] += S[y][x]
        y += 1
        if table[i] > K: break
      else: continue
      rres = H + W - 2
      break

    #print(c, rres, table)
    res = min(res, rres)
print(res)

Submission status: Accepted

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

h, w, kk = map(int, input().split())
ss = [[0 for _ in range(h)] for _ in range(w)]
for i in range(h):
    for j, c in enumerate(list(input().strip())):
        if c == '1':
            ss[j][i] = 1

ans = 100000
for i in range(2 ** (h - 1)):
    end = []
    for j in range(h - 1):
        if i & 2 ** j:
            end.append(j + 1)
    end.append(h)
    start = [0]
    for j in end:
        start.append(j)
    start.pop()
    sums = [0] * len(start)

    tans = len(start) - 1
    imp = False
    for j in range(w):
        reset = False
        for k, (s, e) in enumerate(zip(start, end)):
            sums[k] += sum(ss[j][s:e])
            if sums[k] > kk:
                reset = True
                break
        if reset:
            tans += 1
            for k, (s, e) in enumerate(zip(start, end)):
                sums[k] = sum(ss[j][s:e])
                if sums[k] > kk:
                    imp = True
        if imp:
            break
    if not imp:
        ans = min(ans, tans)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
#sum(a,b -> x,y) (1-indexed)
#cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

min_split = 10**10

for i in range(2**(h-1)):
    li = []

    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = [0]*w
    total = []

    over = False

    for l in range(h):
        for m in range(w):
            lin[m] += s[l][m]
            if lin[m] > k:
                over = True
        if l in li:
            total.append(lin)
            lin = [0]*w

    if over:
        continue

    now = 0
    t = len(total)
    count = t-1

    for n in range(t):
        total[n] = [0]+list(accumulate(total[n]))
    for o in range(1,w+1):
        for p in range(t):
            if total[p][o]-total[p][now] > k:
                now = o-1
                count += 1
                break

    min_split = min(min_split,count)

print(min_split)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
INF = 1 << 60


def main():
    H, W, K = map(int, readline().split())
    S = read().split()

    ans = INF

    for bit in range(1 << (H - 1)):
        idx = [0] * H
        for i in range(H - 1):
            if bit & (1 << i):
                idx[i + 1] = idx[i] + 1
            else:
                idx[i + 1] = idx[i]

        res = idx[-1]
        n = idx[-1] + 1
        A = [0] * n

        for j in range(W):
            B = [0] * n
            ok = True
            for i in range(H):
                if S[i][j] == '1':
                    B[idx[i]] += 1
                    if B[idx[i]] > K:
                        ok = False
                        break

            if not ok:
                res = INF
                break

            divided = False
            for k in range(n):
                A[k] += B[k]
                if A[k] > K:
                    divided = True
                    break

            if not ok:
                res = INF
                break
            if divided:
                A = B
                res += 1

        if ans > res:
            ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    ans = INF

    for r in range(H):
        for comb in combinations(range(1, H), r):
            sep = [0]
            sep.extend(list(comb))
            sep.append(H)

            res = r
            A = [0] * (r + 1)

            for j in range(W):
                B = [0] * (r + 1)
                for k in range(r + 1):
                    for i in range(sep[k], sep[k + 1]):
                        if S[i][j] == '1':
                            B[k] += 1

                ok = True
                divided = False
                for k in range(r + 1):
                    if B[k] > K:
                        ok = False
                        break
                    if A[k] + B[k] > K:
                        divided = True
                        break
                    else:
                        A[k] += B[k]

                if not ok:
                    res = INF
                    break
                if divided:
                    A = B
                    res += 1

            if ans > res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
H, W, K = map(int, input().split())
S = [list(map(lambda x: int(x=='1'), input())) for _ in range(H)]


def cal_min_vert_div(hs):
    cnt = 0
    n_h_div = len(hs)
    n_white = [0]*n_h_div
    for i in range(W):
        for j in range(n_h_div):
            n_white[j] += hs[j][i]
            if n_white[j] > K:
                n_white = [hs[k][i] for k in range(n_h_div)]
                cnt += 1
                if max(n_white)>K:
                    return math.inf
                break
    return cnt

ans = math.inf

for mask in range(2**(H-1)):
    hs = []
    tmp = S[0]
    for i in range(H-1):
        if mask>>i & 1:
            hs.append(tmp)
            tmp = S[i+1]
        else:
            tmp = [tmp[w]+S[i+1][w] for w in range(W)]
    hs.append(tmp)
    tmp = cal_min_vert_div(hs)+sum(map(int, bin(mask)[2:]))
    ans = min(ans, tmp)
print(ans)