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:
def main():
    
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()def main():
    
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import numpy as np
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
int h,w,k;
string s[20];
int calc(vector<bool> const& status){
  int res=0;
  vector<int> white(h,0);
  int cnt=0;
  rep(j,w){
    int buf=0;
    rep(i,h){
      if(status[i]||i==h-1){
        if(s[i][j]=='1')buf++;
        if(buf>k){
          res=inf;
          goto FINE;
        }
        if(white[i]+buf>k){
          cnt++;
          rep(kk,h){
            white[kk]=0;
          }
          buf=0;
          rep(ii,h){
            if(status[ii]||ii==h-1){
              if(s[ii][j]=='1')buf++;
              if(buf>k){
              res=inf;
              goto FINE;
              }
              white[ii]+=buf;
              buf=0;
            }
            else{
              if(s[ii][j]=='1')buf++;
            }
          }
          break;
        }
        white[i]+=buf;
        buf=0;
      }
      else{
        if(s[i][j]=='1')buf++;
      }
    }
    NEXT:;
  }
  res=cnt;
  rep(i,h-1){
    if(status[i])res++;
  }
  FINE:
  return res;
}
int solve(vector<bool> status,int cur){
  int res;
  if(cur==h-1){
    return calc(status);
  }
  else{
    res=solve(status,cur+1);
    status[cur]=true;
    res=min(res,solve(status,cur+1));
    return res;
  }
}
signed main(){
  cin>>h>>w>>k;
  rep(i,h){
    cin>>s[i];
  }
  vector<bool> status(h,false);
  int res=solve(status,0);
  cout<<res<<endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    h, w, k = map(int, input().split())
    s = np.array([[int(i) for i in list(input())] for _ in range(h)])
    cnt = [0] * 2**(h - 1)
    for i in range(2**(h - 1)):
        ss = np.split(s, [i & 2**j for j in range(h - 1) if i & 2**j > 0])
        cnt[i] += bin(i).count("1")
        l = 0
        for j in range(1, w + 1):
            if max(si[:, l:j].sum() for si in ss) > k:
                l = j - 1
                cnt[i] += 1
    print(min(cnt))

if __name__ == '__main__':
    main()

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=10001

for i in range(2**(h-1)):
    split=[0]*h
    curcnt=0
    for j in range(h):
        if (i>>j)&1:
            split[j]=1
            curcnt+=1
        
    nsplit=curcnt+1
    sumlst=[[0]*(nsplit) for _ in range(w)]
    
    cw=0
    memo=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[memo][l]+=s[ch][cw]

            if sumlst[memo][l]>k:
                memo+=1
                break

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

print(cnt)

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=10001

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

    curcnt=sum(split)
    nsplit=curcnt+1
    
    
    cw=0
    while cw<w:
        l=0
        for ch in range(h):
            sumlst[l]+=s[ch][cw]

            if sumlst[l]>k:
                sumlst=[0]*(nsplit)
                curcnt+=1
                break

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

print(cnt)

Submission status: Runtime Error

Solution code:
h, w, k = [int(c) for c in input().split()]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    a[i] = [int(c) for c in input()]

M = h*w

def _sum(i1,i2,j1,j2):
    return sum(sum(l[j1:j2]) for l in a[i1:i2])

from functools import lru_cache
@lru_cache(2**20)
def sub(i1,i2,j1,j2):
    if _sum(i1,i2,j1,j2)<=k:
        return 0
    else:
        if i2-i1>=2:
            m1 = min(sub(i1,i3,j1,j2)+sub(i3,i2,j1,j2)+1 for i3 in range(i1+1,i2))
        else:
            m1 = M
        if j2-j1>=2:
            m2 = min(sub(i1,i2,j1,j3)+sub(i1,i2,j3,j2)+1 for j3 in range(j1+1,j2))
        else:
            m2 = M
        res = min(m1,m2)
        print(i1,i2,j1,j2,res)
        return res
print(sub(0,h,0,w))

Submission status: Runtime Error

Solution code:
h, w, k = [int(c) for c in input().split()]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    a[i] = [int(c) for c in input()]

M = h*w

def _sum(i1,i2,j1,j2):
    return sum(sum(l[j1:j2]) for l in a[i1:i2])

from functools import lru_cache
@lru_cache(2**20)
def sub(i1,i2,j1,j2):
    if _sum(i1,i2,j1,j2)<=k:
        return 0
    else:
        if i2-i1>=2:
            m1 = min(sub(i1,i3,j1,j2)+sub(i3,i2,j1,j2)+1 for i3 in range(i1+1,i2))
        else:
            m1 = M
        if j2-j1>=2:
            m2 = min(sub(i1,i2,j1,j3)+sub(i1,i2,j3,j2)+1 for j3 in range(j1+1,j2))
        else:
            m2 = M
        res = min(m1,m2)
        print(i1,i2,j1,j2,res)
        return res
sub(0,h,0,w)

Submission status: Runtime Error

Solution code:
import sys
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


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)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            ass(len(grid) > i)
            ass(len(grid[i]) > j)
            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
        # ass(len(counters))
        # ass(k)
        if max(counters) > k:
            # ass(hasattr(local_counters, 'copy'))
            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:
import sys
readline = sys.stdin.buffer.readline

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)

#ビット全探索
def bit_list(dig): #引数に何桁かを入れる
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst
#帰ってくるのは[[0,0,1],[0,1,0],[0,1,1],[1,0,0]...[1,1,1]]のようなリスト

blst = bit_list(h-1)
ans = 10**9
for i in range(len(blst)):
    res = []
    res2 = [maze[0]]
    for index,j in enumerate(blst[i],1):
        if j== "0": #分割しない
            res2.append(maze[index])
        else:
            res.append(res2)
            res2 = [maze[index]]
    res.append(res2)
    print(res)
    w_count = 0
    w_mask = [0]*(w-1) #既に仕切りを置いた場所
    for j in res:
        sub_h = len(j)
        count = 0
        
        #超えちゃったら、その手前に仕切りを入れる
        for k in range(w):
            now_row = 0
            for l in range(sub_h):
                if k != 0 and w_mask[k-1]==1: #既に仕切りがあるなら、カウントをリセットして良い
                    count = 0
                if j[l][k] == "1":
                    count += 1
                    now_row += 1
                print(count)
                if count > g: #超えちゃった
                    w_count += 1
                    #print(w_count)
                    w_mask[k-1] = 1
                    count = now_row
    print(blst[i].count("1"))
    print(w_count)
    ans = min(ans)
            


print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(lambda: 0)
for i in range(len(A)):
    d[A[i]] += 1
total = 0
for k,v in d.items():
    total += v*(v-1)//2
for a in A:
    print(total - (d[a]-1))

Submission status: Runtime Error

Solution code:
import sys
h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]

ass(False)
def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


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)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            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:
import sys
h, w, k = map(int, input().split())
grid = [[1 if v == '1' else 0 for v in input()] for _ in range(h)]


def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


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)
        ass(len(counters) == len(local_counters))
        while i < h:
            if (1 << i) & state:
                hi = i
            # print(hi, i, j)
            # print(grid[i])
            ass(len(local_counters) > hi)
            ass(i < h and j < w)
            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:
import sys
h, w, k = map(int, input().split())
grid = [[int(v) for v in input()] for _ in range(h)]


def ass(v):
    if not v:
        print(-1)
        sys.exit(0)

ass(h > 0 and w > 0 and k > 0)
for row in grid:
    ass(len(row) == w)


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:
4 10 4
1110010010
1000101110
0011101001
1101000111

Submission status: Runtime Error

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

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

ans = H * W

for c in range(2**(H-1)):
    num_lines = 0

    g = {}
    tmp = c
    g_index = 0
    for h in range(H):
        g[h] = g_index 
        num_groups = g_index 
        if tmp % 2 == 1:
            g_index += 1
        tmp //= 2

    num_groups += 1

    num_lines = num_groups - 1 

    g_sum = [0] * num_groups

    for w in range(W):
        tmp = g_sum.copy()

        ok = True
        ok2 = True
        for h in range(H):
            tmp[g[h]] += int(S[h][w])
        
            if tmp[g[h]] > K :
                # modoru
                ok = False
                if g_sum[g[h]] == 0:
                    ok2 = False

        if ok :
            g_sum = tmp
        else:
            if ok2:
                g_sum = [tmp[gi] - g_sum[gi] for gi in range(num_groups)]
                num_lines += 1
            else:
                break

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

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:
	# 		cnt=10**7
	# 	dd=copy.copy(d)
	# pre_ans+=cnt
	# ans=min(ans,pre_ans)
print(ans)

Submission status: Runtime Error

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

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

ans = H * W

for c in range(2**(H-1)):
    num_lines = 0

    g = {}
    tmp = c
    g_index = 0
    for h in range(H):
        g[h] = g_index 
        num_groups = g_index 
        if tmp % 2 == 1:
            g_index += 1
        tmp //= 2

    num_groups += 1

    num_lines = num_groups - 1 

    g_sum = [0] * num_groups

    for w in range(W):
        tmp = g_sum.copy()

        ok = True
        ok2 = True
        for h in range(H):
            tmp[g[h]] += int(S[h][w])
        
            if tmp[g[h]] > K :
                # modoru
                ok = False
                if g_sum[g[h]] == 0:
                    ok2 = False

        if ok :
            g_sum = tmp
        else:
            if ok2:
                g_sum = [tmp[gi] - g_sum[gi] for gi in range(num_groups)]
                num_lines += 1
            else:
                break

    if not ok2:
        continue

    if ans > num_lines:
        ans = num_lines


print(ans)

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:
			cnt=10**7
		dd=copy.copy(d)
	pre_ans+=cnt
	ans=min(ans,pre_ans)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter, defaultdict

N, S = map(int, input().split())
A = list(map(int, input().split()))

MOD = 998244353

dp = dict()

for i in range(N):
    dp[(i, i)] = Counter([0])

ans = 0
for m in range(1, N + 1):
    for s in range(0, N + 1 - m):
        dp[(s, s + m)] = dp[(s, s + m - 1)].copy()
        for k, v in dp[(s, s + m - 1)].items():
            if k + A[s + m - 1] <= S:
                dp[(s, s + m)][k + A[s + m - 1]] = (
                    v + dp[(s, s + m)][k + A[s + m - 1]]
                ) % MOD
        ans += dp[(s, s + m)][S]

ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
choko = []
for i in range(H):
    choko.append(list(input()))
    
# Whiteの分布を走査
def tate_scan(choko_portion):
    dosu = []
    wa = 0
    wa_lst = []
    for i in range(len(choko_portion)):
        tasu = sum(choko_portion[i])
        dosu.append(tasu)
        wa += tasu
        wa_lst.append(wa)
    return((dosu,wa_lst))

def yoko_scan(choko_portion):
    dosu = []
    ychoko = [x for x in zip(*choko_portion)]
    wa = 0
    wa_lst = []
    for i in range(len(ychoko)):
        tasu = sum(ychoko[i])
        dosu.append(tasu)
        wa += tasu
        wa_lst.append(wa)
    return((dosu,wa_lst))

scaned = tate_scan(choko)
wa = scaned[1][-1]
count = 0
divmax = (H-1)*(W-1)
for i in range(divmax):
    if wa // 2**i <= K:
        break
    count += 1
print(count)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Mar 22 20:56:06 2020

@author: naoki
"""
import math
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
H, W, K = map(int, input().split())
S = [list(map(int,str(input()).replace('\n',''))) for _ in range(H)]
t_S = [[S[j][i] for j in range(len(S))]for i in range(len(S[0]))]

sum_gyo = [sum(gyo) for gyo in S]
sum_retu = [sum(retu) for retu in t_S]

katamari = [sum(sum_retu)]

if katamari[0] > K:
    print(math.ceil(katamari[0]/K))
else:
    print(0)

Submission status: Runtime Error

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

S = [0 for i in range(H)]

for i in range(H):
  S[i] = input()
  
A = [[0]*H for i in range(H)]

for i in range(H):
  for j in range(i, H):
    # [i-j]
    temp = 0
    for k in range(W):
      # Check Greedy;
      r = 0
      for h in range(i, j+1):
        r += int(S[k][h])
      if r > k:
        A[i][j]  += H + W + 1;
      elif temp + r > k:
        A[i][j] += 1
        temp = r

ans = H+W+1
for n in range(1<<(H-1)):
  m += 0
  now = n
  s = 0
  # BitSplit...
  for i in range(H-1):
    if i % 2 == 1:
      m += A[s][i] + 1
      s = i
  ans = min(ans, m + A[s][H-1])

print(ans)

Submission status: Runtime Error

Solution code:
from itertools import product
import numpy as np
H, W, K = map(int, input().split())
S = np.array([])
for _ in range(H):
    S = np.append(S, np.array(list(input()), dtype='int'))

S = S.reshape(H, W).astype('int')

l = [[0, 1] for _ in range(H - 1)]
ans = 10**10
for arr in product(*l):
    cut = arr.count(1)
    subset = []
    arr = np.array(arr, dtype='bool')
    idx = np.arange(1, H)[arr]
    if len(idx) == 0:
        subset = [S]
    elif len(idx) == 1:
        subset.append(S[:idx[0], :])
        subset.append(S[idx[0]:, :])
    else:
        subset.append(S[:idx[0], :])
        for i in range(len(idx) - 1):
            subset.append(S[idx[i]:idx[i + 1], :])
        subset.append(S[idx[-1]:, :])

    cumsum = []
    for i in range(len(subset)):
        tmp = [(subset[i].sum(axis=1)).cumsum() for j in range(1, W + 1)]
        # tmp = [subset[i][:, :j].sum() for j in range(1, W + 1)]
        cumsum.append(tmp)
    cumsum = np.array(cumsum)
    # print('cumsum', cumsum)
    for i in range(1, W):
        # print(cumsum[:, i] > K)
        if np.any(cumsum[:, i] > K):
            cut += 1
            for j in range(cumsum.shape[0]):
                cumsum[j, :] -= cumsum[j, i - 1]
                # print('update cumsum', cumsum)
    # print('cut', cut)
    ans = min(ans, cut)
print(ans)

Submission status: Runtime Error

Solution code:
for x in product((0,1),repeat=H-1):
    cur = 0
    cnt = 0
    h = sum(x)+1
    A = [0 for _ in range(h)]
    flag = 0
    for j in range(W):
        ind = 0
        A0 = [0 for _ in range(h)]
        for i in range(H):
            if i<H-1 and x[i]==1:
                A0[ind] += S[i][j]
                ind += 1
            else:
                A0[ind] += S[i][j]
        B = [A[i]+A0[i] for i in range(h)]
        if j==0 and max(B)>K:
            flag = 1
            break
        if max(B)>K:
            cur = j
            cnt += 1
            A = A0[:]
        else:
            A = B[:]
    if flag ==0:
        cmin = min(cmin,cnt+sum(x))
print(cmin)

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(dd)):
				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

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

sum_s = [[0 for i in range(w)] for j in range(h)]
if s[0][0] == 1: sum_s[0][0] = 1
for j in range(1, w):
    sum_s[0][j] = sum_s[0][j-1] + s[0][j]
for i in range(1, h):
    sum_s[i][0] = sum_s[i-1][0] + s[i][0]
for i in range(1, h):
    for j in range(1, w):
        sum_s[i][j] = sum_s[i-1][j] + sum_s[i][j-1] - sum_s[i-1][j-1] + s[i][j]
sum_s = np.array(sum_s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = []
    temp_s = sum_s[:]
    cnt = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo.append(list(temp_s[j, :]))
            temp_s[j+1:, :] = temp_s[j+1:, :] - temp_s[j, :]
    kouryo.append(list(sum_s[h-1, :]))

    kouryo = np.array(kouryo)
    for j in range(1, w):
        if cnt >= 10**9: break
        for m in range(len(kouryo)):
            if cnt >= 10**9: break
            if kouryo[m, j] > k:
                kouryo[:, j:] = kouryo[:, j:] - kouryo[:, j-1]
                cnt += 1
                break
        for m in range(len(kouryo)):
            if kouryo[m, j-1] > k:
                cnt += 10**9
                break
    ans = min(ans, cnt)
print(ans)

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::
        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
h, w, k = map(int, input().split())
grid = [[int(v) for v in input()] for _ in range(h)]
if h == 0 or w == 0:
    print(-1)
    sys.exit(0)
for row in grid:
    if len(row) != w:
        print(-1)
        sys.exit(0)


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)