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: Runtime Error

Solution code:
H,W,K = map(int,input().split())
S = []
ssum = 0
for i in range(H):
    s = list(input())
    ssum += s.count('1')
    S.append(s)

St = [i for i in zip(*S)]

if ssum <= K:
    print(0)
else:
    ans = float('inf')
    if W == 1:
        count = 0
        now = 0
        for i in range(H):
            if S[i][0] == '1':
                now += 1
            if now == K:
                count += 1
                now = 0
        print(count)
    elif H == 1:
    if W == 1:
        count = 0
        now = 0
        for i in range(W):
            if S[0][i] == '1':
                now += 1
            if now == K:
                count += 1
                now = 0
        print(count)
    else:
        for i in range(2**(H-1)):
            cut = []
            for j in range(H-1):
                if (i >> j) & 1 == 1:
                    cut.append(j+1)
            count = len(cut)
            choco = [0 for j in range(len(cut)+1)]
            
            if not cut:
                cut.append(H)
            for j in range(W):
                flag = False
                choco[0] += St[j][:cut[0]].count('1')
                if choco[0] > K:
                    flag = True
                else:
                    for k in range(1,len(cut)):
                        if choco[k] + St[j][cut[k-1]:cut[k]].count('1') > K:
                            flag = True
                            break
                        choco[k] +=  St[j][cut[k-1]:cut[k]].count('1')
                    if len(choco) > 1:
                        if choco[-1] + St[j][cut[-1]:].count('1') > K:
                            flag =True
                        else:
                            choco[-1] +=  St[j][cut[-1]:].count('1')
    
                if flag:
                    choco[0] = St[j][:cut[0]].count('1')
                    for k in range(1,len(cut)):
                        choco[k] =  St[j][cut[k-1]:cut[k]].count('1')
                    if len(choco) > 1:
                        choco[-1] =  St[j][cut[-1]:].count('1')
                    count += 1
            ans = min(ans,count)
        print(ans)

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

H, W, K = map(int, input().split())
S = np.array([list(input()) for _ in range(H)], dtype="int")

if np.sum(S) <= K:
    print(0)
    sys.exit()

flag = 0
cnt = 0
while True:
    pcnt = 0
    # 縦方向に割る
    vs = np.sum(S, axis=0)

    ss = np.cumsum(vs)
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[0 < ss & ss <= K])
        S[:, :ind + 1] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 横方向に割る
    hs = np.sum(S, axis=1)
    ss1 = np.cumsum(vs)
    if np.count_nonzero(ss1 <= K):
        ind = np.argmax(ss1[0 < ss1 & ss1 <= K])
        S[:ind + 1, :] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 逆から探査
    ss = K - ss
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[0 < ss & ss <= K])
        S[:, ind + 1:] = 0
        pcnt += 1
    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    # 逆から探査
    ss1 = K - ss1
    if np.count_nonzero(ss <= K):
        ind = np.argmax(ss[0 < ss1 & ss1 <= K])
        S[ind + 1:, :] = 0
        pcnt += 1

    if np.sum(S) <= K:
        cnt += pcnt
        pcnt = 0
        break

    if pcnt != 0:
        cnt += pcnt
        pcnt = 0

    if pcnt == 0 and np.sum(S) > K:
        # どうにかする
        continue

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate
import numpy as np
import math


def input():
    return sys.stdin.readline().strip()


H, W, K = map(int, input().split())
S = []
A = []
for i in range(H):
    s = list(input())
    for w in range(W):
        s[w] = int(s[w])
    A.append(list(accumulate(s)))
A = np.array(A)
a = A[-1][-1]
answer = math.ceil(a / (a ** (1 / 2))) * math.floor(a ** (1 / 2))

print(answer)

Submission status: Runtime Error

Solution code:
ans=10**8
h,w,K=map(int,input().split())
s=[]
import copy
def two(x):
	return "0"*(h-1-len(bin(x)[2:]))+bin(x)[2:]
for i in range(h):
	s.append(input())
for i in range(2**(h-1)):
	r=two(i)
	pre_ans=r.count("1")
	d=[0]*(pre_ans+2)
	cnt=0
	for j in range(w):
		now=0
		for k in range(h):
			if s[k][j]=="1":
				d[now]+=1
			if k!=h-1:
				if r[k]=="1":
					now+=1
		if max(d)>K:
			e=[]
			for x in range(len(d)):
				e.append(d[x]-dd[x])
			d=copy.copy(e)
			cnt+=1
		if max(d)>K:
			pre_ans=10**7
			break
		dd=copy.copy(d)
	pre_ans+=cnt
	ans=min(ans,pre_ans)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

def divide(s):
    global ans
    left = 0
    top = 0
    right = s.shape[1] + 100
    btm = s.shape[0] + 100
    while left + 1 < right:
        if np.count_nonzero(s[:, :(left + right) // 2].ravel()) < np.count_nonzero(s[:, (left + right) // 2:].ravel()):
            left = (left + right) // 2
        else:
            right = (left + right) // 2
    
    while top + 1 < btm:
        if np.count_nonzero(s[: (top + btm) // 2].ravel()) < np.count_nonzero(s[(top + btm) // 2:].ravel()):
            top = (top + btm) // 2
        else:
            btm = (top + btm) // 2
            
    diff_1 = abs(np.count_nonzero(s[:, :left]) - np.count_nonzero(s[:, left:]))
    diff_2 = abs(np.count_nonzero(s[:top]) - np.count_nonzero(s[top:]))
   
    if diff_1 <= diff_2:
        ans += 1
        if np.count_nonzero(s[:, :left]) > K:
            divide(s[:, :left])
        if np.count_nonzero(s[:, left:]) > K:
            divide(s[:, left:])
    else:
        ans += 1
        if np.count_nonzero(s[:top]) > K:
            divide(s[:top])
        if np.count_nonzero(s[top:]) > K:
            divide(s[top:])
    
    return 0

if __name__ == "__main__":
    H, W, K = map(int, input().split())
    S = []
    for _ in range(H):
        S.append([int(s) for s in input()])
    S = np.array(S)
    ans = 0
    if np.count_nonzero(S.ravel()) <= K:
        print(ans)
        exit()
    divide(S)
    print(ans)

Submission status: Runtime Error

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

print(grid)

def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        if max(counters) > k:
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int H, W, K; cin >> H >> W >> K;
    vector<string> grid(H);
    vector<int> whites(H);
    rep(i, H) {
        cin >> grid[i];
        int white = 0;
        rep(j, W) if (grid[i][j]=='1') white++;
        whites[i] = white;
    }
    int total = accumulate(all(whites), 0);
    if (total <= K) {
        cout << 0 << endl;
        return 0;
    }
    vector<int> columns(W);
    rep(j, W) {
        int column = 0;
        rep(i, H) if(grid[i][j]=='1') column++;
        columns[j] = column;
    }
    
    // 横線だけ
    int curr = 0;
    int h_ans = 0;
    rep(i, H-1) {
        curr += whites[i];
        if (curr + whites[i+1] > K) {
            h_ans++;
            curr = 0;
        }
    }

    // 縦線だけ
    curr = 0;
    int w_ans = 0;
    rep(i, W-1) {
        curr += columns[i];
        if (curr + columns[i+1] > K) {
            w_ans++;
            curr = 0;
        }
    }

    int ans = 0;
    while (total > K) {
        ans++;
        total /= 2;
    }

    bool flag = true;
    rep(i, H) {
        if (whites[i] != whites[H-i-1]) flag = false;
    }
    rep(j, W) {
        if (columns[j] != columns[W-j-1]) flag = false;
    }
    if (H%2!=0 || W%2!=0) flag = false;
    if (!flag) ans++;

    // cout << h_ans << " " << w_ans << " " << ans << endl;

    cout << min(ans, min(h_ans, w_ans)) << endl;
}

Submission status: Runtime Error

Solution code:
def main():
    from itertools import product
    H, W, K = map(int, input().split())
    G = [list(map(int, list(input()))) for _ in range(H)]

    ans = float('inf')
    for pattern in product([0, 1], repeat=H-1):
        tmp_ans = 0
        div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [100]
        grids = []
        for i in range(len(div) - 1):
            grids.append(G[div[i]: div[i + 1]])

        rows = []
        for grid in grids:
            row = []
            for w in range(W):
                v = 0
                for h in range(len(grid)):
                    v += grid[h][w]
                row.append(v)
            rows.append(row)

        w = 0
        dead_flg = False
        counts = [0] * len(rows)
        dead_set = set()
        while w < W:
            for i, row in enumerate(rows):
                counts[i] += row[w]
                if counts[i] > K:
                    if w in dead_set:
                        dead_flg = True
                        break
                    dead_set.add(w)
                    tmp_ans += 1
                    counts = [0] * len(rows)
                    break
            else:
                w += 1

            if dead_flg:
                break
        tmp_ans += len(div) - 2
        ans = min(ans, tmp_ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	H, W, K int
	S       []string
	cw      [][]int
)

type block struct {
	t, l, b, r int
}

type qel struct {
	blist []block
	divs  int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func w(b block) int {
	result := 0
	for i := b.t; i < b.b; i++ {
		if b.l == 0 {
			result += cw[i][b.r-1]
		} else {
			result += cw[i][b.r-1] - cw[i][b.l-1]
		}
	}
	return result
}

func ww(t, l, b, r int) int {
	return w(block{t, l, b, r})
}

func solve(t, l, b, r int) int {
	if ww(t, l, b, r) <= K {
		return 0
	}
	result := 10000000
	for i := t + 1; i < b; i++ {
		result = min(result, solve(t, l, i, r)+solve(i, l, b, r))
	}
	for i := l + 1; i < r; i++ {
		result = min(result, solve(t, l, b, i)+solve(t, i, b, r))
	}
	return result + 1
}

func main() {
	H = readInt()
	W = readInt()
	K = readInt()
	S = make([]string, H)
	for i := 0; i < H; i++ {
		S[i] = readString()
	}

	cw = make([][]int, H)
	for i := 0; i < H; i++ {
		cw[i] = make([]int, W)
	}

	for i := 0; i < H; i++ {
		if S[i][0] == '1' {
			cw[i][0] = 1
		}
		for j := 1; j < W; j++ {
			cw[i][j] = cw[i][j-1]
			if S[i][j] == '1' {
				cw[i][j]++
			}
		}
	}

	/*
		result := 1000000
		q := make([]qel, 0)
		q = append(q, qel{[]block{block{0, 0, H, W}}, 0})
		for len(q) != 0 {
			t := q[0]
			q = q[1:]
			b := t.blist
			nb := make([]block, 0)
			for i := 0; i < len(b); i++ {
				if w(b[i]) > K {
					nb = append(nb, b[i])
				}
			}
			if len(nb) == 0 {
				if t.divs < result {
					result = t.divs
				}
			}
		}
	*/
	fmt.Println(solve(0, 0, H, W))
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = readInt()
	}
	return result
}

Submission status: Runtime Error

Solution code:
ans=10**8
h,w,K=map(int,input().split())
s=[]
import copy
def two(x):
	return "0"*(h-1-len(bin(x)[2:]))+bin(x)[2:]
for i in range(h):
	s.append(input())
for i in range(2**(h-1)):
	r=two(i)
	pre_ans=r.count("1")
	d=[0]*(pre_ans+1)
	cnt=0
	for j in range(w):
		now=0
		for k in range(h):
			if s[k][j]=="1":
				d[now]+=1
			if k!=h-1:
				if r[k]=="1":
					now+=1
		if max(d)>K:
			e=[]
			for x in range(len(d)):
				e.append(d[x]-dd[x])
			d=copy.copy(e)
			cnt+=1
		if max(d)>K:
			pre_ans=10**7
			break
		dd=copy.copy(d)
	pre_ans+=cnt
	ans=min(ans,pre_ans)
print(ans)

Submission status: Runtime Error

Solution code:
h, w, k = list(map(int,input().split()))
for i in range(h):
  s1 = input()
  s.append(s1)
  
white = 0

for i in range(h):
  white += s[i][0:w].count('1')
if white <= k:
  print('0')

Submission status: Runtime Error

Solution code:
H, W, K = tuple(map(int, input().split()))
import math 
L = []
cnt = 0

for _ in range(H):
    L.append([1 if x == "1" else 0 for x in list(input())])
    cnt += L[_].count(1)
    
print(math.ceil(math.log2(cnt/K)))

Submission status: Runtime Error

Solution code:
H, W, K = tuple(map(int, input().split()))
import math 
L = []
cnt = 0

for _ in range(H):
    L.append([1 if x == "1" else 0 for x in list(input())])
    cnt += L[_].count(0)
    
print(math.ceil(math.log2(cnt)))

Submission status: Runtime Error

Solution code:
h, w, k = list(map(int,input().split()))
for i in range(h):
  s1 = input()
  s.append(s1)
  
white = 0

for i in range(h):
  white += s[i].count('1')
if white <= k:
  print('0')

Submission status: Runtime Error

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


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << h):
    j = 0
    vcnt = 0
    counters = [0] * (h + 1)
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * (h + 1)
        while i < h:
            if (1 << i) & state:
                hi = i + 1
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        if max(counters) > k:
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
S = [list(map(int,list(input()))) for i in range(H)]

li = [[0 for _ in range(W)] for _ in range(H+1)]
for h in range(H):
    li[h+1][0] = S[h][0]
    for w in range(1,W):
        li[h+1][w] = li[h+1][w-1]+S[h][w]
for w in range(W):
    for h in range(1,H):
        li[h+1][w]=li[h][w]+li[h+1][w]

ans = (1<<(H))+H
for h1 in range(1<<(H-1)):
    flg = [0]
    for h2 in range(H-1): 
        if ((h1>>h2)&1):
            flg.append(h2+1)
    flg.append(H)
    
    cnt = len(flg)-2
    mm = [0 for _ in range(len(flg)-1)]
    i = 0

    a = True

    # print(flg)
    for w in range(W):
        for h in range(len(flg)-1):
            mm[h] = li[flg[h+1]][w]-li[flg[h]+1][i]
            if mm[h]>K:
                cnt += 1
                i = w
                if li[flg[h+1]][w]-li[flg[h]+1][i]>K:
                    a = False
                    # print(flg[h+1],flg[h]+1,w,flg)
                    break
    if a:
        ans = min(ans,cnt)
        if ans == cnt:
            # print(flg)

print(ans)




# for h in range(H+1):
#     print(*li[h])

Submission status: Runtime Error

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

if s.count('1') <= k:
  print('0')

Submission status: Runtime Error

Solution code:
import numpy as np

h,w,k = (int(x) for x in input().split())

s_list = np.array([[x for x in input()] for _ in range(h)])

cut_num = h + w - 2

def clear(c_list):
  c_w = [0]
  c_h = [0]
  for c in c_list:
    if c < w:
      c_w.append(c)
    else:
      c_h.append(c-w+1)
      
  c_w.append(w)
  c_h.append(h)
  
  flg = True
  for i in range(1,len(c_w)):
    for j in range(1,len(c_h)):
      field = s_list[c_h[j-1]:c_h[j],c_w[i-1]:c_w[i]]
      if np.count_nonzero(field=='1') > k:
        flg = False
        break
        
  return flg
      
def cut(c_list,k):
  if k > cut_num:
    if clear(c_list):
      return len(c_list)
    else:
      return cut_num + 1

  c_list.append(k)
  x = cut(c_list,k+1)

  c_list.remove(k)
  x = min(x,cut(c_list,k+1))
  
  return x

x = cut([],1)
print(x)

Submission status: Runtime Error

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

s=[list(map(int,[x for x in input()])) for _ in range(h)]

cnt=10000

for i in range(2**(h-1)):
    split=[0]*h

    for j in range(h-1):
        split[j]=(i>>j)&1
    
    curcnt=sum(split)
    
    sumlst=[0]*(curcnt+1)

    j=0
    while j<w:
        l=0
        ch=0

        while ch<h:
            sumlst[l]+=s[ch][j]
            
            if sumlst[l]>k:
                curcnt+=1
                sumlst=[0]*(sum(split)+1)
                j-=1
                continue

            if split[ch]==1:
                l+=1
            
            ch+=1
        
        j+=1
    
    cnt=min(cnt,curcnt)

print(cnt)

Submission status: Runtime Error

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


def count_ones(i):
    cnt = 0
    while i:
        if i & 1:
            cnt += 1
        i >>= 1
    return cnt

ans = h + w

for state in range(1 << (h - 1)):
    j = 0
    vcnt = 0
    counters = [0] * h
    is_ok = True
    while j < w:
        hi = 0
        i = 0
        local_counters = [0] * h
        while i < h:
            if (1 << i) & state:
                hi = i + 1
            local_counters[hi] += grid[i][j]
            i += 1
        for i, v in enumerate(local_counters):
            if v > k:
                is_ok = False
                break
            counters[i] += local_counters[i]
        if not is_ok:
            break
        if max(counters) > k:
            counters = local_counters.copy()
            vcnt += 1

        j += 1


    if is_ok and ans > count_ones(state) + vcnt:
        ans = count_ones(state) + vcnt
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix


def count(h0, h1, w0, w1, T):
    k = 0
    for h in range(h0, h1):
        k += T[h][w1] - T[h][w0]
    return k


def cut(h0, h1, w0, w1, K, T, n, lim):
    if n >= lim:
        return n

    if count(h0, h1, w0, w1, T) <= K:
        return n

    # -- に割る
    for h in range(h0+1, h1):
        n1 = cut(h0, h, w0, w1, K, T, n+1, lim)
        n2 = cut(h, h1, w0, w1, K, T, n+1, lim)
        n = max(n1, n2)
        if n < lim:
            lim = n

    # | に割る
    for w in range(w0+1, w1):
        n1 = cut(h0, h1, w0, w, K, T, n, lim)
        n2 = cut(h0, h1, w, w1, K, T, n, lim)
        n = max(n1, n2)
        if n < lim:
            lim = n

    return lim


def solv(H, W, K, S):
    T = []
    for s in S:
        t = [0]
        tt = 0
        for c in s:
            tt += (c == '1')
            t.append(tt)
        T.append(t)
    return cut(0, H, 0, W, K, T, 0, H+W)


if __name__ == "__main__":

    # H W K
    # S_{1,1}S_{1,2}...S_{1,W}
    # :kkkkkkkkkk
    # S_{H,1}S_{H,2}...S_{H,W}
    #
    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]

    ans = solv(H, W, K, S)
    print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product
import numpy as np
import time
import random

H, W, K = map(int, input().split())
s = [np.array(list(input()), dtype=np.int32) for _ in range(H)]

start = time.time()

# 2**(H-1)通り試す
# 事前に各行のcumsumを取っておくと多分はやい
s2 = [np.cumsum(row, dtype=np.int32) for row in s]

rate = H*W//5
mi = 10 ** 9
seed = [0, 1]
tgt = product(seed, repeat=H-1)
selected = []
# for ls in tgt:
while time.time()-start < 1.9:
    t = random.choices(seed, k=H - 1)
    if t in selected:
        continue
    selected.append(t)
    ls = t
    # numは横線の数
    num = sum(ls)+1
    tmp = num - 1
    
    s3 = np.zeros((num, W))
    s3[0] = s2[0]
    cnt = 0
    for i in range(H - 1):
        if ls[i] == 0:
            s3[cnt] += s2[i + 1]
        else:
            cnt += 1
            s3[cnt] = s2[i + 1]
    s3 = s3.T
    
    hosei = np.zeros(num)
    for w in range(W):
        if np.max(s3[:][w] - hosei) > K:
            tmp += 1
            if w != 0:
                hosei = s3[:][w - 1]
            else:
                tmp = 10 ** 9
    if mi > tmp:
        mi = tmp
z = 0
for row in s:
    z += np.sum(row)
if z <= K:
    mi = 0
print(mi)

Submission status: Runtime Error

Solution code:
import math

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

S = []
for i in range(H):
    S.append(list(map(int,input().split())))

ans = 0
for i in range(H):
    ans = ans + sum(S[i])
    
b = -(-ans//K)

c = math.ceil(math.log2(b))

print(c)

Submission status: Runtime Error

Solution code:
h,w,K = map(int,input().split())
cum = [[0 for _ in range(w+1)]]
for _ in range(h):
  tmp = input()
  add = [0]
  for j in range(w):
    add.append(add[-1]+int(tmp[j]))
  cum.append(add)
for i in range(h):
  for j in range(w):
    cum[i+1][j+1] += cum[i][j+1]
time = [0 for _ in range(h-1)]
def nex(time):
  for d in range(h-1):
    if time[d] == 0:
      time[d] = 1
      return time
    else:
      time[d] = 0
  else:
    return 'over'
can = []
while time != 'over':
  tmp = [0]
  for d in range(h-1):
    if time[d] == 1:
      tmp.append(d+1)
  tmp.append(h)
  #print(tmp,time)
  l = len(tmp) - 1
  ans = l - 1
  now = 0
  att = 1
  for j in range(1,w+1):
    cand = []
    for k in range(l):
      cand.append(cum[tmp[k+1]][j] - cum[tmp[k+1]][now] - cum[tmp[k]][j] + cum[tmp[k]][now])
    #print(cand,now,tmp)
    if max(cand) > K:
      if att == 1:
        break
      now = j - 1
      ans += 1
      att = 1
    else:
      att = 0
  else:
    #print(l-1,ans,time)
    can.append(ans)
  time = nex(time)
  #print(tmp,l-1,ans)
print(min(can))

Submission status: Runtime Error

Solution code:
import math

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

S = []
for i in range(H):
    S.append(list(map(int,input().split())))

ans = 0
for i in range(H):
    ans = ans + sum(S[i])
    
b = -(-ans//K)

c = math.floor(math.log2(b))

print(c+1)

Submission status: Runtime Error

Solution code:
import math

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

S = []
for i in range(H):
    S.append(list(map(int,input().split())))

ans = 0
for i in range(H):
    ans = ans + sum(S[i])
    
b = -(-ans//K)

c = math.floor(math.log2(b))

print(c)

Submission status: Runtime Error

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

ans = float("inf")
for state in range(2 ** (H - 1)):
    # 横棒のカウント
    yoko = 0
    for i in range(H - 1):
        if (state >> i) & 1:
            yoko += 1

    res = yoko

    # ホワイトチョコレートの個数
    cntHW = [0] * (yoko + 1)
    for j in range(W):
        # 今のグループ
        now = 0
        # 列を探索
        cntH = [0] * (yoko + 1)
        for i in range(H):
            if S[i][j] == 1:
                cntH[now] += 1

            if (state >> i) & 1: # 区切り
                now += 1
        # 個数の最大値
        MAX = max(cH + cHW for cH,cHW in zip(cntH,cntHW))
        if MAX > K:
            res += 1
            cntHW = cntH.copy()
        elif MAX == K:
            if j == W - 1: continue
            res += 1
            cntHW = [0] * (yoko + 1)
        else:
            for i in range(yoko + 1):
                cntHW[i] += cntH[i]

    ans = min(ans, res)

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    H,W,K = map(int, input().split())
    S = [[int(i) for i in list(input())] for _ in range(H)]

    ans = float("inf")
    for state in range(2 ** (H - 1)):
        # 横棒のカウント
        yoko = 0
        for i in range(H - 1):
            if (state >> i) & 1:
                yoko += 1

        res = yoko

        # ホワイトチョコレートの個数
        cntHW = [0] * (yoko + 1)
        for j in range(W):
            # 今のグループ
            now = 0
            # 列を探索
            cntH = [0] * (yoko + 1)
            for i in range(H):
                if S[i][j] == 1:
                    cntH[now] += 1

                if (state >> i) & 1: # 区切り
                    now += 1
            # 個数の最大値
            MAX = max(cH + cHW for cH,cHW in zip(cntH,cntHW))
            if MAX > K:
                res += 1
                cntHW = cntH.copy()
            elif MAX == K:
                if j == W - 1: continue
                res += 1
                cntHW = [0] * (yoko + 1)
            else:
                for i in range(yoko + 1):
                    cntHW[i] += cntH[i]

        ans = min(ans, res)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

int main(){
        int h, w, k;
        scanf("%d %d %d", &h, &w, &k);
        vector<vector<int>> cho(h, vector<int>(w));
        for(int i=0; i<h; i++){
                char s[w+1];
                scanf("%s", s);
                for(int j=0; j<w; j++){
                        cho[i][j] = (s[j]=='1');
                }
        }

        int ans = 2e9;
        for(int pt=0; pt<(1<<(h-1)); pt++){
                vector<vector<int>> ccho(cho);
                for(int i=1; i<h; i++){
                        if((pt>>(i-1))&1) continue;
                        for(int j=0; j<w; j++){
                                ccho[i][j] += ccho[i-1][j];
                                ccho[i-1][j] = 0;
                        }
                }

                //for(int i=0; i<h; i++){for(int j=0; j<w; j++) printf("%d ", ccho[i][j]);puts("");}


                int cand = 2e9;
                vector<bool> lined(w-1, 0);
                vector<int> cnt(h, 0);
                for(int j=0; j<w; j++){
                        for(int i=1; i<=h; i++){
                                if(i==h or (pt>>(i-1))&1){
                                        if(ccho[i-1][j]>k) goto brebre;
                                        cnt[i-1] += ccho[i-1][j];
                                        if(cnt[i-1]>k){
                                                lined[j-1] = 1;
                                                for(int I=0; I<h; I++) cnt[I] = ccho[I][j];
                                        }
                                }
                        }
                }
                cand = __builtin_popcount(pt);
                for(int i=0; i<w-1; i++) cand += lined[i];
                brebre:
                //printf("%d\n", cand);
                ans = min(ans, cand);
        }

        printf("%d\n", ans);
        return 0;
}

Submission status: Runtime Error

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

ans = float('inf')
for i in range(1 << (h - 1)):
    cut_h = []
    for j in range(h - 1):
        if (i >> j) & 1:
            cut_h.append(j)

    blocks = []
    before = 0
    for cut in cut_h:
        blocks.append([before, cut])
        before = cut + 1
    blocks.append([before, h - 1])

    counts = [[0] * w for _ in range(len(blocks))]
    for b in range(len(blocks)):
        for j in range(blocks[b][0], blocks[b][1] + 1):
            for k in range(w):
                if s[j][k] == '1':
                    counts[b][k] += 1

    # print(cut_h)
    # print(blocks)
    # print(counts)

    maxcounts = 0
    for j in range(len(counts)):
        for k in range(len(counts[0])):
            mincounts = max(mincounts, counts[j][k])
    if maxcounts > K:
        continue

    tmpans = len(cut_h)
    cumsums = [0] * len(blocks)
    for k in range(w):
        for b in range(len(blocks)):
            cumsums[b] += counts[b][k]

        if max(cumsums) > K:
            # print(cumsums)
            tmpans += 1
            cumsums = [counts[b][k] for b in range(len(blocks))]


    ans = min(ans, tmpans)
    # print(tmpans)
print(ans)

Submission status: Runtime Error

Solution code:
h, w, K = map(int, input().split())
grid = []
for i in range(h):
    grid.append(input())

ans = 1000000
for i in range(2**(h-1)):
    b = format(i, "0{}b".format(h-1))
    ans_temp = b.count("1")
    white_after = [0]*(ans_temp+1)
    index = 0
    for j in range(w):
        for k in range(h):
            if grid[k][j] == "1":
                white_after[index] += 1
            if k != h-1:
                if b[k] == "1":
                    index += 1
        if max(white_after) <= K:
            white_before = white_after[:]
        else:
            for k in range(len(white_after)):
                white_after[k] -= white_before[k]
            white_before = white_after[:]
            ans_temp += 1
        index = 0
    ans = min(ans, ans_temp)

print(ans)