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: Wrong Answer

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)
    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: Wrong Answer

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Submission status: Wrong Answer

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

ans = H + W - 2

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Submission status: Wrong Answer

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
    bit = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            new = s_arr[start:j+1].sum(axis=0, keepdims=True)
            if np.any(new>k):
                bit = 1
                break
            kouryo = np.concatenate((kouryo, new), axis=0)
            start=j+1
    if bit == 1: continue
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
S = np.array([list(map(int, list(input()))) for _ in range(H)])
ans = H*W
for i in range(1 << H-1):
  cnt = 0
  A = np.zeros((H, W))
  A[0,] = np.cumsum(S[0, ])
  for y in range(1, H):
    if (i >> y-1) % 2 == 1:
      A[y,] = np.cumsum(S[y,])
      cnt += 1
    else:
      A[y,] = np.cumsum(S[y,]) + A[y-1,]
  for x in range(1, W):
    if K+1 in A[:, x]:
      cnt += 1
      for x2 in range(x,W):
        A[:, x2] -= A[:, x-1]
  if ans > cnt:
    ans = cnt
print (ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
S = np.array([list(map(int, list(input()))) for _ in range(H)])
ans = H*W
B = np.zeros((H,W))
for i in range(H):
  for j in range(W):
    B[i][j] = np.sum(S[:i+1, :j+1])
for i in range(1 << H-1):
  cnt = 0
  A = np.zeros((H, W))
  A[0,] = np.cumsum(S[0, ])
  for y in range(1, H):
    if (i >> y-1) % 2 == 1:
      A[y,] = np.cumsum(S[y,])
      cnt += 1
    else:
      A[y,] =  np.cumsum(S[y,]) + A[y-1,]
  if K in A[:, 0]: continue
  for x in range(1, W):
    if K+1 in A[:, x]:
      cnt += 1
      for x2 in range(x,W):
        A[:, x2] -= A[:, x-1]
  if ans > cnt:
    ans = cnt
print (ans)

Submission status: Wrong Answer

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) 
    #print(k)  
    #print(temp)


    
    sum1=[0 for i in range(0,11)]
    flag=0
    for j in range(0,m):
        last=0
        for t in range(0,le):
            for w in range(last,temp[t]+1):
                ## print(str(w)+" "+str(j))
                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):
                    for w1 in range(last,temp[t1]+1):
                        if a[w1][j]=='1':
                            sum1[t1]+=1
                    if sum1[t]>K:
                        flag=1
                        res=n*m+1
                        break
                    last=temp[t]+1
                    
                break
        if flag==1:break
       
    ans=min(res,ans)
                
            
    
print(ans)

Submission status: Wrong Answer

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

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
#            spl = sum(tmp[:j])
            spl = 0
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            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("  ",cur_ans,ok)
print(ans)

Submission status: Wrong Answer

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)
    
    
    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]) and m!=-w-1:
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]
    res = min(res, cnt)
print(res)

Submission status: Wrong Answer

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) 
    #print(k)  
    #print(temp)


    
    sum1=[0 for i in range(0,11)]
    flag=0
    for j in range(0,m):
        last=0
        for t in range(0,le):
            for w in range(last,temp[t]+1):
                ## print(str(w)+" "+str(j))
                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):
                    for w1 in range(last,temp[t1]+1):
                        if a[w1][j]=='1':
                            sum1[t1]+=1
                    if sum1[t]>K:
                        flag=1
                        res=n*m+1
                        break
                    last=temp[t]+1
                    
                break
        if flag==1:break
       
    ans=min(res,ans)
                
            
    
print(ans)

Submission status: Wrong Answer

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)
    
    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]) and m!=w-1:
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]
    res = min(res, cnt)
print(res)

Submission status: Wrong Answer

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

res = 10**9+2
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)
    
    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: Wrong Answer

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

res = 10**7
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)
    
    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: Wrong Answer

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

res = 10**6
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)
    
    cnt = len(cut)
    tank = [0]*len(comp_arr)    
    for m in range(w):
        for n in range(len(comp_arr)-1):
            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: Wrong Answer

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

res = 10**6
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)
    
    cnt = len(cut)
    tank = [0]*len(comp_arr)    
    for m in range(w-1):
        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: Wrong Answer

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

res = 10**6
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)
    

    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: Wrong Answer

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

s = [str(input()) for i in range(h)]

#Greedy algorithm
num = 0
count = 0
i = 0

while i < w:
    print(i)
    for j in range(h):
        if s[j][i] == "1":
            count += 1
        if count > k:
            break
    if count > k:
        count = 0
        num += 1
        continue
    i += 1

print(num)

Submission status: Wrong Answer

Solution code:

import numpy as np

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

res = float('inf')
# bit全探索
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:
        p_ = np.array(p).astype(np.int)
        comp_arr.append(p_.sum(axis=0))
    comp_arr_T = np.array(comp_arr).T
    
    tank = 0
    cnt = 0
    for c in comp_arr_T:
        s = c.sum()
        if tank + s > k:
            tank = s
            cnt += 1
        else:
            tank += s
    res = min(res, cnt)
print(res)

Submission status: Wrong Answer

Solution code:





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

# 縦1マスなら、たての分割は行わず横だけ見て行く
if H == 1:
    S = input()
    cnt = 0
    ans = 0

    for i in range(W):
        if S[i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1


    
    print(ans)
    exit()

# 横1マスなら、横の分割は行わずに縦だけ見て行く
elif W == 1:
    S = [input() for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(H):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()


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

ans = H + W
for bit in range(1 << (H-1)):
    
    cannot_cut_h = False
    # 決め打った横方向の割り方で規定の数を超える場合はスキップしたいので、前回どこで縦方向の切れ目を入れたのかを保存
    ex_cut_w = -1

    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")
    # 横方向に割った時の、同じ区間かつ現在の列より左のホワイトチョコの数を管理するlist
    cnt_white_prev = [0] * nums

    for w in range(W):
        # 横方向に割った時の、現在の列のホワイトチョコの数を管理するlist
        cnt_white_curr = [0] * nums
        idx = 0

        # ある列にあるホワイトの数を数える
        for h in range(H):
            if S[h][w] == "1":
                cnt_white_curr[idx] += 1
            if h < H-1 and bit & (1 << h):
                idx += 1

        # K個を上回るブロックがあったか
        is_over_K = False
        for i in range(nums):
            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                break
        
        # K個を超えるブロックがあった場合、
        if is_over_K:
            # 前回の縦の区切りが一つ手前で、最小幅に切ってもKを超える場合は、その横の区切りはできない
            if w - ex_cut_w <= 1:
                cannot_cut_h = True
                break
            else:
                cnt_cut += 1
                ex_cut_w = w
                for i in range(nums):
                    cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]

    if cannot_cut_h:
        
        continue
    
    
    ans = min(ans, cnt_cut)

    

        

print(ans)

Submission status: Wrong Answer

Solution code:





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

# 縦1マスなら、たての分割は行わず横だけ見て行く
if H == 1:
    S = input()
    cnt = 0
    ans = 0

    for i in range(W):
        if S[i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1


    
    print(ans)
    exit()

# 横1マスなら、横の分割は行わずに縦だけ見て行く
elif W == 1:
    S = [input() for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(H):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()


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

ans = (H-1) + (W - 1)
for bit in range(1 << (H-1)):
    
    cannot_cut_h = False
    # 決め打った横方向の割り方で規定の数を超える場合はスキップしたいので、前回どこで縦方向の切れ目を入れたのかを保存
    ex_cut_w = -1

    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")
    # 横方向に割った時の、同じ区間かつ現在の列より左のホワイトチョコの数を管理するlist
    cnt_white_prev = [0] * nums

    for w in range(W):
        # 横方向に割った時の、現在の列のホワイトチョコの数を管理するlist
        cnt_white_curr = [0] * nums
        idx = 0

        # ある列にあるホワイトの数を数える
        for h in range(H):
            if S[h][w] == "1":
                cnt_white_curr[idx] += 1
            if h < H-1 and bit & (1 << h):
                idx += 1

        # K個を上回るブロックがあったか
        is_over_K = False
        for i in range(nums):
            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                break
        
        # K個を超えるブロックがあった場合、
        if is_over_K:
            # 前回の縦の区切りが一つ手前で、最小幅に切ってもKを超える場合は、その横の区切りはできない
            if w - ex_cut_w <= 1:
                cannot_cut_h = True
                break
            else:
                cnt_cut += 1
                ex_cut_w = w
                for i in range(nums):
                    cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]

    if cannot_cut_h:
        
        continue
    
    
    ans = min(ans, cnt_cut)

    

        

print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = (h - 1) * (w - 1)
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 accum_temp + v_cut_num < ans:
        ans = accum_temp + v_cut_num
print(ans)

Submission status: Wrong Answer

Solution code:



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

# 縦1マスなら、たての分割は行わず横だけ見て行く
if H == 1:
    S = input()
    cnt = 0
    ans = 0
    for i in range(W):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()

# 横1マスなら、横の分割は行わずに縦だけ見て行く
elif W == 1:
    S = [input() for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(H):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()


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

ans = (H-1) * (W - 1)
for bit in range(1 << (H-1)):
    
    cannot_cut_h = False
    # 決め打った横方向の割り方で規定の数を超える場合はスキップしたいので、前回どこで縦方向の切れ目を入れたのかを保存
    ex_cut_w = -1

    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")
    # 横方向に割った時の、同じ区間かつ現在の列より左のホワイトチョコの数を管理するlist
    cnt_white_prev = [0] * nums

    for w in range(W):
        # 横方向に割った時の、現在の列のホワイトチョコの数を管理するlist
        cnt_white_curr = [0] * nums
        idx = 0

        # ある列にあるホワイトの数を数える
        for h in range(H):
            if S[h][w] == "1":
                cnt_white_curr[idx] += 1
            if h < H-1 and bit & (1 << h):
                idx += 1

        # K個を上回るブロックがあったか
        is_over_K = False
        for i in range(nums):
            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                break
        
        # K個を超えるブロックがあった場合、
        if is_over_K:
            # 前回の縦の区切りが一つ手前で、最小幅に切ってもKを超える場合は、その横の区切りはできない
            if w - ex_cut_w <= 1:
                cannot_cut_h = True
                break
            else:
                cnt_cut += 1
                ex_cut_w = w
                for i in range(nums):
                    cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]

    if cannot_cut_h:
        
        continue
    
    
    ans = min(ans, cnt_cut)

    

        

print(ans)

Submission status: Wrong Answer

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)
        subcusum = []

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

        cutnum = 0
        j=0
        temp = [0]*len(subcusum)

        while j<w:
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:
                    j-=1
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
            j+=1
        
        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: Wrong Answer

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)
        subcusum = []

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

        cutnum = 0
        j=0
        temp = [0]*len(subcusum)

        while j<w:
            for l in range(len(subcusum)):
                pos = 0
                if subcusum[l][j]-temp[l]>k:
                    pos = j
                    j-=1
                    if j-pos==0:
                        cutnum+=10000
                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
            j+=1
        
        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()