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:
import collections
import math
import numpy as np
H, W, K = map(int, input().split(' '))
S = []

for i in range(H):
    S.append(list(input()))

df = np.array(S)
df = df.astype('int64')
minimum = float('inf')
for i in range(2**(H-1)):
    temp = df.copy()
    count = 0
    for j in range(H-1):
        if((i >> j) & 1):
            count += 1
            temp[H-j-2] += temp[H-j-1]
            temp = np.delete(temp, H-j-1, 0)
    count = H-1 - count
    wa = 0
    column = 0
    for k in range(1, W-1):
        temp[:, column] += temp[:, k]
        if (temp[:, column] > K).any():
            column = k
            count += 1
    if count < minimum:
        minimum = count
    count = 0

print(minimum)

Submission status: Wrong Answer

Solution code:
import collections
import math
#import pandas as pd
import numpy as np
H, W, K = map(int, input().split(' '))
S = []

for i in range(H):
    S.append(list(input()))

df = np.array(S)
df = df.astype('int64')
minimum = float('inf')
for i in range(2**(H-1)):
    temp = df.copy()
    count = 0
    for j in range(H-1):
        if((i >> j) & 1):
            count += 1
            temp[H-j-2] += temp[H-j-1]
            temp = np.delete(temp, H-j-1, 0)
    count = H-1 - count
    wa = 0
    column = 0
    print(temp)
    print()
    for k in range(1, W-1):
        temp[:, column] += temp[:, k]
        if (temp[:, column] > K).any():
            column = k
            count += 1
    if count < minimum:
        minimum = count
    count = 0

print(minimum)

Submission status: Wrong Answer

Solution code:
import collections
import math
#import pandas as pd
import numpy as np
H, W, K = map(int, input().split(' '))
S = []

for i in range(H):
    S.append(list(input()))

# df = pd.DataFrame(S)
# df = df.astype('int64')
# minimum = float('inf')
# for i in range(2**(H-1)):
#     temp = df.copy()
#     count = 0
#     for j in range(H-1):
#         if((i >> j) & 1):
#             count += 1
#             temp.iloc[H-j-2] += temp.iloc[H-j-1]
#             temp.drop(index=df.index[H-j-1], inplace=True)
#     count = H-1 - count
#     wa = 0
#     column = 0
#     for k in range(1, W-1):
#         temp.iloc[:, column] += temp.iloc[:, k]
#         if (temp.iloc[:, column] > K).any():
#             column = k
#             count += 1
#     if count < minimum:
#         minimum = count
#     count = 0

# print(minimum)

Submission status: Wrong Answer

Solution code:
# import collections
# import math
# import pandas as pd
# import numpy as np
H, W, K = map(int, input().split(' '))
S = []

for i in range(H):
    S.append(list(input()))

# df = pd.DataFrame(S)
# df = df.astype('int64')
# minimum = float('inf')
# for i in range(2**(H-1)):
#     temp = df.copy()
#     count = 0
#     for j in range(H-1):
#         if((i >> j) & 1):
#             count += 1
#             temp.iloc[H-j-2] += temp.iloc[H-j-1]
#             temp.drop(index=df.index[H-j-1], inplace=True)
#     count = H-1 - count
#     wa = 0
#     column = 0
#     for k in range(1, W-1):
#         temp.iloc[:, column] += temp.iloc[:, k]
#         if (temp.iloc[:, column] > K).any():
#             column = k
#             count += 1
#     if count < minimum:
#         minimum = count
#     count = 0

# print(minimum)

Submission status: Wrong Answer

Solution code:
def main():
  H,W,K = map(int,input().split())
  from collections import deque
  ans = 10000
  S = [list(map(int,list(input()))) for _ in range(H)]
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = [i-j for i in cum[q[a+1]] for j in cum[q[a]]]
      if max(x)>K:
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
      else:
        l = y
    ans = min(ans,t_a)

  print(ans)
  
main()

Submission status: Wrong Answer

Solution code:
H, W, K = [int(i) for i in input().split()]
N = H-1
C = [list(map(int, list(input()))) for _ in range(H)]

# # cumsum = [[0 for _ in range(W+1)] for _ in range(H+1)]
# # for i in range(H):
# #     for j in range(W):
# #         cumsum[i+1][j+1] = cumsum[i+1][j] + (1 if C[i][j] else 0)
# # for j in range(W):
# #     for i in range(H):
# #         cumsum[i+1][j+1] += cumsum[i][j+1]

# def count_white(lh, lw, rh, rw):
#     return cumsum[rh][rw]-sumsum[rh][lw]-cumsum[lh][rw]+cumsum[lh][lw]

def solve_small(lh, lw, rh, rw=W): # [l, r)
    w = 0
    res = lw
    for i in range(lw, rw):
        for j in range(lh, rh):
            if C[j][i]: w += 1
            if w > K:return res+i
    return W




mina = 10**9
for bit in range(1<<N):
    s = []
    d = 1
    for i in range(N):
        if 1 & bit>>i:
            s.append(i+1)
            d += 1
    s.append(H)
    # print(s)
    ans = d-1
    r = 0
    while r<W:
        mind = 10**9
        lh = 0
        for i in range(d):
            mind = min(mind, solve_small(lh, r, s[i]))
            lh = s[i]
        r = mind
        if r<W: ans += 1
        # print(r)
    # print(ans)
    mina = min(mina, ans)
print(mina)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=h+w-2
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    ans=min(ans,now+y)
print(ans)

Submission status: Wrong Answer

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

def solve(l):
    choco = [0 for _ in range(len(l))]
    ans = 0
    for i in range(w):
        f = True
        tmp = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    tmp[idx] += 1
        for j in range(len(l)):
            if choco[j] + tmp[j] > k:
                f = False
        if not f:
            ans += 1
            choco = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    choco[idx] += 1
    return ans + len(l) - 1


ans = 10 ** 12
for i in range(2 ** (h-1)):
    div = []
    tmp = []
    for j in range(h):
        tmp.append(j)
        if ((i >> j) & 1):
            div.append(tmp)
            tmp = []
    div.append(tmp)
    res = solve(div)
    ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

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

def solve(l):
    choco = [0 for _ in range(len(l))]
    ans = 0
    for i in range(w):
        f = True
        tmp = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    tmp[idx] += 1
        for j in range(len(l)):
            if choco[j] + tmp[j] > k:
                f = False
        if not f:
            ans += 1
            choco = [0 for _ in range(len(l))]
        for idx, vs in enumerate(l):
            for v in vs:
                if s[v][i]:
                    choco[idx] += 1
    return ans + len(l) - 1


ans = 10 ** 9
for i in range(2 ** (h-1)):
    div = []
    tmp = []
    for j in range(h):
        tmp.append(j)
        if ((i >> j) & 1):
            div.append(tmp)
            tmp = []
    div.append(tmp)
    res = solve(div)
    ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
S=[]
for i in range(h):
    s=int(input(),2)
    S.append(s)
ans=h+w-2
for i in range(2**(h-1)):
    flag=False
    now=0 #区切った数
    cnt=0 #1の数
    y=0
    for j in range(h-1):
        if (i>>j)&1:
            y+=1
    C=[0]*(y+1) #1の数保存配列
    for x in range(w):
        T=[] #現在の列での1の数保存配列
        for j in range(h):      
            cnt+=(S[j]>>x)&1
            if cnt>k:
                flag=True
                break
            if (i>>j)&1: #横の区切り判定
                T.append(cnt)
                cnt=0
            if j==h-1: #最後の列
                T.append(cnt)
                cnt=0
        if flag:
            break
        for j in range(len(C)): #それぞれのブロックに対して
            if C[j]+T[j]>k:
                now+=1
                C=T
                break
            else:
                C[j]+=T[j]
    if flag:
        break
    ans=min(ans,now+y)
print(ans)

Submission status: Wrong Answer

Solution code:
h, w, k = list(map(int, input().split()))
choco = []
for _ in range(h):
    ip = list(map(int, list(input())))
    choco.append(ip)
# print(choco)
h_cut = [True]*(h-1)
h_cut.append(False)
min_cut = w*h
while sum(h_cut) < h:
    cut_index = []
    flag = 0
    for i in range(h-1):
        if h_cut[i]:
            if flag == 0:
                h_cut[i] = False
                if not h_cut[i+1]:
                    h_cut[i+1] = True
                    flag = 1
            else:
                cut_index.append(i+1)
        else:
            if flag == 0:
                h_cut[i] = True
                flag = 1
                cut_index.append(i+1)
    cut_index.append(h)
    now_cut = len(cut_index)-1
    w_from = 0
    w_to = 1
    while w_to <= w:
        h_from = 0
        for h_i in cut_index:
            # print([l[w_from:w_to] for l in choco[h_from:h_i]], h_from, h_i, w_from, w_to)
            if sum(map(sum, [l[w_from:w_to] for l in choco[h_from:h_i]])) > k:
                if w_to - w_from == 1:
                    w_to = w
                    now_cut += w*h
                    break
                else:
                    now_cut += 1
                    w_from = w_to-1
            else:
                h_from = h_i
                w_to += 1
    if now_cut < min_cut:
        min_cut = now_cut
print(min_cut)

Submission status: Wrong Answer

Solution code:
import itertools
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
#print(S)
l=[]
id=[0]*H
tables=[[0 for _ in range(W)] for _ in range(H)]
gnum=0
ans=0
mi=float("inf")
impossibleflag=0
for k in range(pow(2,H-1)):
    for i in range(H):
        id[i]=gnum
        if (k>>i)&1:    #kが2^iを持つかどうか
            gnum=gnum+1 #持っていればそこが琴線でありそこで分ける
    gnum=gnum+1         #0~gnumのグループ番号があるので、グループ数はgnum+1
    #print(id)
    tables = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            tables[id[i]][j]=tables[id[i]][j]+int(S[i][j])
    ans=ans+gnum-1  #とりあえず素のgroup数-1こ線を引かないといけない
    #print(tables)
    groupedwchoko=[0 for _ in range(gnum)]
    for i in range(W):
        for j in range(gnum):
            groupedwchoko[j]=groupedwchoko[j]+tables[j][i]
            #print(tables[j][i])
            if groupedwchoko[j]>K:
                ans=ans+1
                groupedwchoko = [0 for _ in range(gnum)]
                for l in range(gnum):
                    groupedwchoko[l]=tables[l][i]
                    if tables[l][i]>K:
                        ans=float("inf")
        #print(groupedwchoko)
    #print(ans)
    if mi>ans:
        mi=ans
    gnum=0
    ans=0

print(mi)

Submission status: Wrong Answer

Solution code:
import itertools
H,W,K=map(int,input().split())
S=[list(input()) for _ in range(H)]
#print(S)
l=[]
id=[0]*H
tables=[[0 for _ in range(W)] for _ in range(H)]
gnum=0
ans=0
mi=float("inf")
for k in range(pow(2,H-1)):
    for i in range(H):
        id[i]=gnum
        if (k>>i)&1:    #kが2^iを持つかどうか
            gnum=gnum+1 #持っていればそこが琴線でありそこで分ける
    gnum=gnum+1         #0~gnumのグループ番号があるので、グループ数はgnum+1
    #print(id)
    tables = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            tables[id[i]][j]=tables[id[i]][j]+int(S[i][j])
    ans=ans+gnum-1  #とりあえず素のgroup数-1こ線を引かないといけない
    #print(tables)
    groupedwchoko=[0 for _ in range(gnum)]
    for i in range(W):
        for j in range(gnum):
            groupedwchoko[j]=groupedwchoko[j]+tables[j][i]
            #print(tables[j][i])
            if groupedwchoko[j]>K:
                ans=ans+1
                groupedwchoko = [0 for _ in range(gnum)]
                for l in range(gnum):
                    groupedwchoko[l]=tables[l][i]
        #print(groupedwchoko)
    #print(ans)
    if mi>ans:
        mi=ans
    gnum=0
    ans=0

print(mi)

Submission status: Wrong Answer

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)

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 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)

Submission status: Wrong Answer

Solution code:
def main():
  H,W,K = map(int,input().split())
  from collections import deque
  ans = 10000
  S = [list(map(int,list(input()))) for _ in range(H)]
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = [x-y for x in cum[q[a+1]] for y in cum[q[a]]]
      for j in x:
        if j>K:
          judge = True
          break
      if judge:
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      for x,a in enumerate(p):
        y = l[x]+a[w]
        if y>K:
          t_a+=1
          l = [0]*n
          for z,b in enumerate(p):
            l[z] = b[w]
          break
        else:
          l[x]=y
    ans = min(ans,t_a)

  print(ans)
  
main()

Submission status: Wrong Answer

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)

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 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 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
    if num < ans:
        ans = num
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

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

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


def f(i1, j1, i2, j2):
    return cs[i1][j1] - cs[i1][j2] - cs[i2][j1] + cs[i2][j2]


ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1:
            border.append(i + 1)
            cand += 1
    border.append(h)

    j0 = 0
    # cut = []
    for j in range(w):
        for i, bi in enumerate(border[:-1]):
            if f(border[i + 1], j, bi, j0) <= k and \
               f(border[i + 1], j + 1, bi, j0) > k:
                cand += 1
                j0 = j
                # cut.append(j)

    # print(border, cand, cut)
    if f(border[-1], w, border[-2], j0) <= k:
        ans = min(ans, cand)
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
from collections import deque
ans = 10000
S = [list(map(int,list(input()))) for _ in range(H)]
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]

for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = [x-y for x in cum[q[a+1]] for y in cum[q[a]]]
    for j in x:
      if j>K:
        judge = True
        break
    if judge:
      break
    else:
      p.append(list(x))

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+a[w]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)

Submission status: Wrong Answer

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)

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 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:
                            check[k] = sum([S[t][j] for t in range(p[k], p[k + 1])])
                    break
    if num < ans:
        ans = num
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 = 10**9 + 7
for i in range(2**(h-1)):
    ans_temp = 0
    b = "".join(list(reversed(str(bin(i)[2:]).zfill(h-1))))
    # print(b)
    ls_group_id = [0]*h
    group_id = 0
    for j in range(1,h):
        if b[j-1]=="1":
            ans_temp += 1
            group_id += 1
            ls_group_id[j] = group_id
        else:
            ls_group_id[j] = group_id
    # print(ls_group_id)
    # ここまでOK?

    ls_white_in_group = [0]*h
    for j in range(w):
        for l in range(h):
            if s[l][j]==1:
                ls_white_in_group[ ls_group_id[l] ] += 1
            else:
                pass
        
        if max(ls_white_in_group)==k and j!=(w-1):
            ls_white_in_group = [0]*h
            ans_temp += 1
        elif max(ls_white_in_group)>k:
            ans_temp += 10**9 + 7
        else:
            pass
    
    ans = min(ans,ans_temp)
print(ans)

Submission status: Wrong Answer

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)

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 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 l in range(len(p) - 1):
                        if p[l + 1] - p[l] == 1:
                            check[l] = S[l][j]
                        else:
                            check[l] = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    break
    if num < ans:
        ans = num
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline

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

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


def f(i1, j1, i2, j2):
    return cs[i1][j1] - cs[i1][j2] - cs[i2][j1] + cs[i2][j2]


ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1:
            border.append(i + 1)
            cand += 1
    border.append(h)

    j0 = 0
    for j in range(w):
        for i, bi in enumerate(border[:-1]):
            if f(border[i + 1], j, bi, j0) <= k and \
               f(border[i + 1], j + 1, bi, j0) > k:
                cand += 1
                j0 = j

    # print(border, cand0, cand, cut)
    ans = min(ans, cand)
print(ans)

Submission status: Wrong Answer

Solution code:
def make_bit(i):
    if i == h - 1:
        solve(t)
        return
    make_bit(i + 1)
    t[i] = 1
    make_bit(i + 1)
    t[i] = 0

def solve(u):
    global ans
    c = sum(u)
    x = [0] * (c + 1)
    y = [0] * h
    for i in range(h - 1):
        y[i + 1] = y[i] + u[i]
    for i in range(w):
        for j in range(h):
            x[y[j]] += int(s[j][i])
        if max(x) > k:
            c += 1
            x = [0] * c
            for j in range(h):
                x[y[j]] += int(s[j][i])
    if ans > c:
        ans = c
    return

h, w, k = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [0] * (h - 1)
ans = 114514
make_bit(0)
print(ans)

Submission status: Wrong Answer

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)

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 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:
                    check[l] += sum([S[t][j] for t in range(p[l], p[l+1])])
            for l in check:
                if l > K:
                    num += 1
                    for l in range(len(p) - 1):
                        if p[l + 1] - p[l] == 1:
                            check[l] = S[l][j]
                        else:
                            check[l] = sum([S[t][j] for t in range(p[l], p[l + 1])])
                    break
    if num < ans:
        ans = num
print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
xyz = [0,1,2]
S = np.array([list(map(int,list(input()))) for _ in range(H)])
cum = [[0]*W for _ in range(H+1)]
for j in range(W):
  for i in range(1,H+1):
    cum[i][j] = cum[i-1][j]+S[i-1][j]
    
cum = np.array(cum)
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  q = list(q)
  p = deque()
  judge = False
  for a in range(len(q)-1):
    x = cum[q[a+1]]-cum[q[a]]
    if (x>K).any():
      judge = True
      break
    else:
      p.append(list(x))

  if judge:
    continue
  p = list(p)
  t_a = len(q)-2
  n = len(p)
  l = [0]*n
  for w in range(W):
    for x,a in enumerate(p):
      y = l[x]+xyz[2]
      if y>K:
        t_a+=1
        l = [0]*n
        for z,b in enumerate(p):
          l[z] = b[w]
        break
      else:
        l[x]=y
  ans = min(ans,t_a)
    
print(ans)