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 numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    popcnt=lambda bit:bin(bit).count("1")
    h,w,k=MI()
    aa=[[0]+[int(c) for c in SI()] for _ in range(h)]
    aa=np.array(aa)
    for i in range(h):
        aa[i]=np.cumsum(aa[i])
    #print(aa)
    ans=h+w
    for bit in range(1<<(h-1)):
        s=aa[0].copy()
        sn=popcnt(bit)+1
        ss=np.zeros((sn,w+1),dtype="i8")
        si=0
        for i in range(1,h):
            if bit>>(i-1)&1:
                ss[si]=s
                s=aa[i].copy()
                si+=1
            else:s+=aa[i]
        ss[si]=s
        #print(bin(bit))
        #print(ss)
        #print()
        cnt=popcnt(bit)-1
        j=0
        while j<w:
            cnt+=1
            mn=100
            for i in range(sn):
                nj=np.searchsorted(ss[i],ss[i][j]+k,side="right")-1
                mn=min(mn,nj)
            if mn==j:
                cnt=10**9
                break
            j=mn
        ans=min(ans,cnt)
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
#a...入力されたチョコレート
#b...bit全探索用の文字列
#c...そのブロックの中で何個ホワイトチョコレートがあったか
#d...そのbitで何回縦割りを行ったか
#e...出力用変数(その時点での最小分割数を保持)
#f...ホワイトチョコレートに当たった時に、cのどの横割りに格納すればよいか(累積和)
#g...ホワイトチョコレートが許容数を超えた際に1になるフラグ
#h...チョコレートの縦の長さ
#i...何回目のbit全探索か
#j...左から何個目の列を見ているか(正確には見ているはずだったか)
#k...上から何個目の行を見ているか
#l...何回巻き戻したか(ホワイトチョコレートがあふれて、一個前から数えなおした回数)
#w...チョコレートの横の長さ
#z...ホワイトチョコレートの許容数

#fを作るための累積和の定義

def Csum(a):
    b,c=[0],0
    for i in range(len(a)):
        c+=int(a[i])
        b.append(c)
    return b

#入力の受け取り・変数の初期化

h,w,z=map(int,input().split())
a=[]
e=10000
g=0
l=0
for i in range(h):
    a.append(list(input()))

#bit全探索

for i in range(2**(h-1)):
    #変数のリセット
    b=(h-len(bin(i)[2:-1]+bin(i)[-1])-1)*'0'+bin(i)[2:-1]+bin(i)[-1]
    f=Csum(b)
    c=[0]*h
    d=0
    l=0
    j=0
    #巻き戻しの回数+横幅の回数だけ処理を行う
    while j<w+l:
        #巻き戻りフラグの確認
        if g==1:
            #切ったのでホワイトチョコレートのカウントを0に、巻き戻しのカウントをインクリメントする
            c=[0]*h
            l+=1
            g=0
        #縦に見ていく
        for k in range(h):
            #ホワイトチョコレートだったらカウンタをインクリメント
            if a[k][j-l]=='1':
                c[f[k]]+=1
        #ホワイトチョコレートが許容数をオーバーしていないかすべてのブロックで確認
        for k in range(h):
            #オーバーしていたら縦線を引き、フラグgを1にする
            if c[k]>z:
                d+=1
                g=1
        #while文なのでインクリメント
        j+=1
    #縦割りの数+横割りの数が現在の最小値より少なかったら更新
    e=min(e,d+f[-1])

#最小値を出力
print(e)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import Counter

h, w, k = [int(s) for s in sys.stdin.readline().strip().split()]
s = [''] * h
for i in range(h):
    s[i] = sys.stdin.readline().strip()

# h, w, k = 3, 5, 3
# s = [
#     '11111',
#     '11111',
#     '11111'
# ]


ans = float('inf')
for i in range((h - 1) ** 2):
    colors = [0]
    cur = 0
    cand = 0
    for div in range(h-1):
        if (i >> div) & 1:
            cur += 1
            colors.append(cur)
            cand += 1
        else:
            colors.append(cur)

    impossible = False
    color_count = Counter()
    for j in range(w):
        col_color_count = Counter()
        for row in range(h):
            color = colors[row]
            # print('s', s)
            # print('row', row)
            # print('j', j)
            char = s[row][j]
            if char == '1':
                col_color_count[color] += 1

        has_break = False
        for col in range(cur+1):
            if col_color_count[col] > k:
                impossible = True
                break
            if col_color_count[col] + color_count[col] > k:
                has_break = True
        if impossible:
            break
        if has_break:
            color_count = col_color_count
            cand += 1
        else:
            for col in range(cur+1):
                color_count[col] += col_color_count[col]
    if not impossible:
        ans = min(ans, cand)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

h, w, k = map(int, input().split())
s = [['0' for i in range(w)] for j in range(h)]

for i in range(h):
  s[i] = input()

cnt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
  cnt[i][0] = int(s[i][0]) + (0 if i == 0 else cnt[i - 1][0])

for i in range(w):
  cnt[0][i] = int(s[0][i]) + (0 if i == 0 else cnt[0][i - 1])

for i in range(1, h):
  for j in range(1, w):
    cnt[i][j] = cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1] + int(s[i][j])

num = [i for i in range(h - 1)]
ans = 99999
for i in range(0, h):
  for v in itertools.combinations(num, i):
    n = list(v)
    n.append(h - 1)
    
    _ans = i
    _left = -1
    for j in range(w):
      for _k in range(len(n)):
        if cnt[n[_k]][j] - (0 if _left < 0 else cnt[n[_k]][_left]) - (0 if _k == 0 else cnt[n[_k - 1]][j]) + (0 if _left < 0 or _k == 0 else cnt[n[_k - 1]][_left]) > k:
          _left = j
          _ans += 1
          break
    ans = min(ans, _ans)

print(ans)

Submission status: Wrong Answer

Solution code:
from pprint import pprint
from bisect import bisect_left


def read():
    H, W, K = list(map(int, input().strip().split()))
    S = list()
    for i in range(H):
        s = list(map(int, input()))
        S.append(s)
    return H, W, K, S


def cumsum_build(H, W, S):
    c = [[0 for j in range(W+1)] for i in range(H+1)]
    for i in range(H):
        for j in range(W):
            c[i+1][j+1] = S[i][j]
    for i in range(1, H+1):
        for j in range(1, W+1):
            c[i][j] += c[i][j-1] + c[i-1][j] - c[i-1][j-1]
    return c

def cumsum_query(x0, y0, x1, y1, c):
    return c[x1][y1] - c[x0][y1] - c[x1][y0] + c[x0][y0]

def get_ubrange(ptn, H):
    us = [0]
    for h in range(H):
        if ptn & 0x1 == 0x1:
            us.append(h)
        ptn >>= 1
    bs = []
    for i in range(1, len(us)):
        bs.append(us[i])
    bs.append(H)
    return us, bs

def get_lrrange(u, l, b, c, K, W, INF=10000000):
    for r in range(l+1, W+1):
        if cumsum_query(u, l, b, r, c) > K:
            return r-1
    return W

def solve(H, W, K, S, INF=10000000):
    c = cumsum_build(H, W, S)
    ptns = 2 ** (H-1)
    
    min_n_bars = H * W - 2
    for ptn in range(ptns):
        us, bs = get_ubrange(ptn, H)
        n_bars = len(us) - 1
        l = 0
        while True:
            r = W
            for u, b in zip(us, bs):
                r = min(r, get_lrrange(u, l, b, c, K, W))
            if r == W:
                break
            else:
                n_bars += 1
                l = r
        min_n_bars = min(n_bars, min_n_bars)
    return min_n_bars

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = h + w - 2

for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
            else:
                pass
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
#input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  h, w, k = map(int, input().split())
  a = [list(map(int, list(input()))) for i in range(h)]
  gokei = 0
  for i in a:
    gokei += sum(i)
  ans = 0
  while(True):
    if gokei<=k:
      print(gokei)
      break
    else:
      gokei = gokei//2 + gokei%2

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  ones_cum = [0]*len(Sdivs)
  ones = [0]*len(Sdivs)
  mark1,mark2 = False,False
  ws = [0]
  for w in range(1,W+1):
    if mark2 == True:
      #print(mark)
      break
    for i,Sdiv in enumerate(Sdivs):
      #print(w)
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
        ones[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        mark1 = True
        if w-1 == ws[-1]:
          mark2 = True
        ws.append(w-1)
      #print(ones_cum,ws)
    if mark1 == True:
      mark1 = False
      ones_cum = ones
    ones = [0]*len(Sdivs)
  if mark2 == True:
    continue
  cnt += len(ws)-1
  mcnt = min(mcnt,cnt)
print(mcnt)

Submission status: Wrong Answer

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

pattern = []
segs=[]
for i in range(2 ** (h-1)):
    tmp = [False] * (h-1)
    f0=0
    f1=0
    seg=[]
    for j in range(h-1):
        if i >> j & 1:
            tmp[j] = True
            f1 = j+1
            seg.append((f0,f1))
            f0 = f1
    seg.append((f1,h))
    segs.append(seg)
    pattern.append(tmp)
def f(L0,k,wall,w0):
    L=[sum([i[j] for i in L0]) for j in range(w0)]
    c = 0
    w = 0
    print(L)
    for i,l in enumerate(L):
        if i in wall:
            c = 0
        else:
            c += l
            print(c,i)
            if (c > k): 
                wall.append(i-1)
                w += 1
                c = l
            elif (c == k and i != w0-1):
                wall.append(i-1)
                w += 1
                c = 0
    return w, wall
L9=[]
for seg,p in zip(segs,pattern):
    L3=[]
    L4=[[] for _ in range(w)]
    for se in seg:
        L3=[sum([i[j] for i in S[se[0]:se[1]]]) for j in range(w)]
        for i in range(w):
            L4[i].append(L3[i])
    L9.append(L4)
ans=10**10
for seg,L66 in zip(pattern,L9):
    nc = len(L66[0])
    wh = sum(seg)
    count = [0 for _ in range(nc)]
    for i in range(w):
        for j in range(nc):
            count[j] += L66[i][j]
            if count[j] >= k:
                count = [0 for _ in range(nc)]
                wh+=1
            break
    #print(ans,wh,L66)
    ans=min(wh,ans)
print(ans)

Submission status: Wrong Answer

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

s = [[0 for i in range(W+1)] for j in range(H + 1)]
for i in range(H):
    for j in range(W):
        s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + S[i][j]

n = H - 1
ans = 1 << 30
for i in range(2 ** n):
    horizon = [0]
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
    horizon.append(H)
    # hori = 横はどこで割るのか？
    y1 = 0
    y2 = 1
    vertical = 0
    length = len(horizon)
    # print("horizon", horizon)
    while (y2 <= W):
        # print(y1, y2)
        for i in range(length - 1):
            x2 = horizon[i + 1]
            x1 = horizon[i]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            # print(sq, K)
            if (sq > K):
                if (y2 == 1):
                    break
                else:
                    vertical += 1
                    y1 = y2 - 1
        y2 += 1
    ans = min(ans, (vertical) + (length - 2))
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,k = inpl()
s = [input() for i in range(h)]
white = 0
ass = [[0] for i in range(h)]
for i in range(h):
    for j in range(w):
        tmp = 1 if s[i][j] == '1' else 0
        ass[i].append(ass[i][-1] + tmp)
# print(ass)
if w == 1:
    ass = [0]
    for i in range(h):
        tmp = 1 if s[i][j] == '1' else 0
        ass.append(ass[-1] + tmp)
    su = 0
    res = 0
    ind = 0
    for i in range(h):
        su += ass[i+1] - ass[ind]
        if su > k:
            res += 1
            ind = i-1
            su = 0
    print(res)
    quit()
res = INF
for flag in itertools.product([0,1],repeat=h-1):
    cnt = flag.count(1)
    bun = set()
    for i,j in enumerate(flag):
        if j: bun.add(i)
    ind = 0
    for x in range(w):
        lcnt = 0
        for y in range(h):
            lcnt += ass[y][x+1] - ass[y][ind]
            if lcnt > k:
                ind = x
                cnt += 1
                lcnt = 0
                break
            if y in bun: lcnt = 0
    # print(cnt,flag)
    res = min(res,cnt)
print(res)

Submission status: Wrong Answer

Solution code:
H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 10
for i in range(2 ** (H )):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1


    ans = min(cand,ans)
if ruiseki_2d[-1][-1] <= K:
    ans = 0
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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

S = [0]*H
for i in range(H):
  S[i] = input()
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H-1):
  start = 0
  end = 1
  Sdivs=[]
  for a in b:
    if a==1:
      Sdivs.append(S[start:end])
      start = end
    end += 1
  Sdivs.append(S[start:end])
  cnt = sum(b)
  ones_cum = [0]*len(Sdivs)
  ones = [0]*len(Sdivs)
  mark1,mark2 = False,False
  ws = [0]
  for w in range(1,W):
    if mark2 == True:
      #print(mark)
      break
    for i,Sdiv in enumerate(Sdivs):
      #print(w)
      for s in Sdiv:
        ones_cum[i] += s[w-1]=='1'
        ones[i] += s[w-1]=='1'
      if ones_cum[i] > K:
        mark1 = True
        if w-1 == ws[-1]:
          mark2 = True
        ws.append(w-1)
      #print(ones_cum,ws)
    if mark1 == True:
      mark1 = False
      ones_cum = ones
    ones = [0]*len(Sdivs)
  if mark2 == True:
    continue
  cnt += len(ws)-1
  mcnt = min(mcnt,cnt)
print(mcnt)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = 10 ** 18

for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    # print(len(new_s))
    total = [0] * len(new_s)
    # print(new_s)
    for k in range(w):
        flag = 0
        tmp_list = [0]*len(new_s)
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
            elif m == K and k != w - 1:
                cnt += 1
                total = [0]*len(new_s)
            else:
                pass
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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

choco = [list(map(int, list(input()) )) for i in range(h)]

choco_cumsum = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_init = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_init
    w_last_cot_pos = -1

    temp_list = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            temp_list[temp_dict[ih]] += choco[ih][iw]
        # print(iw, temp_list)

        condition = max(temp_list) > k
        if condition:
            if w_last_cot_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cot_pos = iw
                temp_list = [0] * (num_cut_init + 1)
                # print('iw: ', iw, 'last: ', w_last_cot_pos)

            else:
                # 1つしか動かしてない場合は土台無理なので次のh_cutに
                break
        
        else:
            iw += 1
    
    ans = min(ans, num_cut)
    # print(num_cut)

print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret-=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*(w+1) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
    if j==w:
      acum[i][j]=acum[i][j-1]
ans=10**18
for i in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')
  if len(flag)!=(h-1):
    flag='0'*((h-1)-len(flag))+flag
  for j in range((h-1)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  prevx=0
  tmp=len(hlist)-1
  cnt=tmp
  for j in range(w):
    prevy=0
    for l in range(tmp+1):
      if count(prevx,prevy,j,hlist[l])<=k and count(prevx,prevy,j+1,hlist[l])>k:
        cnt+=1
        prevx=j+1
        break
      prevy=hlist[l]+1
  ans=min(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate, combinations

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W, K = MI()
S = [[int(x) for x in list(input())] for _ in range(H)]

# accum[i][j] := i行目のj番目までに現れる1の数(累積和)
# accum = [list()] * H
# for i in range(H):
#     accum[i] = list(accumulate([int(x) for x in list(input())]))


def fn(hdivs):
    hdivs = list(hdivs)
    hdivs.append(H)
    slice = 0

    cnt = [0] * len(hdivs)
    for j in range(W):
        col_cnts = [0] * len(hdivs)
        for h, hdiv in enumerate(hdivs):
            lower = hdivs[h - 1] if h > 0 else 0
            upper = hdiv
            col_cnt = sum(row[j] for row in S[lower:upper])
            if col_cnt > K:
                return -1
            col_cnts[h] = col_cnt
        if not all(cnt[h] + col_cnts[h] <= K for h in range(len(hdivs))):
            slice += 1
            cnt = col_cnts
        else:
            for h in range(len(hdivs)):
                cnt[h] += col_cnts[h]
    return slice

ans = fn(tuple())
for d in range(1, H):
    for hdivs in combinations(range(1, H), d):
        min_slice = fn(hdivs)
        if min_slice > -1:
            ans = min(ans, (len(hdivs)) + min_slice)
print(ans)

Submission status: Wrong Answer

Solution code:
def count(x1,y1,x2,y2):
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret-=acum[y1-1][x1-1]
  return ret

h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*(w+1) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if board[i][j]=='1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]
    if j==w:
      acum[i][j]=acum[i][j-1]
ans=10**18
for i in range(2**(h-1)):
  hlist=[]
  flag=format(i,'b')
  if len(flag)!=(h-1):
    flag='0'*((h-1)-len(flag))+flag
  for j in range((h-1)):
    if flag[j]=='1':
      hlist.append(j)
  hlist.append(h-1)
  prevx=0
  tmp=len(hlist)-1
  cnt=tmp
  for j in range(w):
    prevy=0
    for l in range(tmp+1):
      if count(prevx,prevy,j,hlist[l])<=k and count(prevx,prevy,j+1,hlist[l])>k:
        cnt+=1
        prevx=j+1
        break
      prevy=hlist[l]+1
  ans=min(ans,cnt)
  print(flag,cnt)
print(ans)

Submission status: Wrong Answer

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: Wrong Answer

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

a = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        a[i][j] = int(s[j])

best_result = h * w + 1000

for m in range(2 ** (h - 1)):
    mask = m
    num_splits = 0
    splits = []
    i = 0
    while mask > 0:
        if (mask % 2) == 1:
            num_splits += 1
            splits.append(i)
        i += 1
        mask = mask // 2

    #print('mask = ', m, 'splits = ', splits, 'num_splits =', num_splits)

    counts = [0 for j in range(num_splits + 1)]
    current_counts = [0 for j in range(num_splits + 1)]
    result = num_splits

    for j in range(w):
        if result >= best_result:
            break
        split_index = 0
        success = True
        current_counts[0] = 0

        for i in range(h):
            if a[i][j] == 1:
                counts[split_index] += 1
                if counts[split_index] > k:
                    success = False

            current_counts[split_index] += a[i][j]

            if split_index < num_splits and i == splits[split_index]:
                split_index += 1
                current_counts[split_index] = 0

        if not success:
            result += 1
            #print('not success j = ', j, 'result = ', result, 'counts = ', counts)
            for x in range(num_splits + 1):
                counts[x] = current_counts[x]
            

    best_result = min(best_result, result)

print(best_result)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools
sys.setrecursionlimit(10**7)
#input = sys.stdin.readline
def LI(): return [int(x) for x in sys.stdin.readline().split()]
INF = 10000
MOD = 10**9 + 7
DD = ((1,0),(0,1),(-1,0),(0,-1))
H,W,K = LI()
C = [[int(x) for x in input()] for _ in range(H)]

min_cnt = INF
for y in range(2^H):
    cnt = 0
    bit = 1
    shikiri = [False] * H
    for b in range(H):
        if y & bit:
            shikiri[b] = True     #仕切り
            cnt +=1
        bit = bit << 1
    ct = [0] * H
    x = 0
    bx = 0
    while x < W:
        ix = 0
        for i in range(H):
            ct[ix] += C[i][x]
            if shikiri[i] : ix = i+1
        if max(ct) > K:
            if x != bx:
                cnt += 1
                ct = [0] * H
                bx = x
            else:
                cnt = INF
                break
        else:
            x = x + 1

    min_cnt = min(min_cnt,cnt)
print (min_cnt)

Submission status: Wrong Answer

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

ans = float("inf")

for b in range(2 ** (h - 1)):
  cut = sum(int(c) for c in format(128, "b"))

  w_row = [0] * h
  for j in range(w):
    for i in range(h):
      w_row[i] += s[i][j]

    w_block = 0
    need2cut = False
    hoge = False
    
    for m, c in enumerate("0" + format(b, "b")):
      if c == 1:
        w_block = 0
        hoge = False
      w_block += w_row[m]
      if w_block > k:
        if hoge:
          cut = float("inf")
        need2cut = True
        hoge = True

    if need2cut:
      w_line = [0] * h
      cut += 1

  ans = min(ans, cut)

print(ans)

Submission status: Wrong Answer

Solution code:
H,W,K  =(map(int,input().split(" "))) #  H × W のグリッド
nums = [list(map(int,list(input())))  for  _ in range(H)]
ruiseki_2d = [ [0] * (W + 1)  for _ in range(H + 1) ] # 0 → 0
for w in range(W):
    for h in range(H):
        ruiseki_2d[h + 1][w + 1] =ruiseki_2d[h + 1][w] + ruiseki_2d[h][w + 1] + nums [h ][w]  - ruiseki_2d[h][w]


# Hの分割は決め打ち
# H =10 → 9箇所の分け目
# Wの分割は必要ならする
ans = 10 ** 10
for i in range(2 ** (H - 1)):
    # print(i)
    cand = 0
    # print("pattern {}: ".format(i), end="")
    cuts = [0] #一番端っこでカット
    for j in range(0,H -1 ):  #
        if ((i >> j) & 1):  # j + 1の箇所でHを切る
            # print(i,j + 1)
            cuts.append(j + 1)
            cand += 1
    cuts.append(H)
    beforeW = 0 #個数が変化するのは beforeW からwの区間とwより右の区間
    for w in range(1,W + 1):
        mi = 10 ** 6
        ss = []
        for i in range(len(cuts) - 1): #広げたら超えてしまっていたら、その一個前で線を引く
            y1 = cuts[i]
            y2 = cuts[i + 1]
            x2  = w
            x1 = beforeW
            s = ruiseki_2d[y2][x2] -ruiseki_2d[y2][x1] -ruiseki_2d[y1][x2] +ruiseki_2d[y1][x1]
            ss.append(s)


        ma = max(ss)
        if ma > K :
            cand += 1
            beforeW = w -1


    ans = min(cand,ans)
if ruiseki_2d[-1][-1] <= K:
    ans = 0
print(ans)