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, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)
if h == 1:
    ans = 0
    cnt = 0
    for i in range(w):
        if s[0][i] == '1':
            cnt += 1
        if cnt > z:
            ans += 1
            cnt -= z
    print(ans)
    exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    #print(val,d)
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True#横がiのときにcnt2の要素がkを超えるとFalse
    flg = True#cntの要素がkを超えるとFalse
    cnt = [0] * len(lis)#全体での1の個数
    for i in range(w):
        cnt2 = [0] * len(lis)#iでの1の個数
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':#高さがkで横がiの時、
                    cnt[j] += 1#lis[j]を1たす
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        #print(cnt,cnt2)
        #print(i,val)
    if flg2 == True:
        ans = min(ans,val)
    #print(val,d,lis,flg)
print(ans)

Submission status: Accepted

Solution code:
h, w, z = map(int ,input().split())
s = []
for i in range(h):
    s.append(list(input()))
ans = int(1e9+7)
if h == 1:
    ans = 0
    cnt = 0
    for i in range(w):
        if s[0][i] == '1':
            cnt += 1
        if cnt > k:
            ans += 1
            cnt -= k
    print(ans)
    exit()

for i2 in range(2**(h-1)):
    d = [True] * (h-1)
    for j2 in range(h-1):
        if (i2 >> j2) & 1:
            d[j2] = False
    d.append(False)


    val = 0
    for i in range(len(d)-1):
        if d[i] == False:
            val += 1
    #print(val,d)
    l = []
    lis = []
    for i in range(h):
        l.append(i)
        if d[i] == False:
            lis.append(l)
            l = []

    flg2 = True#横がiのときにcnt2の要素がkを超えるとFalse
    flg = True#cntの要素がkを超えるとFalse
    cnt = [0] * len(lis)#全体での1の個数
    for i in range(w):
        cnt2 = [0] * len(lis)#iでの1の個数
        for j in range(len(lis)):
            for k in lis[j]:
                if s[k][i] == '1':#高さがkで横がiの時、
                    cnt[j] += 1#lis[j]を1たす
                    cnt2[j] += 1
            if cnt[j] > z:
                flg = False
            if cnt2[j] > z:
                flg2 = False
        if flg == False:
            for j in range(len(cnt)):
                cnt[j] = cnt2[j]
            flg = True
            val += 1
        #print(cnt,cnt2)
        #print(i,val)
    if flg2 == True:
        ans = min(ans,val)
    #print(val,d,lis,flg)
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np
H, W, K = map(int, input().split())

grid = [[] for _ in range(H) ]
for i in range(H):
  grid[i] = list(map(int, input()))

#print(grid)

def init_cnt():
  _grid = [[0] * W for _ in range(H) ]
  _grid[0][0] = grid[0][0]
  for w in range(1, W):
    _grid[0][w] = _grid[0][w-1] + grid[0][w]
  for h in range(1, H):
    cnt_w = 0
    for w in range(W):
      cnt_w += grid[h][w]
      _grid[h][w] = _grid[h-1][w] + cnt_w
  
  return _grid

_grid = init_cnt()
#print(_grid)

# (x1, y1) ~ (x2, y2)の合計
def cnt(x1, x2, y1, y2):
  if x1 == 0 and y1 == 0:
    return _grid[x2][y2]
  if x1 == 0:
    return _grid[x2][y2] - _grid[x2][y1 -1]
  if y1 == 0:
    return _grid[x2][y2]- _grid[x1 - 1][y2]
  return _grid[x2][y2] - _grid[x2][y1 - 1] - _grid[x1 - 1][y2] + _grid[x1 - 1][y1 - 1]


ans = 1010
for i in range(2 ** (H - 1)):
  res = 0
  lst = list(k for k, j in enumerate(range(H), 1) if i >> j & 1)
  res += len(lst)
  lst.append(H)
 
  #print(lst)
  y =  0
  for w in range(1, W+1):
    x = 0
    flag = False
    
    for lst_i in lst:
      if cnt(x, lst_i - 1 ,y ,w - 1) > K:
        if y + 1 < w:
          res += 1
          y = w - 1
        else:
          flag = True
        break
        
      x = lst_i 
    else:
      pass
    if flag:
      break
  else:
    ans = min(ans, res)
    
print(ans)

Submission status: Accepted

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

for div in range(1<<(H-1)):
  g = 0
  id = [None] * (H)

  # 列をgroup分け
  for i in range(H):
    id[i] = g
    if (div>>i)&1: g += 1

  # groupごとにwhite chocolateが何個あるのか
  c = [ [0]*W for _ in range(g+1) ]
  for i,block in zip(id, chocolate):
    for j,b in enumerate(block):
      if b == "1":
        c[i][j] += 1

  # 縦方向の列をgroup化する
  now = [0] * (g+1)
  lines = g
  for j in range(W):
    for i in range(g+1):
      now[i] += c[i][j]

    ok = all( n<=K for n in now )
    if not ok:
      lines += 1
      now = [0] * (g+1)
      for i in range(g+1):
        now[i] += c[i][j]
      ok = all( n<=K for n in now )
      if not ok:
        # 絶対不可能な場合
        lines = INF
        break

  ans = min(ans, lines)

print(ans)

Submission status: Accepted

Solution code:
h,w,k=map(int,input().split())
def split(word): 
    return [char for char in word]  
      
m=[]
for i in range(h):
  m.append(input())
t=[0]*(h-1)
ans=w-1+h-1
for i in range(2**(h-1)):
  failflag=0
  s=split("{0:b}".format(i))
  s.reverse()
  for j in range(h-1-len(s)):
    s.append('0')
  s.reverse()
  a=[]
  a.append([])
  for j in range(w):
    a[0].append(int(m[0][j]))
  for j in range(1,h):
    if s[j-1]=='0':
      for l in range(w):
        a[-1][l]+=int(m[j][l])
    else:
      a.append([])
      for l in range(w):
        a[-1].append(int(m[j][l]))
  n=len(a)
  tmp=0
  p=[0]*n
  flag=0
  for j in range(w):
    for l in range(n):
      if a[l][j]>k:
        failflag=1
      if p[l]+a[l][j]>k:
        flag=1
        break
    if flag==1:
      tmp+=1
      flag=0
      for t in range(n):
        p[t]=0
    for l in range(n):
      p[l]+=a[l][j]
  if failflag==0 and n-1+tmp<ans:
    ans=n-1+tmp
print(ans)

Submission status: Accepted

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


ans = 10**8
for i in range(2 ** (H-1)):
    fail_flag = False
    comb = []
    for j in range(H-1):
        if ((i >> j) & 1): 
            comb.append(j)
    comb.append(H-1)
    # print(comb)
    sections = []
    for k in range(0,len(comb)):
        if k == 0:
            sections.append( sl[0:comb[0]+1] )
        else:
            sections.append( sl[comb[k-1]+1:comb[k]+1] )
    # print(sections)

    partition_cnt = 0
    sections_w_cnts = [0]*len(sections)
    for w in range(W):
        sections_curr_w_cnts = [0]*len(sections)
        partition_flag = False
        for i, sec in enumerate(sections):
            for row in sec:
                if row[w] == '1':
                    sections_curr_w_cnts[i] += 1
                    sections_w_cnts[i] += 1
                    if sections_curr_w_cnts[i] > K:
                        fail_flag = True
                        break
                    if sections_w_cnts[i] > K:
                        partition_flag = True

            if fail_flag: break
        if fail_flag: break

        if partition_flag:
            sections_w_cnts = [v for v in sections_curr_w_cnts]
            # sections_w_cnts[:] = sections_curr_w_cnts[:]
            partition_cnt += 1
        

    if not fail_flag:
        ans = min(len(comb)-1+partition_cnt, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w,k=map(int,input().split())
    S=[input() for _ in range(h)]
    final_ans=10**10
    for row_lis in range(1<<(h-1)):
        lst=[0]*h
        q,ans=0,0
        for r in range(h-1):
            if (row_lis>>r)&1==0:
                lst[r+1]=q
            else:
                q+=1
                lst[r+1]=q
                ans+=1
        data=[0]*h
        for j in range(w):
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    ans+=1
                    break
            else:
                continue
            data=[0]*h
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    break
            else:
                continue
            break
        else:
            final_ans=min(final_ans,ans)
    print(final_ans)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

def solve(h, w, k, S):
    ret = float('inf')
    bits = 2 ** (h - 1)
    for b in range(bits):
        tmp = 0
        idx = 0
        groups = []
        for y in range(h):
            groups.append(idx)
            if (1 << y) & b:
                idx += 1
        m = idx + 1
        counts = [[0] * w for _ in range(m)]
        imp = False
        for y in range(h):
            g = groups[y]
            for x in range(w):
                if S[y][x] == 1:
                    counts[g][x] += 1
                    if counts[g][x] > k:
                        imp = True
                        break
        if imp:
            continue

        cuts = 0
        cum = [counts[g][0] for g in range(m)]
        for x in range(1, w):
            cut = False
            for g in range(m):
                cum[g] += counts[g][x]
                if cum[g] > k:
                    cut = True
                    break
            if cut:
                cuts += 1
                cum = [counts[g][x] for g in range(m)]
        ret = min(ret, m - 1 + cuts)
        #print(b, groups, m, cuts, ret)
    print(ret)
    return

def main():
    h, w, k = map(int, input().split())
    s = []
    for i in range(h):
        tmp = str(input())
        s.append([int(j) for j in tmp])
    solve(h, w, k, s)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

#da[i][j]:(0,0)~(i,j)の長方形の和
def da_generate(h, w, a):
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q - 1]
    if q == 0:
        return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

H, W, K = map(int, sys.stdin.readline().rstrip().split())
grid = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(H)]
da = da_generate(H, W, grid)

ans = 10 ** 18
for i in range(2**(H - 1)):
    res = 0
    s = [k for k, j in enumerate(range(H), 1) if i >> j & 1] # s行は含まない
    res += len(s)
    s.append(H)
    y = 0
    for w in range(1, W + 1): # w行は含まない
        x = 0
        flag = False
        for s_i in s:
            if da_calc(x, y, s_i - 1, w - 1) > K:
                if y + 1 < w:
                    res += 1
                    y = w - 1
                else:
                    flag = True
                break
            x = s_i
        else:
            pass
        if flag:
            break
    else:
        ans = min(ans, res)

print(ans)

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j+(t>j);i=h
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=0;t=j=w;d=[0]*h
 while j:
  i=c=0;j-=1
  while h-i:
   d[c]+=s[i][j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j+(t>j);i=h
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;r+=1;t,j=j,j-(t<j);i=h
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r+=1;t=j;j-=f;i=h
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r+=1;t=j;j-=f;break
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0';c+=b>>i&1;i+=1
   if max(d)>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0;j+=1
  while h-i:
   d[c]+=s[i][~j]>'0'
   if d[c]>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=w
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=t<j
   if d[c]>k:d=[0]*h;r+=1-h*w*~-f;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r-~c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k=map(int,h.split())
m=b=h+w
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0'
   if d[c]>k:d=[0]*h;f=t<j;r-=h*w*~-f-1;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m=min(m,r-~c)
print(m)

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=-1;d=[0]*h
 while~j+w:
  j+=1;i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=t<j
   if d[c]>k:d=[0]*h;r+=1-h*w*~-f;t=j;j-=f;break
   c+=b>>i&1;i+=1
 m+=r-~c,
print(min(m))

Submission status: Accepted

Solution code:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';y=t<j
   if d[c]>k:d=[0]*h;r+=1-~-y*h*w;t=j;j-=y;break
   c+=b>>i&1;i+=1
  j+=1
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+c,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1;v=c
 m+=r+v,
print(min(m))

Submission status: Accepted

Solution code:
h,*s=open(0)
h,w,k,*m=map(int,h.split())
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';f=d[c]>k
   if(t<j)&f:r+=1;t=j;d=[0]*h;break
   r+=h*w*f;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+bin(b).count('1'),
print(min(m))

Submission status: Accepted

Solution code:
x,*s=open(0)
h,w,k,*m=map(int,x.split())
for b in range(512):
 r=t=j=0;d=[0]*h
 while w-j:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=h*w*x;c+=b>>i&1;i+=1
  else:j+=1
 m+=r+bin(b).count('1'),
print(min(m))

Submission status: Accepted

Solution code:
r=range
h,*s=open(0)
h,w,k,*m=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v-=f
  if f:c=u
 if g<1:m+=l-v,
print(min(m))

Submission status: Accepted

Solution code:
m=9e9
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v-=f
  if f:c=u
 if g<1:m=min(m,l-v)
print(m)

Submission status: Accepted

Solution code:
r=range
h,*s=open(0)
m=9e9
h,w,k=map(int,h.split())
for i in r(512):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=-1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if g<1:m=min(m,v+l)
print(m)

Submission status: Accepted

Solution code:
r=range
h,*s=open(0)
m=9e9
h,w,k=map(int,h.split())
for i in r(1<<h-1):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=-1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if g<1:m=min(m,v+l)
print(m)

Submission status: Accepted

Solution code:
r=range;_,*s=open(0);m=9e9
h,w,k=map(int,_.split())
for i in r(1<<h-1):
 t=[j+1for j in r(h)if i>>j&1]+[h];l=len(t);v=-1;c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if not g:m=min(m,v+l)
print(m)

Submission status: Accepted

Solution code:
r=range;_,*s=open(0)
h,w,k=map(int,_.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):z=i>>j&1;t+=[-~j]*z;l+=z
 t+=h,
 c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if not g:m=min(m,v+l)
print(m)

Submission status: Accepted

Solution code:
r=range;_,*s=open(0)
h,w,k=map(int,_.split())
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):
  if i>>j&1:t+=j+1,;l+=1
 t+=h,
 c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if not g:m=min(m,v+l)
print(m)

Submission status: Accepted

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

for i in range(1<<H-1):
    SW = []
    tmp = S[0]
    counter = 0
    
    for k in range(H-1):
        if i>>k & 1:
            SW.append(tmp)
            tmp = S[k+1]
        else:
            tmp = [tmp[l]+S[k+1][l] for l in range(W)]
    SW.append(tmp)
    counter += len(SW)-1
    max_counter = 0

    for k in range(len(SW)):
        max_counter = max(max(SW[k]),max_counter)
    if max_counter >K:
        continue

    tmp_w = [SW[row][0] for row in range(len(SW))]
    
    for w in range(W-1):
        test = [tmp_w[row]+SW[row][w+1] for row in range(len(SW))]
        if max(test)>K:
            tmp_w = [SW[row][w+1] for row in range(len(SW))]
            counter += 1
        else:
            tmp_w = test

    posibility.add(counter)
print(min(posibility))

Submission status: Accepted

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

def func(div):
  ret=0
  n_grp=len(div)
  grp=[0]*n_grp
  div.append(h)
  for c in range(w):
    for r in range(h):
      for i in range(n_grp):
        if div[i]<=r<div[i+1]:
          grp[i]+=s[r][c]
    if max(grp)>k:
      ret+=1
      grp=[0]*n_grp
      for r in range(h):
        for i in range(len(div)):
          if div[i]<=r<div[i+1]:
            grp[i]+=s[r][c]
      if max(grp)>k:
        return -1
  return ret

# 縦の分割の仕方はpow(2,h-1)
ans=h*w
for i in range(pow(2,h-1)):
  div=[0]
  for j in range(h-1):
    if ((i>>j) & 1):#立っているビットのところで処理が走る
      div.append(j+1)
  a=func(div)
  #print(a,div)
  if a>-1:
    ans=min(ans,a+len(div)-2)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

INF = 1 << 60
H, W, K = nm()
grid = []
for i in range(H):
    row = ns()
    assert len(row) == W
    grid.append(row)


def min_vsplits(ranges):
    vsplits = 0
    block_count = [0] * len(ranges)
    for c in range(W):
        line_count = [0] * len(ranges)
        for i, (start, end) in enumerate(ranges):
            for r in range(start, end):
                if grid[r][c] == "1":
                    line_count[i] += 1
                    block_count[i] += 1
        if max(line_count) > K:
            return INF  # one column contains more than K.
        if max(block_count) > K:
            vsplits += 1
            for i in range(len(block_count)):
                block_count[i] = line_count[i]
    return vsplits


def solve():
    S = 1 << (H - 1)
    min_splits = (H - 1) * (W - 1)  # split all
    for splits in range(S):
        ranges = []
        start = 0
        stop = 1
        while splits:
            if splits & 1:
                ranges.append((start, stop))
                start = stop
            splits >>= 1
            stop += 1
        ranges.append((start, H))
        hsplits = len(ranges) - 1
        vsplits = min_vsplits(ranges)
        s = hsplits + vsplits
        if min_splits > s:
            min_splits = s
            # print(
            #     f"min_splits={min_splits} ({hsplits}+{vsplits}) ranges={ranges}",
            #     file=sys.stderr,
            # )
    return min_splits


print(solve())

Submission status: Accepted

Solution code:
import sys
#import numpy as np
#import math
#from fractions import Fraction
#import itertools
#import heapq

h,w,k=map(int,input().split())
s = [list(map(int, input())) for _ in range(h)]
res=0
ans=10**9
for i in range(2**(h-1)):
    p=1
    partation=[-1]*(h-1)

    for j in range(h-1):
        if i &(1<<j):
            partation[j]=1
            p+=1
    g=[0]*p
    res=0
    l=r=0
    f=False
    while r<w:
        m=0
        for j in range(h):
            g[m]+=s[j][r]
            if g[m]>k:
                res+=1
                g=[0]*p
                if l==r:
                  f=True
                l=r
                break
            if j<h-1 and partation[j]==1:
                m+=1
        else:
            r+=1
        if f:
          break
    else:
      res+=p-1
      if res<ans:
          ans=res
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)
#pypyを使おう!

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:




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

# 縦の累積ホワイトチョコ数
whites_col = [[0 for _ in range(W)] for _ in range(H)]
for w in range(W):
    for h in range(H):
        if h == 0:
            whites_col[h][w] = S[h][w]
        else:
            whites_col[h][w] = whites_col[h-1][w] + S[h][w]

"""
マス目で考えると、縦Hマスある場合はH+1本の横線がある。
その横線の番号を渡して、その間にある数をとってくる
"""
def calc(w, a,b):
    if a == 0:
        return whites_col[b-1][w]
    else:
        return whites_col[b-1][w] - whites_col[a-1][w]

ans = (H-1)*(W-1)
for bit in  range(1 << (H-1)):
    
    cnt_split = bin(bit).count("1")

    divs = [0]
    for i in range(H-1):
        if bit & (1 << i):
            divs.append(i+1)
    divs.append(H)

    curr = [0] * (len(divs)-1)
    prev = [0] * (len(divs)-1)
    over_K_in_curr = False
    for w in range(W):
        for i,(a,b) in enumerate(zip(divs, divs[1:])):
            curr[i] = calc(w, a, b)

        over_K_in_curr = False
        if max(curr) > K:
            over_K_in_curr = True
            break
        
        for i in range(len(divs)-1):
            prev[i] += curr[i]

        if max(prev) > K:
            cnt_split += 1
            prev = curr[:]

    if not over_K_in_curr:
        ans = min(ans, cnt_split)

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 2000
#itertoolsproductでビット全探索が簡潔に書ける
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    #横方向の分割の回数を数えている
    lst = [[s for s in S[0]]]
    #リストを新たな要素として加えるか、それとも中身を足し合わせるだけか
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        #横方向の分割を終えた時点で一列にK+1個以上あるとアウト
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)
#このコードはループをうまくリストに入れ込んでるので短く見えてすごい
#5月24日

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(accumulate(list(map(int, list(input()))))))
    for h in range(1, H):
        for w in range(W):
            S[h][w] += S[h-1][w]

    ret = float('inf')

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()