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:
h,w,k = map (int,input().split())
s = [0] * h
aans =10000000
for i in range(h):
    s[i] = [int(i) for i in str(input())]
for i in range(2 ** (h - 1)):
    ans = 0

    kugiri = [0] * (h - 1)
    for j in range(h - 1):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            kugiri[j] = 1

    box = [0] * (sum(kugiri) + 1)
    ans += sum(kugiri)
    for j in range(w): #横に見てる
        box[0] += s[0][j]
        num = 0
        for l in range(1,h): #縦に足し合わせる
            num += kugiri[l-1]

            box[num] = s[l][j] + box[num]
        for l in range(len(box)):
            if box[l] > k and j != 0:
                box = [0 for _ in range(sum(kugiri) + 1)]
                num = 0
                for m in range(1, h):
                    num += kugiri[m - 1]
                    box[num] = s[m][j] + box[num]
                ans += 1
                break
            elif box[l] > k and j == 0:
                ans += 10000000000

    aans =min(aans,ans)
    
print(aans)

Submission status: Wrong Answer

Solution code:
h,w,k = map (int,input().split())
s = [0] * h

for i in range(h):
    s[i] = [int(i) for i in str(input())]
for i in range(2 ** (h - 1)):
    ans = 0
    aans =10000000
    kugiri = [0] * (h - 1)
    for j in range(h - 1):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            kugiri[j] = 1
        
    box = [0] * (sum(kugiri) + 1)
    for j in range(w):
        box[0] += s[0][j]
        num = 0
        for k in range(1,h):
            num += kugiri[k-1]

            box[num] = s[k][j] + box[num]
        for k in range(len(box)):
            if box[k] > k:
                box = [0 for i in range(sum(kugiri) + 1)]
                num = 0
                for k in range(1, h):
                    num += kugiri[k - 1]
                    box[num] = s[k][j] + box[num]
                ans += 1
                break
    aans =min(aans,ans)
print(aans-4)

Submission status: Wrong Answer

Solution code:
h,w,k = map (int,input().split())
s = [0] * h

for i in range(h):
    s[i] = [int(i) for i in str(input())]
for i in range(2 ** (h - 1)):
    ans = 0
    aans =10000000
    kugiri = [0] * (h - 1)
    for j in range(h - 1):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            kugiri[j] = 1
        print(kugiri)
    box = [0] * (sum(kugiri) + 1)
    for j in range(w):
        box[0] += s[0][j]
        num = 0
        for k in range(1,h):
            num += kugiri[k-1]

            box[num] = s[k][j] + box[num]
        for k in range(len(box)):
            if box[k] > k:
                box = [0 for i in range(sum(kugiri) + 1)]
                num = 0
                for k in range(1, h):
                    num += kugiri[k - 1]
                    box[num] = s[k][j] + box[num]
                ans += 1
                break
    aans =min(aans,ans)
print(aans-4)

Submission status: Wrong Answer

Solution code:
'''

'''

INF = float('inf')

def main():
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S = [''.join(S[row][col] for row in range(H)) for col in range(W)]
    ans = INF
    for b in range(2**(H-1)):
        sections = [(0, H)]
        for shift in range(H-1):
            if (1<<shift) & b:
                sections.append((sections.pop()[0], shift))
                sections.append((shift, H))
        t_ans = len(sections) - 1
        count = {(l, r): 0 for l, r in sections}
        for col in range(W):
            if any(count[(l, r)] + S[col][l:r].count('1') > K for l, r in sections):
                for key in count.keys():
                    count[key] = 0
                t_ans += 1
            for l, r in sections:
                count[(l, r)] += S[col][l:r].count('1')
            if max(count.values()) > K:
                t_ans = INF
                break
        ans = min(ans, t_ans)
    print(ans)



main()

Submission status: Wrong Answer

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

s=[input() for _ in range(h)]

#hが短いのでhはbit全探索

count=10**9
#print(s)
for i in range(2**(h-1)):
    cnt=bin(i).count("1")

    #yには何行目で割るかが配列ではいる
    y=[]
    for j in range(h-1):
        if (i>>j) &1:
            y.append(j)
    y.append(h-1)
    ruiseki=[0]*(cnt+1)
    #print("y>>>>",y,cnt)
    test=0
    for xx in range(w):
        yyy=0
        flag=0
        for index,yy in enumerate(y):
            while yyy<=yy:
                if s[yyy][xx]=="1":
                    ruiseki[index]+=1
                yyy+=1
        #print(max(ruiseki))
        if max(ruiseki)>k:
            #print("reset")
            cnt+=1
            yyy=0
            ruiseki=[0]*(bin(i).count("1")+1)
            for index,yy in enumerate(y):
                while yyy<=yy:
                    if s[yyy][xx]=="1":
                        ruiseki[index]+=1
                    yyy+=1
        #print(xx,ruiseki)
        #print("count:",cnt)
    count=min(count,cnt)
print(count)

Submission status: Wrong Answer

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

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  
# 二次元累積和でチョコレートの数を管理
# 直前に選んだチョコのY座標をp,X座標をqとすると、
# チョコレートの数をO(1)で求められる
# 最初に空行を入れているので1-indexで。

for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  
# Hが10と少ないので、切る場所9箇所をすべて試しても2^9 = 512通り
# すべてに対して、Wのどこを切るかを求める。
# 二分探索なら　O(2^(H-1) * (log W * H)) = 約51200
# 線形探索でも　O(2^(H-1) * WH) = 5,120,000

def isOk(x,lastq,cond,K,H,W):
  # xで切ったとき、iで分割されたすべての領域の数がK以下になればOK
  lastp = 0 # Hを最後に切った場所
  for j in range(H-1):
    if (cond >> j) & 1: # j+1で切る
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  # 最後に切った場所から、最後まで
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") # カットした回数
  lastq = 0 # 最後にカットした場所
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cnt_num = 10000
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

Submission status: Wrong Answer

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

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  
# 二次元累積和でチョコレートの数を管理
# 直前に選んだチョコのY座標をp,X座標をqとすると、
# チョコレートの数をO(1)で求められる
# 最初に空行を入れているので1-indexで。

for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  
# Hが10と少ないので、切る場所9箇所をすべて試しても2^9 = 512通り
# すべてに対して、Wのどこを切るかを求める。
# 二分探索なら　O(2^(H-1) * (log W * H)) = 約51200
# 線形探索でも　O(2^(H-1) * WH) = 5,120,000

def isOk(x,lastq,cond,K,H,W):
  # xで切ったとき、iで分割されたすべての領域の数がK以下になればOK
  lastp = 0 # Hを最後に切った場所
  for j in range(H-1):
    if (cond >> j) & 1: # j+1で切る
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  # 最後に切った場所から、最後まで
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") # カットした回数
  lastq = 0 # 最後にカットした場所
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cnt_num = 10**10
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    onecnt = 0
    for i in range(w):
        if s[0][i] == "1":
            onecnt += 1
    print(math.ceil(onecnt/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for y in range(zerocnt+1)]
    for j in range(w):
        nex = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                nex.append(num)
                num = 0
        nex.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + nex[n] > k:
                now = nex
                cnt += 1
                break
            else:
                now[n] += nex[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    onecnt = 0
    for i in range(w):
        if s[0][i] == "1":
            onecnt += 1
    print(math.ceil(onecnt/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for y in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    onecnt = 0
    for i in range(w):
        if s[0][i] == "1":
            onecnt += 1
    print(math.ceil(onecnt/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    onecnt = 0
    for i in range(w):
      if s[0][i] == "1":
        onecnt += 1
    print(math.ceil(onecnt/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #    print(now)
  #    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])/k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
    print(now)
    print(ans,cnt,zerocnt)
    ans = min(ans,cnt+zerocnt)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])//k))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #        print(now)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

if h == 1:
    print(math.ceil("1".count(s[0])))
    exit()

for i in range(2 ** (h-1)):
    ss = str(format(i,"b").zfill(h-1))
    cnt = 0
    zerocnt = 0
    for j in range(len(ss)):
        if ss[j] == "0":
            zerocnt += 1
    now = [0 for i in range(zerocnt+1)]
    for j in range(w):
        next = []
        num = 0
        for n in range(h):
            if s[n][j] == "1":
                num += 1
            if num > k:
                break
            if n < h-1 and ss[n] == "0":
                next.append(num)
                num = 0
        next.append(num)
  #        print(next,now)
        for n in range(zerocnt+1):
            if now[n] + next[n] > k:
                now = next
                cnt += 1
                break
            else:
                now[n] += next[n]
  #        print(now)
    ans = min(ans,cnt+zerocnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    wn[ni] += int(S[j][i])
                    f = True
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                    break
                for wii in range(ni + 1):
                    wn[wii] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                        break
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                if sum(wn) > K:
                    tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H - 1):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1
        wi[ni].add(H - 1)

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                            break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                            break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from itertools import accumulate
INF = float("inf")


def bit(n, k):
    return (n >> k) & 1


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa


def bit_kthone(n, k):
    # nを二進数表現した時に、下から1となる桁を数えてk番目となる桁
    for kk in range(1, k):
        n = n ^ (n & -n)
    c = 1
    while n > 1:
        c += 1
        n >>= 1
    return c


def main():

    H, W, K = map(int, input().split())
    S = [[0]*W for _ in range(H)]
    for h in range(H):
        S[h][:] = [int(c) for c in input()]
    acc = [[0]+list(accumulate(S[h])) for h in range(H)]

    min_kaisu = +INF
    for h in range(1 << (H-1)):
        # hは分割方法を与える
        # hは領域をいくつに分割しますか
        n = bit_sum(h)+1
        # n個の配列を作り、累積和を構築します。
        division = [0]
        # まずhによって与えられる分割方向が固定されていると考える(acc)
        # Xの位置で縦方向に分割した時、それより左の領域でのホワイトチョコレートの和は、いくつか
        # K未満になるかどうか
        startend = []
        c = 0
        hh = h
        while hh != 0:
            c += 1
            if hh & 1:
                startend.append(c)
            hh >>= 1
        start = [0]+startend
        end = startend + [H]

        for x in range(1, W+1):
            # xの位置で分割したとき、左の領域のホワイトチョコレートの数
            white = [acc[i][x] - acc[i][division[-1]] for i in range(H)]
            white_sum = [sum(white[s:e]) for s, e in zip(start, end)]
            white_max = max(white_sum)
            if white_max > K:
                division.append(x-1)
        division_num = len(division)-1
        # hによる分割も考慮する
        division_tot = division_num + bit_sum(h)
        if min_kaisu > division_tot:
            min_kaisu = division_tot
            # print(bin(h), division)
    print(min_kaisu)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools
H,W,K=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

L=[[0]*(W+1)]    #数値の配列
for h in range(H):
    temp_L=[0]
    for s in S[h]:
        temp_L.append(int(s))
    L.append(temp_L)

#横方向の累積和
for h in range(H+1):
    for w in range(W):
        L[h][w+1]+=L[h][w]

#縦方向の累積和
for w in range(W+1):
    for h in range(H):
        L[h+1][w]+=L[h][w]


H_pattern=[]
for n in range(2**(H-1)):
    C=[0]
    for i in range(H-1):
        if n>>i&1:
            C.append(i+1)
    C.append(H)
    H_pattern.append(C)

ans=float("inf")
for C in H_pattern:
    cnt=0
    len_c=len(C)
    cnt+=len(C)-2
    l=0
    for r in range(W):
        for i in range(len_c-1):
            u,d=C[i],C[i+1]
            if K<L[d][r+1]-L[u][r+1]-L[d][l]+L[u][l]:
                cnt+=1
                l=r
                break
    ans=min(ans,cnt)

print ans

Submission status: Wrong Answer

Solution code:
H,W,K = map(int,input().split(sep=" "))
S = [list(map(int,list(input()))) for i in range(0,H,1)]
minimum = H+W
for sepH in range(0,2**(H-1),1):
    bitcounter = 0
    tmp_sepH = sepH
    while tmp_sepH > 0:
        if tmp_sepH & 1 == 1:
            bitcounter+=1
        tmp_sepH = tmp_sepH//2
    A = [[0 for i in range(0,W,1)] for j in range(0,bitcounter+1,1)]
    index=[[]for i in range(0,bitcounter+1,1)]
    countInd = 0
    for i in range(0,H,1):
        index[countInd].append(i)
        if (sepH >> i) & 1:
            countInd +=1
   
    for j in range(0,bitcounter+1,1):
        for i in range(0,W,1):
            for k in range(0,len(index[j]),1):
                if S[index[j][k]][i] == 1:
                    A[j][i]+=1
    countA=[0 for i in range(0,bitcounter+1,1)]
    sepCounter = 0
    dame = False

    for i in range(0,W,1):
        for j in range(0,bitcounter+1,1):
            if A[j][i] > K:
                dame = True
            countA[j] += A[j][i]
            if countA[j] > K:
                sepCounter +=1
                j=-1
                for k in range(0,bitcounter+1,1):
                    countA[k]=0

    if bitcounter+sepCounter < minimum and (not dame):
        minimum = bitcounter +sepCounter

print(minimum)