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 = [0] * H

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


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    out = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                out = 1
                break
        else:
            after_tmp = [0] * (MAP[-1] + 1)
    if out == 1:
        return 1000000
    else:
        for w in range(W):
            for h in range(H):
                after_tmp[MAP[h]] += int(S[h][w])
            for af in after_tmp:
                if af > K:
                    cnt += 1
                    after_tmp = [0] * (MAP[-1] + 1)
                    for h2 in range(H):
                        after_tmp[MAP[h2]] += int(S[h2][w])
                    break
        return cnt + MAP[-1]

MIN = 1000000
for i in range(2**(H - 1)):
    MIN = min(MIN, check(i))

print(MIN)

Submission status: Accepted

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

for i in range(2**(H-1)):
    s = set()
    
    for j in range(H-1):
        if (i>>j)&1:
            s.add(j)
    
    cnt = [0]*(len(s)+1)
    ans_cand = len(s)
    
    for j in range(W):
        add = [0]*(len(s)+1)
        add_idx = 0
        
        for k in range(H):
            add[add_idx] += S[k][j]
        
            if k in s:
                add_idx += 1
        
        if max(add)>K:
            ans_cand = 10**18
            break
        
        for k in range(len(s)+1):
            if cnt[k]+add[k]>K:
                ans_cand += 1
                
                for l in range(len(s)+1):
                    cnt[l] = add[l]
                    
                break
        else:
            for k in range(len(s)+1):
                cnt[k] += add[k]
        
    ans = min(ans, ans_cand)
    
print(ans)

Submission status: Accepted

Solution code:
def nasu(x):
  L = [0]
  t = x
  cnt = 1
  while t != 0:
    if t & 1:
      L.append(cnt)
    t >>= 1
    cnt += 1
  Ans = len(L) - 1

  L.append(H)
  pr = 0
  for i in range(1, W + 1):
    f = True
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        pr = i - 1
        Ans += 1
        #print(pr, end = ",")
        break     
    else:
      continue
    for j in range(1, len(L)):
      k = D[L[j]][i] + D[L[j - 1]][pr] - D[L[j]][pr] - D[L[j - 1]][i]
      if k > K:
        return 10 ** 10
  #print(L, Ans)
  return Ans

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

N = 2 **(H - 1)

D = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
  D[i][1] = S[i - 1][0]

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

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

Ans = 10 ** 10
for i in range(N):
  Ans = min(Ans, nasu(i))

print(Ans)

Submission status: Accepted

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

    for pat in range(2 ** (H - 1)):
        Cnt_sum = [0] * H  # 区分における1の数
        ans_w = 0
        ans_h =  bin(pat).count('1')
        fail = False
        for j in range(W): #横のj番目を見る
            if fail:
                break
            s = 0 #区分
            Cnt = [0] * H
            for i in range(H):
                if (S[i][j] == '1'):
                    Cnt[s] += 1
                    Cnt_sum[s] += 1

                if Cnt[s] > K:
                    fail = True
                    break

                if (1 << i) & pat > 0: 
                    s += 1

            if any([v > K for v in Cnt_sum]):
                ans_w += 1
                Cnt_sum = Cnt[::]
        else:
            ans = min(ans, ans_h + ans_w)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

h,w,k=LI()

ans=0
s=[]
for i in range(h):
    s.append([int(i)for i in input()])

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

def check(ls):
    rt=[0]
    border=0
    wbg=0
    fl=False
    for wed in range(1,w+1):
        hbg=0
        for j in ls:
            hed=j
            cnt=ad[hed][wed]-ad[hed][wbg]-ad[hbg][wed]+ad[hbg][wbg]
            #show((hbg,wbg),(hed,wed),cnt)
            if cnt>k:
                fl=True
                border=wed-1
                #show(cnt)
                break
            hbg=j
        if fl:
            if rt[-1]==border:
                return []
            wbg=wed-1
            rt+=[border]
            fl=False
    return rt

ans=h+w
bg=0
ed=h
for i in range(1<<(h-1)):
    c=[]
    for j in range(h-1):
        if i>>j&1:
            c+=[j+1]
    c+=[h]
    rt=check(c)
    if rt==[]:
        continue
    wcut=len(rt)
    ans=min(ans,len(c)-1+wcut-1)
#    show(c,rt,(len(c),wcut),'ans=',len(c)-1+wcut-1)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]
 
total = sum(sum(c) for c in C)
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):
    ans = sum(X)
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:
        M.append([])
      M[-1].append(i+1)
    D = [0] * len(M)
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)
      if any(d > K for d in D):
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]
        if any(d > K for d in D):
          ans = answer + 1
          break
    answer = min(answer, ans)
   
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
def can_merge(K: int, prev_cnt: list, cur_cnt: list) -> bool:
    ret = True
    for i, _ in enumerate(cur_cnt):
        if prev_cnt[i] + cur_cnt[i] > K:
            ret = False
            break
    return ret

def merge(prev_cnt: list, cur_cnt: list):
    for i, _ in enumerate(cur_cnt):
        prev_cnt[i] += cur_cnt[i]

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

    min_split_num = 999+9
    for hbitv in range(2**(H-1)):
        split_num = bin(hbitv).count('1')
        region_num = split_num + 1
        prev_cnt = [0] * region_num

        # ->
        for w in range(W):
            impossible_hbitv = False
            cur_cnt = [0] * region_num

            # |
            # v
            ri = 0
            for h in range(H):
                if S[h][w] == '1':
                    cur_cnt[ri] += 1
                    if cur_cnt[ri] > K:
                        impossible_hbitv = True
                        break

                if (hbitv >> h) % 0b10 == 1:
                    ri += 1

            if impossible_hbitv:
                break

            if can_merge(K, prev_cnt, cur_cnt):
                merge(prev_cnt, cur_cnt)
            else:
                split_num += 1
                prev_cnt, cur_cnt = cur_cnt, prev_cnt
        
        if not impossible_hbitv:
            min_split_num = min(min_split_num, split_num)

    print(min_split_num)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
# pythonだと重いケースが通ったり通らなかったり
# h, w, k = 10, 1000, 2
# CHOCO = [list(map(int, "11010"*200)) for _ in range(h)]
INF = 10**5

# print(h, w, k)
# for row in CHOCO:
#     print("".join(map(str, row)))

# 水平方向の切れ込み全探索
it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    # print("".join(x))
    # 貪欲に垂直方向に切れ込みをいれる
    cnt = sum(map(int, x))

    # pieceごとに集約して、それぞれで貪欲に切る
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]
    # print(agg)

    # 集約した配列を貪欲に切っていく
    # 切れない場合に注意
    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue
    # print(ans, cnt, tmp)
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m,K=IA()
a=["" for i in range(0,n)]
for i in range(0,n):
    a[i]=input()

ans=n*m+1
for k in range(0,1<<(n-1)):
    res=0
    temp=[]
    for j in range(0,(n-1)):
        if (k&(1<<(j)))!=0:
            temp.append(j)
            res+=1
    le=len(temp) 
    if le==0:
        temp.append(n-1)
        
    if temp[le-1]!=n-1:
        temp.append(n-1)
        
    le=len(temp) 
  


    
    sum1=[0 for i in range(0,11)]
    flag=0
    for j in range(0,m):
        if flag==1:break
        last=0
        for t in range(0,le):
            for w in range(last,temp[t]+1):
                if a[w][j]=='1':
                    sum1[t]+=1
            last=temp[t]+1
            
            if sum1[t]>K:
                res+=1
                last=0
                sum1=[0 for i in range(0,11)]
                for t1 in range(0,le):
                    if flag==1:break
                    for w1 in range(last,temp[t1]+1):
                        if a[w1][j]=='1':
                            sum1[t1]+=1
                    
                    if sum1[t1]>K:
                        flag=1
                        res=n*m+1
                        break
                    last=temp[t1]+1
                break
        if flag==1:break
     
    ans=min(res,ans)
                
            
    
print(ans)

Submission status: Accepted

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

ans = 10 ** 5
for bit in range(2 ** (H - 1)):    
    group = [0] * H
    gnum = 0

    # Group each row
    for i in range(H - 1):
        if not bit >> i & 1:
            group[i + 1] = group[i]
        else:
            group[i + 1] = group[i] + 1
            gnum += 1

    gok = True
    add = 0  # Vertical split num
    nums = [0] * (gnum + 1)  # Number of '1' in previous blocks
    # For each column
    for j in range(W):
        ones = [0] * (gnum + 1)
        ok = True
        # For each row
        for i in range(H):
            ones[group[i]] += int(S[i][j])
            nums[group[i]] += int(S[i][j])
            if ones[group[i]] > K: gok = False;
            if nums[group[i]] > K: ok = False;

        if not ok:
            add += 1
            nums = ones[:]
            
    if gok:
        ans = min(ans, gnum + add)
                
    
print(ans)

Submission status: Accepted

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

ans = 10 ** 5
for bit in range(2 ** (H - 1)):    
    cur = [0] * H
    gnum = 0

    # Group each row
    for i in range(H - 1):
        if not (bit & (1 << i)):
            cur[i + 1] = cur[i]
        else:
            cur[i + 1] = cur[i] + 1
            gnum += 1

    gok = True
    add = 0
    nums = [0] * (gnum + 1)
    # For each column
    for j in range(W):
        ones = [0] * (gnum + 1)
        ok = True
        # For each row
        for i in range(H):
            ones[cur[i]] += int(S[i][j])
            nums[cur[i]] += int(S[i][j])
            if ones[cur[i]] > K: gok = False;
            if nums[cur[i]] > K: ok = False;
                
        if not ok:
            add += 1
            nums = ones[:]
            
    if gok:
        ans = min(ans, gnum + add)
                
    
print(ans)

Submission status: Accepted

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

res = float('inf')
for div in range(2**(h-1)):
    cut = []
    for i in range(h-1):
        if ((div >> i) & 1):
            cut.append(i+1)
    fr = 0
    part = []
    for i in range(len(cut)):
        to = cut[i]
        part.append(S[fr:to])
        fr = to
    else:
        part.append(S[fr:])
    comp_arr = []

    for p in part:
        tmp = [0]*(w)
        for p_ in p:
            for idx in range(len(p_)):
                if p_[idx]=='1':
                    tmp[idx] += 1
        comp_arr.append(tmp)
    
    if not all([all([i <= k for i in b]) for b in comp_arr]):
        continue
    
    cnt = len(cut)
    tank = [0]*len(comp_arr)
    for m in range(w):
        for n in range(len(comp_arr)):
            tank[n] += comp_arr[n][m]
        if any([c>k for c in tank]):
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]
    res = min(res, cnt)
print(res)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(h)]
ans = 10**9+7
for i in range(1 << (h-1)):
    group = [[0]*w]
    g_id = 0
    group[g_id] = [s+b for s, b in zip(S[0], group[0])]
    for j in range(1, h):
        if (i>>(j-1))&1:
            group.append([0]*w)
            g_id += 1
        group[g_id] = [s+b for s, b in zip(S[j], group[g_id])]
    if not all([all([i <= k for i in b]) for b in group]):
        continue
    cnt = len(group) - 1
    g_cnt = [0] * len(group)
    
    for jj in range(w):
        for g_id in range(len(group)):
            g_cnt[g_id] += group[g_id][jj]
        if any([c > k for c in g_cnt]):
            cnt  += 1
            for g_id in range(len(group)):
                g_cnt[g_id] = group[g_id][jj]
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

    spl_l=[]
    for aaa in range(h):
        spl_l.append(sum(tmp[:aaa]))
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = spl_l[j]
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

print(ans)

Submission status: Accepted

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

    res = 1 << 29
    for bit in range(1 << (H-1)):
        gok = True
        N = 0
        ord_lst = [0] * H
        for i in range(H-1):
            if not(bit & 1<<i):
                ord_lst[i+1] = ord_lst[i]
            else:
                ord_lst[i+1] = ord_lst[i] + 1
                N += 1
        
        add = 0
        nums = [0] * (N+1)
        for w in range(W):
            one = [0] * (N+1)
            ok = True
            for h in range(H):
                one[ord_lst[h]] += int(fi[h][w])
                nums[ord_lst[h]] += int(fi[h][w])
                if one[ord_lst[h]] > K:
                    gok = False
                if nums[ord_lst[h]] > K:
                    ok = False
            
            if not ok:
                add += 1
                nums = one[:]
        if gok:
            res = min(res, N + add)
    print(res)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

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

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Accepted

Solution code:
def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

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

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

def solve():
    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)):
        p = deque()
        for j in range(H - 1):
            if (i >> j) & 1:
                p.append(j + 1)
        num = len(p)
        if len(p) == 0:
            check = 0
            for j in range(W):
                temp_sum = sum([S[l][j] for l in range(H)])
                if temp_sum > K:
                    num = INF
                if check + temp_sum > K:
                    check = temp_sum
                    num += 1
                else:
                    check += temp_sum
        else:
            p.appendleft(0)
            p.append(H)
            check = [0] * (len(p) - 1)
            for j in range(W):
                for l in range(len(p) - 1):
                    if p[l + 1] - p[l] == 1:
                        check[l] += S[l][j]
                    else:
                        temp_sum = sum([S[t][j] for t in range(p[l], p[l + 1])])
                        if temp_sum > K:
                            num = INF
                            break
                        check[l] += temp_sum
                for l in check:
                    if l > K:
                        num += 1
                        for k in range(len(p) - 1):
                            if p[k + 1] - p[k] == 1:
                                check[k] = S[k][j]
                            else:
                                temp_sum = sum([S[t][j] for t in range(p[k], p[k + 1])])
                                if temp_sum > K:
                                    num = INF
                                check[k] = temp_sum
                        break
        if num < ans:
            ans = num
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

"""
bit全探索の考え方

for div in range(2**3):
    print(div)
    # divの値を2進数で考えると、
    # 0000
    # 0001
    # 0010
    # 0011
    # 0100
    # 0101
    # ...
    # となるので、全探索を考えやすい

"""


def solve():
    """
    最初に横に切る方法を全探索し、
    次に、ギリギリのラインを縦に切っていく
    O(2**H W)

    Note1:
        1 << K  =>  2**k

    Note2:
        div>>i&1
        => divのi桁目が1であるかどうか
    """
    H, W, K = list(map(int, input().split()))
    S = ["" for _ in range(H)]
    for i in range(H):
        s = input()
        S[i] += s
    ans = float("inf")

    # 横に切るのを全部試す
    # divのbitが1のところで切る
    # gはグループ数
    for div in range(0, 1<<(H-1)):  # 2**(H-1)を全探索するとき、bitで考えたほうがラク
        g = 0
        ids = [0 for _ in range(H)]
        for i in range(H):
            ids[i] = g
            if div>>i&1:
                g += 1
        g += 1

        c = [[0 for _ in range(1005)] for __ in range(10)]

        for i in range(H):
            for j in range(W):
                c[ids[i]][j] += int(S[i][j])

        num = g-1  # g-1回、横に切る
        now = [0 for _ in range(g)]  # 今、各グループに何個のホワイトチョコレートがあるか
        def add(j, now, c):
            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, now, c):
                num += 1
                now = [0 for _ in range(g)]
                if not add(j, now, c):
                    num = float("inf")
                    break
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = (h - 1) * (w - 1)  #INF
for bitseed in range(2 ** (h - 1)):
    i2cell = [0]
    accum_temp = 0
    for _ in range(h - 1):
        accum_temp += bitseed % 2
        i2cell.append(accum_temp)
        bitseed //= 2
    #accum_temp == horizontal cut num
    cell2whitenum = [0] * (accum_temp + 1)
    v_cut_num = 0
    for j in range(w):
        for i in range(h):
            cell2whitenum[i2cell[i]] += s[i][j]
        if max(cell2whitenum) > k:
            v_cut_num += 1
            cell2whitenum = [0] * (accum_temp + 1)
            for i in range(h):
                cell2whitenum[i2cell[i]] += s[i][j]
            if max(cell2whitenum) > k:
                v_cut_num = (h - 1) * (w - 1)  #INF
    if accum_temp + v_cut_num < ans:
        ans = accum_temp + v_cut_num
print(ans)

Submission status: Accepted

Solution code:
import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subs = divide(s,i)

        subcusum = []

        rowsum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        for sub_ in subs:
            rowsum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))


        cutnum = 0

        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    if rowsum[l][j]>k:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
s = []
INF = (H - 1) + (W - 1)
ans = INF

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

for _ in range(H):
    s.append(list(input()))

for div in range(1 << (H - 1)):
    g = 0
    id = [0] * H
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1
    g += 1
    
    now = [0] * g
    num = g - 1
    c = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            c[id[i]][j] += int(s[i][j])

    for j in range(W):
        if not add(j):
            num += 1
            now = [0] * g

            if not add(j):
                num = INF
                break

    ans = min(ans, num)
    
print(ans)