Buggy python submission (verdict: Time Limit Exceeded):




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

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

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


    
    print(ans)
    exit()

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

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


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

ans = (H-1) + (W - 1)
for bit in range(1 << (H-1)):
    is_valid = True
    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")


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

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

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

        # K個を上回るブロックがあったか
        is_over_K = False
        
        for i in range(nums):

            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                if cnt_white_curr[i] > K:
                    is_valid = False
                break


        
        # K個を超えるブロックがあった場合、かつ、横方向の割り方は妥当な場合
        if is_over_K:
            cnt_cut += 1

            for i in range(nums):
                cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]
    



    if is_valid:
        ans = min(ans, cnt_cut)

    

        

print(ans)

    


Fixed submission:




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

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

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


    
    print(ans)
    exit()

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

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


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

ans = (H-1) + (W - 1)
for bit in range(1 << (H-1)):
    is_valid = True
    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")


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

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

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

        # K個を上回るブロックがあったか
        is_over_K = False
        
        for i in range(nums):

            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                if cnt_white_curr[i] > K:
                    is_valid = False
                break


        
        # K個を超えるブロックがあった場合、かつ、横方向の割り方は妥当な場合
        if is_over_K:
            cnt_cut += 1

            for i in range(nums):
                cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]
    



    if is_valid:
        ans = min(ans, cnt_cut)

    

        

print(ans)