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())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 6
for a in range((H-1)**2):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if not flag:
            break
        else:
            for i, (start, end) in enumerate(H_):
                if not flag:
                    break
                else:
                    for h in range(start, end):
                        if chocolate[h][w] == "1":
                            white_counter[i] += 1
                            if white_counter[i] > K:
                                white_counter = [0]*parts_num
                                count += 1
                                for i_, (start_, end_) in enumerate(H_):
                                    for h in range(start_, end_):
                                        if chocolate[h][w] == "1":
                                            white_counter[i_] += 1
                                for c in white_counter:
                                    if c > K:
                                        flag = False
                                break
    if ans > count and flag:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 6
for a in range((H-1)**2):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))

    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if not flag:
            break
        else:
            for i, (start, end) in enumerate(H_):
                if not flag:
                    break
                else:
                    for h in range(start, end):
                        if chocolate[h][w] == "1":
                            white_counter[i] += 1
                            if white_counter[i] > K:
                                white_counter = [0]*parts_num
                                count += 1
                                for i_, (start_, end_) in enumerate(H_):
                                    for h in range(start_, end_):
                                        if chocolate[h][w] == "1":
                                            white_counter[i_] += 1
                                for c in white_counter:
                                    if c > K:
                                        flag = False
                                break
    if ans > count and flag:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 5
for a in range((H-1)**2):
    flag = True
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))

    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        if flag:
            for i, (start, end) in enumerate(H_):
                if flag:
                    for h in range(start, end):
                        if chocolate[h][w] == "1":
                            white_counter[i] += 1
                            if white_counter[i] > K:
                                white_counter = [0]*parts_num
                                count += 1
                                for i_, (start_, end_) in enumerate(H_):
                                    for h in range(start_, end_):
                                        if chocolate[h][w] == "1":
                                            white_counter[i_] += 1
                                for c in white_counter:
                                    if c > K:
                                        flag = False
                                break
    if ans > count and flag:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
H, W, K = map(int, input().split())
chocolate = [list(input()) for _ in range(H)]
ans = 10 ** 5
for a in range((H-1)**2):
    count = 0
    H_ = []
    before_b = 0
    for b in range(H-1):
        if ((a >> b) & 1):
            H_.append((before_b, b+1))
            before_b = b + 1
            count += 1
    H_.append((before_b, H))

    parts_num = len(H_)
    white_counter = [0] * parts_num
    for w in range(W):
        for i, (start, end) in enumerate(H_):
            flag = True
            for h in range(start, end):
                if flag:
                    if chocolate[h][w] == "1":
                        white_counter[i] += 1
                        if white_counter[i] > K:
                            white_counter = [0]*parts_num
                            count += 1
                            for i_, (start_, end_) in enumerate(H_):
                                for h in range(start_, end_):
                                    if chocolate[h][w] == "1":
                                        white_counter[i_] += 1
                            flag = False
    if ans > count:
        ans = count

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def count1_inrange(a,b,c,d,CHOCO):
    """
    CHOCOにおいて(a,b)から(c,d)の範囲にある1の数を数える
    """
    one=0
    for i_a in range(a,c+1):
        for i_b in range(b,d+1):
            one+=CHOCO[i_a][i_b] 
    return one

INPUT=input().split()
H=int(INPUT[0])
W=int(INPUT[1])
K=int(INPUT[2])
CHOCO=[[0 for i_a in range(W)] for i_b in range(H)]
for i_a in range(H):
    INPUT=list(input())
    for i_b in range(W):
        CHOCO[i_a][i_b]=int(INPUT[i_b])

Min_Lines=H*W
for _a in range(1<<H-1):
    Lines=ones=flag_bad=0
    for _b in range(H-1):
        if (_a & 1<<_b):
            ones+=1
    #:ones: _aをbinで表したときの1の数。(分け目の数)
    Lines=ones
    set_H=[0]*(2*ones+2)
    flag_1=0
    for _b in range(H-1):
        if (_a & 1<<_b):
            set_H[flag_1*2+1]=_b
            set_H[flag_1*2+2]=_b+1
            flag_1+=1
    set_H[-1]=H-1
    """
    :set_H: 縦のセット。
    """
    Left=Right=0
    for _b in range(W):
        #横移動
        Right=_b
        for _c in range(ones+1):
            #縦移動
            print(_a,set_H[_c*2],Left,set_H[_c*2+1],Right,count1_inrange(set_H[_c*2],Left,set_H[_c*2+1],Right,CHOCO) > K)
            if (Left==Right and count1_inrange(set_H[_c*2],Left,set_H[_c*2+1],Right,CHOCO) > K):
                flag_bad=1
                print("flag_bad")
            elif (count1_inrange(set_H[_c*2],Left,set_H[_c*2+1],Right,CHOCO) > K):
                Left=_b
                Lines+=1
                print("elif")
                break
    if (flag_bad==1):
        continue
    print("Min_Lines=",Min_Lines)
    Min_Lines=min(Min_Lines,Lines)
print(Min_Lines)

Submission status: Wrong Answer

Solution code:
import sys

def count1_inrange(a,b,c,d,CHOCO):
    """
    CHOCOにおいて(a,b)から(c,d)の範囲にある1の数を数える
    """
    one=0
    for i_a in range(a,c+1):
        for i_b in range(b,d+1):
            one+=CHOCO[i_a][i_b] 
    return one

INPUT=input().split()
H=int(INPUT[0])
W=int(INPUT[1])
K=int(INPUT[2])
CHOCO=[[0 for i_a in range(W)] for i_b in range(H)]
for i_a in range(H):
    INPUT=list(input())
    for i_b in range(W):
        CHOCO[i_a][i_b]=int(INPUT[i_b])

Min_Lines=H*W
for _a in range(1<<H-1):
    Lines=0
    ones=0
    for _b in range(H-1):
        if (_a & 1<<_b):
            ones+=1
    #:ones: _aをbinで表したときの1の数。(分け目の数)
    Lines=ones
    set_H=[0]*(2*ones+2)
    flag_1=0
    for _b in range(H-1):
        if (_a & 1<<_b):
            set_H[flag_1*2+1]=_b
            set_H[flag_1*2+2]=_b+1
            flag_1+=1
    set_H[-1]=H-1
    """
    :set_H: 縦のセット。
    """
    Left=Right=0
    for _b in range(W):
        #横移動
        Right=_b
        for _c in range(ones+1):
            #縦移動
            if (count1_inrange(set_H[_c*2],Left,set_H[_c*2+1],Right,CHOCO) > K):
                Left=_b
                Lines+=1
                break
    Min_Lines=min(Min_Lines,Lines)
print(Min_Lines)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0] * W] * g
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=[int(j) for j in input().split()]
s=[list(map(int,list(input()))) for i in range(h)]
import itertools
s=tuple(itertools.chain(*zip(*s)))
ans=10**18
for i in range(1<<(h-1)):
    dp=list(s)
    for j in range(h-1):
        if i&(1<<j):
            for n in range(0,h*w,h):
                dp[n+j+1]+=dp[n+j]
    tmp=h-1-bin(i).count("1")
    for n in range(0,h*w,h):
        if any(dp[n+j]>k for j in range(h)):
            break
        if n+h==h*w:
            ans=min(ans,tmp)
            break
        if any(dp[n+j]+dp[n+j+h]>k for j in range(h)):
            tmp+=1
            continue
        for j in range(h):
            dp[n+j+h]+=dp[n+j]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
h,w,k=[int(j) for j in input().split()]
s=[list(map(int,list(input()))) for i in range(h)]
import itertools
s=tuple(itertools.chain(*zip(*s)))
ans=10**18
for i in range(1<<(h-1)):
    dp=list(s)
    for j in range(h-1):
        if i&(1<<j):
            for n in range(0,h*w,h):
                dp[n+j+1]+=dp[n+j]
    tmp=h-1-bin(i).count("1")
    for n in range(0,h*w,h):
        if any(dp[n+j]>k for j in range(h)):
            break
        if n+h==h*w:
            ans=min(ans,tmp)
            break
        if any(dp[n+j]+dp[n+j+h]>k for j in range(h)):
            tmp+=1
            continue
        for j in range(h):
            dp[n+j+h]+=dp[n+j]
    ans=min(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w,k = m()

s = []

for i in range(h):
    s.append(list(map(int,input()[:-1])))

st = [0 for i in range(h)]
dp = [[0,0] for i in range(h)]
ans = mod

for po in range(2 << h):
    de = 0
    tm = 0
    for j in range(h):
        dp[j][0] = 0
        dp[j][1] = 0
    for j in range(h):
        if j == 0:
            st[0] = 0
        else:
            a = (po>>j)&1
            b = (po>>(j-1))&1
            if a != b:
                de += 1
            st[j] = de
            
    tm += de
    
    for kp in range(w):
        for kk in range(h):
            if s[kk][kp] == 1:
                dp[st[kk]][1] += 1
        if all(dp[x][0] + dp[x][1] <= k for x in range(h)):
            for kk in range(h):
                dp[kk][0] += dp[kk][1]
                dp[kk][1] = 0
        else:
            tm += 1
            for kk in range(h):
                dp[kk][0] = dp[kk][1]
                dp[kk][1] = 0
    ans = min(tm,ans)
print(ans)

Submission status: Wrong Answer

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

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = g - 1
    now = [0] * g

    # def add(j):
    #     for i in range(g):
    #         now[i] += c[i][j]
    #         if now[i] > k:
    #             return False
    #     return True

    # for j in range(w):
    #     if not add(j):
    #         tmp_ans += 1
    #         now = [0] * g
    #         if not add(j):
    #             tmp_ans = INF
    #             break

    impossible = 0
    for j in range(w):
        if impossible:
            tmp_ans = INF
            break
        for i in range(g):
            if c[i][j] > k:
                impossible = 1
                break
            now[i] += c[i][j]
            if now[i] > k:
                tmp_ans += 1
                now = []
                for cg in [c[gi][j] for gi in range(g)]:
                    if cg > k:
                        impossible = 1
                        break
                    now.append(cg)
                continue

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Wrong Answer

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

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = g - 1
    now = [0] * g
    impossible = 0
    for i in range(w):
        if impossible:
            tmp_ans = INF
            break
        for j in range(g):
            if c[j][i] > k:
                impossible = 1
                break
            now[j] += c[j][i]
            if now[j] > k:
                now = [c[gi][i] for gi in range(g)]
                tmp_ans += 1
                continue

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
field = []
sum = []
def give_cnt(x1, y1, x2, y2):
    count = sum[i + 1][pos_w + 1] - sum[prev_h][prev_w] - sum[prev_h][prev_w] + \
            sum[prev_h][prev_w]
    return count

for i in range(n + 1):
    lst = []
    for j in range(m + 1):
        lst.append(0)
    sum.append(lst)
for i in range(n):
    field.append(input())
for i in range(n + 1):
    for j in range(m + 1):
        if i == 0 or j == 0:
            sum[i][j] = 0
        else:
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + (field[i - 1][j - 1] == '1') - sum[i - 1][j - 1]
min_ans = 1000000000000
for prof in range(1, 2 ** n):
    raz = []
    for i in range(0, 10):
        mask = 1 << i
        if prof & mask:
            raz.append(i)
    ans = len(raz)
    raz.append(n - 1)
    prev_w = 0
    pos_w = 0
    cur = 0
    used = [0] * m
    while pos_w < m:
        used[pos_w] += 1
        prev_h = 0
        flag = 0
        for i in raz:
            count = sum[i + 1][pos_w + 1] - sum[prev_h][pos_w + 1] - sum[i + 1][prev_w] + sum[prev_h][prev_w]
            if count > k:
                flag = 1
            prev_h = i + 1
        if flag:
            ans += 1
            if used[pos_w] < 2:
                pos_w -= 1
                prev_w = pos_w
        pos_w += 1
    min_ans = min(min_ans, ans)
print (min_ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1].copy())
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    for j in cuts:
        if any(k > K for k in j):
            continue

    h = len(cuts)
    tmp = [0] * h

    for j in range(W):
        for k in range(h):
            tmp[k] += cuts[k][j]
        for k in tmp:
            if k > K:
                cnt += 1
                tmp = [cuts[l][j] for l in range(h)]
                break
    if cnt < answer:
        answer = cnt

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1].copy())
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    h = len(cuts)
    tmp = [0] * h

    for j in range(W):
        for k in range(h):
            tmp[k] += cuts[k][j]
        for k in tmp:
            if k > K:
                cnt += 1
                tmp = [cuts[l][j] for l in range(h)]
                break
    if cnt < answer:
        answer = cnt

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1])
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    h = len(cuts)
    tmp = [0] * h

    for j in range(W):
        for k in range(h):
            tmp[k] += cuts[k][j]
        for k in tmp:
            if k > K:
                cnt += 1
                tmp = [cuts[l][j] for l in range(h)]
                break
    if cnt < answer:
        answer = cnt

print(answer)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w,k = m()

s = []

for i in range(h):
    s.append(l())

st = [0 for i in range(h)]
dp = [[0,0] for i in range(h)]
ans = mod

for po in range(2 << h):
    de = 0
    tm = 0
    for j in range(h):
        dp[j][0] = 0
        dp[j][1] = 0
    for j in range(h):
        if j == 0:
            st[0] = 0
        else:
            a = (i>>j)&1
            b = (i>>(j-1)) & 1
            if a != b:
                de += 1
                st[j] = de
    tm += de

    for k in range(w):
        for kk in range(h):
            dp[st[kk]][1] += 1
        if all(dp[x][0] + dp[x][1] < k for x in range(h)):
            for kk in range(h):
                dp[kk][0] += dp[kk][1]
        else:
            tm += 1
            dp[kk][0] = dp[kk][1]
    ans = min(tm,ans)
print(ans)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


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

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]

    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False

            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1],v)
        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


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

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[]
    for j in range(h-1):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)
    line=[0]+line+[h]
    print(line)
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False

            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1],v)
        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
def isCont(l):
    return bool(l[-1]+l[-2] <= k)

def cutChoco(l):
    l[-2] += l[-1]
    l.pop(-1)

h, w, k = map(int,input().split())
ans = (w-1)*(h-1)+1
s = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    row = input()
    for j in range(w):
        s[i][j] = int(row[j])
#print(s)

for i in range(2**(h-1)):
#    print('----{}----'.format(str(bin(i))))
    tmp = [0]
    tmp[0] = s[0].copy()
    div = 0
    for j in range(h-1):
        if ((i >> j) & 1) == 1:
            tmp[-1] = [x+y for (x,y) in zip(tmp[-1],s[j+1])]
        else:
            tmp.append(s[j+1].copy())
            div += 1
#    print(tmp,s)
    for n in range(w):
        if len(tmp[0]) == 1:
            break
        contflag = 1
        for item in tmp:
#            print(item)
            contflag *= isCont(item)
        if contflag == 1:
            for item in tmp:
                cutChoco(item)
        else:
            div += 1
            for item in tmp:
                item.pop(-1)
#    print(div)
    ans = min(ans,div)            
print(ans)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


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

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[0]
    for j in range(h):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)-1
    line.append(h)
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1]-s[line[l+1]][k1-1]-s[line[l]][k1]>k:
                flag=False

            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1],v)
        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)

Submission status: Wrong Answer

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

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


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

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[0]
    for j in range(h):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)-1
    line.append(h)
    x=0
    flag=True
    for k1 in range(1,w+1):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if s[line[l+1]][k1-1]-s[line[l+1]][k1]-s[line[l]][k1]>k:
                flag=False

            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1],v)
        if v<=k:
            continue
        else:
            cnt+=1
            x=k1-1
    if flag:
        ans=min(cnt,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import itertools
from itertools import accumulate
# operatorモジュールから関数形式の標準演算子をインポート
from operator import add, mul

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

for i in range(h):
    for j in range(w):
        s[i][j]=int(s[i][j])

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

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


s=[[0]*w]+s

ans=float('inf')
#bit 全探索
for i in range(2**(h-1)):
    line=[0]
    for j in range(h):
        if (i>>j)&1:
            line.append(j+1)
    cnt=len(line)-1
    line.append(h)
    x=0
    flag=True
    for k1 in range(w):
        v=0
        for l in range(len(line)-1):
            # どう分割してもダメな奴に✖︎のフラグ立てる
            if k1>=1:
                if s[line[l+1]][k1-1]-s[line[l+1]][k1]-s[line[l]][k1]>k:
                    flag=False
            else:
                if s[line[l + 1]][k1]- s[line[l]][k1] > k:
                    flag=False

            v=max(s[line[l+1]][k1]-s[line[l+1]][x]-s[line[l]][k1],v)
        if v<=k:
            continue
        else:
            cnt+=1
            x=l
    if flag:
        ans=min(cnt,ans)
print(ans)

Submission status: Wrong Answer

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

ret = H * W
for bits in range(1 << (H - 1)):
    # 水平カットで生成される2枚目以降の開始行
    # 0行目は確定で, 残りのカットを調べる
    # 次の変換が必要
    # [0,H) -> [1,H]

    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
    # group = [0,0,1,1,1,2,...]

    ctr = [0] * H
    add_v = [0] * H
    c, pc = 0, -1
    cut = bin(bits).count('1')
    while c < W:
        need_cut = False
        for r in range(H):
            g = group[r]
            add_v[g] += s[r][c]
            if ctr[g] + add_v[g] > K:
                need_cut = True
                break

        if need_cut:
            if pc == c:
                t = H * W
                break
            ctr = [0] * H
            add_v = [0] * H
            cut += 1
            pc = c
            if cut >= ret:
                break
            continue

        for g, _add_v in enumerate(add_v):
            ctr[g] += _add_v
        add_v = [0] * H
        pc = c
        c += 1

    ret = min(ret, cut)

print(ret)

Submission status: Wrong Answer

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

    ans = 10 ** 9

    for bit in range(1 << (H-1)):
        canSolve = True
        ord = [0] * (H + 1)
        N = 0
        for i in range(H):
            if bit & 1 << i:
                ord[i+1] = ord[i] + 1
                N += 1
            else:
                print(i)
                ord[i+1] = ord[i]
        nums = [0] * (H + 1)
        for w in range(W):
            one = [0] * (H + 1)
            overK = False
            for h in range(H):
                one[ord[h]] += int(S[h][w])
                nums[ord[h]] += int(S[h][w])
                if one[ord[h]] > K:
                    canSolve = False
                if nums[ord[h]] > K:
                    overK = True
            if not canSolve:
                break
            if overK:
                N += 1
                nums = one
        if canSolve and ans > N:
            ans = N
    print(ans)

if __name__ == '__main__':
    main()