Buggy python submission (verdict: Time Limit Exceeded):
H, W, K = map(int, input().split())

G = [list(input()) for _ in range(H)]

ans = H * W

def calc(lst):
    group = sum(lst) + 1
    tmp = [[0] * W for _ in range(group)] #何グループに分かれるか
    k = 0
    for j in range(W):
        for i in range(H):
            if G[i][j] == '1':
                tmp[k][j] += 1
            if lst[i] == 1 or i == H - 1:
                k = (k + 1) % group
    
    cut = group - 1
    for j in range(W):
        flag = False
        for i in range(group):
            if tmp[i][j] > K:
                return 10 ** 9
            if j < W - 1:
                if tmp[i][j] + tmp[i][j + 1] > K: #次の戸合わせてKより大きくなるなら切る
                    flag = True
        if flag:
            cut += 1
        else:
            for i in range(group):
                if j < W - 1:
                    tmp[i][j + 1] += tmp[i][j]
    return cut


for i in range(2 ** (H - 1)): #ビットでカットするラインを探索
    lst = [0] * H
    for j in range(H - 1):
        if (i >> j) & 1: #切れるとき
            lst[j] = 1
    # print (lst)
    ans = min(ans, calc(lst))

print (ans)
    


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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W, K = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    ans = 10 ** 6

    def calc(lst): #lst: 区切りを与える
        n = sum(lst) + 1 #n+1個に縦を区切る
        tmp = [0] * n
        count = n - 1 #区切る本数
        for w in range(W):
            position = 0
            now = [0] * n
            for h in range(H):
                if S[h][w] == '1': #ホワイトチョコレートのとき
                    now[position] += 1
                if lst[h] == 1:
                    position += 1
            
            flag = True
            for i in range(n):
                if tmp[i] + now[i] > K:
                    flag = False

            if flag:
                for i in range(n):
                    tmp[i] += now[i]
            else:
                count += 1
                for i in range(n):
                    tmp[i] = now[i]
        for i in range(n):
            if now[i] > K:
                count += 10 ** 6
                
        return count

    for i in range(2 ** (H - 1)):
        lst = [0] * (H)
        for j in range(H - 1):
            if (i >> j) & 1:
                lst[j] = 1
        ans = min(calc(lst), ans)

    print (ans)

if __name__ == '__main__':
    main()

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Buggy python submission (verdict: Time Limit Exceeded):
H, W, K = map(int, input().split())
S = [list(input()) for _ in range(H)]

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)
        

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)