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:
import math
import functools
from operator import add

def main():
    h,w,k = tuple([int(t)for t in input().split()])

    s = [[int(i) for i in list(input())] for _ in range(h)]
    
    cusum = [accumelist(s_) for s_ in s]

    candidates = []

    for i in range(1<<(h-1)):
        subcu = divide(cusum,i)
        subcusum = []

        for sub_ in subcu:
            subcusum.append(functools.reduce((lambda a,b:list(map(add,a,b))),sub_))

        cutnum = 0
        j=0
        temp = [0]*len(subcusum)

        for j in range(w):
            for l in range(len(subcusum)):
                if subcusum[l][j]-temp[l]>k:

                    temp = [x[j-1] for x in subcusum]
                    cutnum+=1
                    break
        
        candidates.append(cutnum+bin(i).count('1'))

    print(min(candidates))
            
def divide(s,i):
    subs = []
    counter = 0
    pos = 0
    while i!= 0:
        counter +=1
        if i%2==1:
            subs.append(s[pos:counter])
            pos = counter
        i >>=1
 
    subs.append(s[pos:])
    return subs

def accumelist(s):
    if s == []:
        return []
    res = [s[0]]
    for i in range(1,len(s)):
        res.append(res[i-1]+s[i])

    return res

def _add_(a,b):
    return map(add,a,b)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

#####

import numpy as np
from numpy import int32
# from collections import Counter

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	h,w,k=getIntList(inputs[0])
	
	grid=np.empty((h,w),np.bool)
	for hi in range(h):
		grid[hi]=np.array([c=="1" for c in inputs[1+hi][0]])
	
# 	h=10
# 	w=1000
# 	k=10
# 	grid=np.random.randint(0,2,(h,w))
	
# 	print(grid.astype(int32))
# 	print()
# 	from matplotlib import pyplot as plt
# 	plt.imshow(grid)
# 	plt.show()
	
	divideHNum=0
	mi=None
	for divideHNum in range(2**(h-1)):
		divideH=np.empty(h+1, np.bool)
		for hi in range(h): divideH[hi+1]=divideHNum & (2**hi)
		divideH[0]=True
		divideH[-1]=True
# 		print("divideH", divideHNum, divideH)
		indexH=np.where(divideH)[0]
		nums=np.empty((len(indexH)-1, w), int32)
		for i,ih in enumerate(indexH[:-1]):
			nums[i]=grid[indexH[i]:indexH[i+1]].sum(axis=0)
		
# 		print(indexH)	
# 		print(nums)
# 		print()
		
		cum=np.cumsum(nums, axis=1)
# 		print(cum)
		
		divideW=0
		divideWSize=0
		prevNext=0
		while divideW<w:
			next=np.where((cum[:,prevNext:]>k).any(axis=0))[0]
# 			print("next",next)
			if len(next)==0: break
			next=next[0]
			if next==0:
				divideWSize=None
				break
			next+=prevNext
			divideWSize+=1
			cum-=cum[:,next-1,None]
			prevNext=next
# 			print("next",next)
# 			print("cum",cum)
# 		print("divideWSize",divideWSize)
# 		print()
		
		if divideWSize is not None:
			divideSize=divideWSize+(len(indexH)-2)
			if mi is None or divideSize<mi: mi=divideSize
		
		divideHNum+=1
		
		
	print(mi)
			
	
		
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, K = map(int, input().split())
S = np.array([list(map(int, list(input()))) for _ in range(H)])
ans = H*W
B = np.zeros((H,W))
for i in range(H):
  for j in range(W):
    B[i][j] = np.sum(S[:i+1, :j+1])
  for i in range(1 << H-1):
    cnt = 0
    A = np.zeros((H, W))
    A[0,] = np.cumsum(S[0, ])
    for y in range(1, H):
      if (i >> y-1) % 2 == 1:
        A[y,] = np.cumsum(S[y,])
        cnt += 1
      else:
        A[y,] =  np.cumsum(S[y,]) + A[y-1,]
    if K in A[:, 0]: continue
    for x in range(1, W):
      if K in A[:, x]:
        cnt += 1
        for x2 in range(x,W):
          A[:, x2] -= A[:, x-1]
  ans = min(ans, cnt)
print (ans)

Submission status: Wrong Answer

Solution code:
import itertools
 
H,W,K=map(int, input().split())
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

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

#for x in s: print(x)

c = [[0 for _ in range(w+1)] for _ in range(h+1)]

for i in range(1, h+1):
    temp = 0
    for j, x in enumerate(s[i]):
        temp += x
        c[i][j] = c[i-1][j] + temp

#for x in c: print(x)

ans = float('inf')
mb = 1 << (h-1)
for i in range(1 << (h-1)):
    b = list(map(int, list(reversed(bin(mb + i)[2:]))))
    #print(b)
    temp = sum(b) - 1
    L = 0
    for R in range(1, w+1):
        U = 0
        for D in range(1, h+1):
            if b[D-1] == 1:
                if c[D][R] - c[U][R] - c[D][L] + c[U][L] > k:
                    #print(c[D][R] - c[U][R] - c[D][L] + c[U][L], U, D, R, L)
                    temp += 1
                    L = R - 1
                    break
                U = D
    ans = min(ans, temp)

print(ans)

Submission status: Wrong Answer

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

num = 0
for s_sub in s_list:
    num += s_sub.count('1')

count = 0
while num > k:
    num = (num+1)//2
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

nnn = 0
for i in range(H):
  for j in range(W):
    nnn += int(a[i][j])
else:
  if nnn <= K:
    print(0)
    exit()

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])

ans = MAX_INT
for x in range(1<<H): # 1がたっている数
  l = 0
  num = 0
  for k in range(H-1):
    if (x >> k) & 1 == (x >> k+1) & 1:
      continue
    else: # 割る
      num += 1
  
  for w in range(W):
    # 1行で割れるか判定
    judge = 0
    f = 0
    for h in range(H):
      if (x >> h) & 1 == f: # 割らない 同じ
        judge += int(a[h][w])
      else: # 割る
        judge = 0
        judge += int(a[h][w])
        f = (x >> h) & 1
      if judge > K:
        break
    else:
      continue
    break
  else:
    for w in range(W):
      f = 0
      cnt = 0
      for h in range(H):
        if (x >> h) & 1 == f: # 割らない 同じ
          cnt += rui[h][w+1] - rui[h][l]
        else: # 割る
          cnt = 0
          cnt += rui[h][w+1] - rui[h][l]
          f = (x >> j) & 1
        if cnt > K:
          num += 1
          l = w
          break
    else:
      ans = min(ans, num)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = float('inf')
    for i in range(2 ** (H - 1)):
        group = 0
        h_id = [0] * H
        for j in range(H):
            h_id[j] = group
            if i >> j & 1:
                group += 1
        
        group += 1
        c = [[0] * W for _ in range(group)]
        for h in range(H):
            for w in range(W):
                c[h_id[h]][w] += S[h][w]
        g_flag = True
        for g in range(group):
            for w in range(W):
                if c[g][w] > K:
                    g_flag = False

        if not g_flag:
            continue

        cnt = group - 1
        now = [0] * group
        flag = True
        for w in range(W):
            for g in range(group):
                now[g] += c[g][w]
                if now[g] > K:
                    flag = False
                    cnt += 1
            
            if not flag:
                for g in range(group):
                    now[g] = c[g][w]
                flag = True
        ans = min(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# 解説見た

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

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    ans = min(num_cut, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = float('inf')
    for i in range(2 ** (H - 1)):
        group = 0
        h_id = [0] * H
        for j in range(H):
            h_id[j] = group
            if i >> j & 1:
                group += 1
        
        group += 1
        c = [[0] * W for _ in range(group)]
        for h in range(H):
            for w in range(W):
                c[h_id[h]][w] += S[h][w]

        for g in range(group):
            for w in range(W):
                if c[g][w] > K:
                    continue

        cnt = group - 1
        now = [0] * group
        flag = True
        for w in range(W):
            for g in range(group):
                now[g] += c[g][w]
                if now[g] > K:
                    flag = False
                    cnt += 1
            
            if not flag:
                for g in range(group):
                    now[g] = c[g][w]
                flag = True
        ans = min(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


# 解説見た

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

# 全部のカットを試す
ans = 10 ** 5
for h in range(2 ** (H - 1)):

    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            cnt = tmp_cnt
            num_cut += 1
        else:
            cnt = new_cnt

    ans = min(num_cut, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
#input = sys.stdin.buffer.readline
 
def main():
    H,W,K = map(int,input().split())
    a = [list(input()) for _ in range(H)]
    
    for i in range(H):
        for j in range(W):
            a[i][j] = int(a[i][j])
    
    ans = 10**6
    for i in range(1<<H-1):
        cut,count = [-1],0
        for j in range(H-1):
            if (i>>j)&1 != 0:
                count += 1
                cut.append(j)
        cut.append(H-1)
        l = len(cut)-1
        use = [[0 for _ in range(W)] for _ in range(l)]
        for x in range(l):
            up,down = cut[x],cut[x+1]
            for y in range(up+1,down+1):
                for z in range(W):
                    use[x][z] += a[y][z]

        right,bl,yorn = 0,[0 for _ in range(l)],True
        while right < W:
            st = [0 for _ in range(l)]
            for x in range(l):
                st[x] += use[x][right]
            if max(st) > K:
                yorn = False
                break
            else:
                for x in range(l):
                    bl[x] += st[x]
                    if bl[x] > K:
                        count += 1
                        bl = st
                right += 1
        if yorn:
            ans = min(ans,count)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
if w==1:
    ans = 0
    for i in range(h):
        ans+=ma[i][0]
    print((ans-1)//k)
    exit()
ls = []
for i in range(2**(h-1)):
    l = []
    for j in range(h-1):
        if (i>>j & 1):
            l.append(j)
    ls.append(l)
ans = [len(l) for l in ls]

for m in range(len(ls)):
    l = ls[m]
    n = len(l)+1
    cnt = [0]*n

    for i in range(w):
        tp = [0]*n #一時的な配列を保存
        idx = 0 #indexの初期化
        #jがdev以下のものを一つのindexにまとめる
        if n== 1:
            dev = h
        else:
            dev = l[0]
        for j in range(h):
            if j <= dev:
                pass
            else:
                idx +=1
                if idx ==n-1:
                    dev = h  # len(l) == n-1 ->n-1は溢れる
                else:
                    dev = l[idx]
            cnt[idx] += ma[j][i]
            tp[idx] += ma[j][i]
        if max(cnt) >k:
            ans[m] +=1
            cnt = tp
print(min(ans))

Submission status: Wrong Answer

Solution code:
h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
ls = []
for i in range(2**(h-1)):
    l = []
    for j in range(h-1):
        if (i>>j & 1):
            l.append(j)
    ls.append(l)
ans = [len(l) for l in ls]

for m in range(len(ls)):
    l = ls[m]
    n = len(l)+1
    cnt = [0]*n

    for i in range(w):
        tp = [0]*n #一時的な配列を保存
        idx = 0 #indexの初期化
        #jがdev以下のものを一つのindexにまとめる
        if n== 1:
            dev = h
        else:
            dev = l[0]
        for j in range(h):
            if j <= dev:
                pass
            else:
                idx +=1
                if idx ==n-1:
                    dev = h  # len(l) == n-1 ->n-1は溢れる
                else:
                    dev = l[idx]
            cnt[idx] += ma[j][i]
            tp[idx] += ma[j][i]
        if max(cnt) >k:
            ans[m] +=1
            cnt = tp
print(min(ans))

Submission status: Wrong Answer

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)]
  
def foo(L):#L : Cutting-List
  res = 0
  temp = [0 for i in range(len(L))]
  for w in range(W):# Do Cut at w in [W] ?
    #Count '1' on each block at w-th column.
    r = [0 for i in range(len(L))]
    for i in range(len(L)):
      x = L[i][0]
      y = L[i][1]
      for j in range(x,y+1):
      # [x-y]
        r[i] += int(S[j][w])
    
    for i in range(len(L)):
      if r[i] > K:
        return H + W + 1;
      elif temp[i] + r[i] > K:
        res += 1
        temp = r.copy()
      else:
        temp[i] += r[i]
  return res

ans = H+W+1

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

ans = INF
for x in product([0, 1], repeat=H-1):
	cut = sum(x)
	if any(x):
		lis = np.zeros((H, W+1))
		tmp_lis = np.zeros((W))
		idx = 0
		for i, n in enumerate(x):
			tmp_lis += S[i]
			if n:
				lis[idx][1:] += tmp_lis
				idx += 1
				tmp_lis = np.zeros((W))
				
		if H >= 2:
			tmp_lis += S[-1]
			lis[idx][1:] += tmp_lis
		if (lis>K).sum():
			continue
		lis = lis.cumsum(axis=1)
	else:
		lis = np.sum(S, axis=0)
		tmp = 0
		for n in lis:
			if n > K:
				cut = INF
				break
			tmp += n
			if tmp > K:
				cut += 1
				tmp = n
		ans = min(ans, cut)
		continue
	idxs = []
	idx = 0
	while idx != W+1:
		for i in range(len(lis)):
			for j in range(idx, W+1):
				if lis[i][j]-lis[i][idx] >= K:  # 1番最初にKを超えるところを探す
					idxs.append(j)
		if not idxs:  # 超えない
			break
		idx = min(idxs)
		idxs = []
		cut += 1
	ans = min(ans, cut-1)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K=map(int,input().split())
import numpy as np
S=np.array([list(map(int,list(input()))) for i in range(H)])
ans=10**18
for i in range(2**(H-1)):
  _ans=0
  X=[]
  start=0
  j=0
  while j<H:
    if i & 1:
      X.append(np.sum(S[start:j+1,:],axis=0))
      start=j+1
      j+=1
      i>>=1
      _ans+=1
    else:
      j+=1
      i>>=1
  X.append(np.sum(S[start:,:],axis=0))
  X=np.cumsum(X,axis=-1)
  X=np.vstack((X,[0]*X.shape[-1]))
  #print(X)
  for i in range(W):
    if max(X[:,i])<=K:
      continue
    else:
      if i==0:
        break
        _ans=10**18
      _ans+=1
      #X=X-X[:,i].Tnp.transpose
      X=X-np.reshape(X[:,i-1],(-1,1))
      #print(X)
  ans=min(ans,_ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])
    #行ごと指定できるのが良い

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    #print(cnt)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        #(H-1)にしたのはｔにあわせるため
        #print(lst
        #th=1:切ってる、th=0、切ってない
        if t[h]:
            lst.append(S[h + 1])
            #一つしたの段の要素をリストごと足していることで後で網羅
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
            #既存の最後の要素に一つ下の段の要素を足している
        #print(lst)
    L = len(lst)
    print(L)
    sum_lst = [0] * L
    #とりあえずゼロ配列作るプラス要素数を可変にする
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
            #どれか一行でも超えたらあうと
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1 #前と一緒で合計超えてた場合は切る、切った回数を１足す
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp #合計リストをW回使いまわす#前から切ってない場合の分も足し合わせる
    else:
        ans = min(ans, cnt)
        #アンサーを最小化したら更新する
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

divide = list(itertools.product([0, 1], repeat=h-1))

MIN = 10**10
for d in divide:
    SUM = [0]*(sum(d)+1)
    ans = 0
    frag=True
    reset=False
    ok=True

    for i in range(w):
        #start
        now = 0
        for g in range(h-1):
            if d[g] == 0:
                if s[g][i] == '1':
                    SUM[now] += 1

            elif d[g] == 1:
                if s[g][i] == '1':
                    SUM[now] += 1
                now += 1
        if s[-1][i] == '1':
            SUM[-1] += 1
        #end
        
        for l in SUM:
            if l>k:
                reset=True
                break
        
        if reset and frag:
            ok=False
            break
        elif reset and frag is False:
            frag=True
            reset=False
            ans+=1
            SUM = [0]*(sum(d)+1)
            #start
            now = 0
            for g in range(h-1):
                if d[g] == 0:
                    if s[g][i] == '1':
                        SUM[now] += 1

                elif d[g] == 1:
                    if s[g][i] == '1':
                        SUM[now] += 1
                    now += 1
            if s[-1][i] == '1':
                SUM[-1] += 1
            #end
        else:
            frag=False
    if ok:
        MIN=min(MIN,ans+sum(d))
print(MIN)

Submission status: Wrong Answer

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 x in range(W):
      # Check Greedy;
      r = 0
      for h in range(i, j+1):
        r += int(S[h][x])
      if r > K:
        A[i][j]  += H + W + 1;
      elif temp + r > K:
        A[i][j] += 1
        temp = r
      else:
        temp += r
    #print(i, j, A[i][j])
  
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 now % 2 == 1:
      m += A[s][i] + 1
      s = i+1
    now //= 2
  ans = min(ans, m + A[s][H-1])

print(ans)

Submission status: Wrong Answer

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 = []
    lst1 = [0]*w

    for k in range(w): #分割数はn-1なので、最初の1行目は手動で
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": #分割しない
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)
    flag = 0
    #横分割しなかった部分について、縦分割することで必ず条件を満たせる必要がある。
    for j in res:
        if any(k > g for k in j):
            flag = 1
            break
    if flag:
        continue

    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        for l in count:
            if g < l:
                count = now_count
                w_cut += 1
                continue

    ans = min(ans,blst[i].count("1")+w_cut)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,list(input().split(" ")))
choco=np.empty((H,W))
for i in range(H):
    choco[i]=list(map(int,input()))
V=np.inf
for i in range(2**(H-1)):
    m=0
    num=bin(i)
    sp=[]
    for j in range(1,len(num)-1):
        if num[-j]=="1":
            sp.append(j)
            m+=1
    choco2=choco.copy()
    spmat=np.split(choco2,sp)
    for spline in range(1,W):
        sumlist1=np.array([np.sum(spmat[k][:,:spline]) for k in range(len(spmat))])
        sumlist2=sumlist1+np.array([np.sum(spmat[k][:,spline]) for k in range(len(spmat))])
        if np.all(sumlist1<=K):
            if spline+1<W-1 and np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
            if spline==W-1:
                if np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
                else:
                    choco2[:,:spline+1]=0
        if V<m:
            break
            
    T=True
    for k in range(len(spmat)):
        if np.sum(spmat[k])>K:
            T=False
    if T:
        V=min(V,m)
print(V)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

ans = INF
for x in product([0, 1], repeat=H-1):
	cut = sum(x)
	if any(x):
		lis = np.zeros((H, W+1))
		tmp_lis = np.zeros((W))
		idx = 0
		for i, n in enumerate(x):
			tmp_lis += S[i]
			if n:
				lis[idx][1:] += tmp_lis
				idx += 1
				tmp_lis = np.zeros((W))
				
		if H >= 2:
			tmp_lis += S[-1]
			lis[idx][1:] += tmp_lis
		lis = lis.cumsum(axis=1)
	else:
		lis = np.array(np.sum(S, axis=0))
		tmp = 0
		for n in lis:
			tmp += n
			if tmp > K:
				cut += 1
				tmp = n
		ans = min(ans, cut)
		continue
	idxs = []
	idx = 0
	while 1:
		for i in range(len(lis)):
			for j in range(idx, W+1):
				if lis[i][j]-lis[i][idx] > K:  # 1番最初にKを超えるところを探す
					idxs.append(j)
		if not idxs:  # 超えない
			break
		idx = min(idxs)
		idxs = []
		cut += 1
	ans = min(ans, cut)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,list(input().split(" ")))
choco=np.empty((H,W))
for i in range(H):
    choco[i]=list(map(int,input()))
V=np.inf
for i in range(2**(H-1)):
    m=0
    num=bin(i)
    sp=[]
    for j in range(1,len(num)-1):
        if num[-j]=="1":
            sp.append(j)
            m+=1
    choco2=choco.copy()
    spmat=np.split(choco2,sp)
    for spline in range(1,W):
        sumlist1=np.array([np.sum(spmat[k][:,:spline]) for k in range(len(spmat))])
        sumlist2=np.array([np.sum(spmat[k][:,:spline+1]) for k in range(len(spmat))])
        if np.all(sumlist1<=K):
            if spline+1<W-1 and np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
            if spline==W-1:
                if np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
                else:
                    choco2[:,:spline+1]=0
        if V<m:
            break
            
    T=True
    for k in range(len(spmat)):
        if np.sum(spmat[k])>K:
            T=False
    if T:
        V=min(V,m)
print(V)

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K=map(int,list(input().split(" ")))
choco=np.empty((H,W))
for i in range(H):
    choco[i]=list(map(int,input()))
V=np.inf
for i in range(2**(H-1)):
    m=0
    num=bin(i)
    sp=[]
    for j in range(1,len(num)-1):
        if num[-j]=="1":
            sp.append(j)
            m+=1
    choco2=choco.copy()
    spmat=np.split(choco2,sp)
    for spline in range(1,W):
        sumlist1=np.array([np.sum(spmat[k][:,:spline]) for k in range(len(spmat))])
        sumlist2=np.array([np.sum(spmat[k][:,:spline+1]) for k in range(len(spmat))])
        if np.all(sumlist1<=K):
            if spline+1<W-1 and np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
            if spline==W-1:
                if np.any(sumlist2>K):
                    choco2[:,:spline]=0
                    m+=1
                else:
                    choco2[:,:spline+1]=0
            
    T=True
    for k in range(len(spmat)):
        if np.sum(spmat[k])>K:
            T=False
    if T:
        V=min(V,m)
print(V)

Submission status: Wrong Answer

Solution code:
r=range
h,*s=open(0)
h,w,k=map(int,h.split())
m=9e9
for i in r(1<<h-1):
  t,v,l=[],-1,1
  for j in r(h):
    if i>>j&1:
      t+=j+1,
      l+=1
  t+=h,
  c=[0]*l
  for i in r(w):
    b=f=0
    u=[]
    for j in r(l):
      d,b=sum(s[j][i]>'0'for j in r(b,t[j])),t[j]
      u+=d,
      c[j]+=d
      f|=c[j]>k
    v+=f
    if f:c=u
  m=min(m,v+l)
print(m)