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
h,w,k = map(int,input().split())
if k > h:
    print(0)
    exit()
h_conv = []
for i in range(2**(h-1)):
    h_conv.append(bin(i)[2::].zfill(h-1))
choco = []
for i in range(h):
    choco.append(list(map(int,input())))
choco_num = numpy.zeros([h,w])
choco_num[0] = numpy.cumsum(choco[0])
cnt = choco_num[0][0]
for i in range(1, h):
    if choco[i][0] == 1:
        cnt += 1
    choco_num[i][0] = cnt
for i in range(1,h):
    for j in range(1, w):
        if choco[i][j] == 1:
            choco_num[i][j] = choco_num[i-1][j] + choco_num[i][j-1] - choco_num[i-1][j-1] + 1
        else:
            choco_num[i][j] = choco_num[i - 1][j] + choco_num[i][j - 1] - choco_num[i - 1][j - 1]
ans = 0
for i in range(len(h_conv)):
    cnt = 0
    cutting = []
    for j in range(h-1):
        if h_conv[i][j] == "1":
            cnt += 1
            cutting.append(j)
    cutting.append(h-1)
    cut_w = -1
    for j in range(w):
        prev = 0
        for l in cutting:
            if cut_w == -1:
                focus = choco_num[l][j] - choco_num[l][cut_w]
            else:
                focus = choco_num[l][j] - choco_num[l][cut_w]
            if focus - prev > k:
                cnt += 1
                cut_w = l
            prev = focus
        ans = max(ans,cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
def chk(area):
    num=0
    l=len(area)
    cnt=[0 for _ in range(l)]

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            if i>0: num+=1
            cnt=[0 for _ in range(l)]
            for j in range(l):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

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

area=[0 for i in range(h)]
ans=10**10

for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
from itertools import product
H, W, K = map(int, input().split())
A = np.array([list(input()) for _ in range(H)], dtype=int)
np.cumsum(A, out=A, axis=0)
np.cumsum(A, out=A, axis=1)

ans = 10**9
for split in product(range(2), repeat=H - 1):
    cut = sum(split)
    accum = np.zeros(W, dtype=int)
    row = []
    for i, p in enumerate(split):
        if p == 0:
            continue
        row.append(A[i]-accum)
        accum = A[i]
    else:
        row.append(A[-1] - accum)

    tmp = np.zeros(W, dtype=int)
    for r in row:
        tmp = np.maximum(tmp, r)
    tmp = tmp.tolist()

    cnt = 0
    target = K
    p = 0
    while True:
        q = bisect.bisect_right(tmp, target)
        if q == W:
            break
        if p == q:
            cnt = -1
            break
        p = q
        target = tmp[p-1]+K
        cnt += 1

    if cnt < 0:
        continue
    ans = min(ans, cut + cnt)


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] - 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:
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):
    if ptn == 0:
        return [0], [H]
    us = list()
    bs = list()
    u = 0
    for h in range(H):
        if ptn & 0x1 == 0x1:
            us.append(u)
            bs.append(h+1)
            u = h + 1
        ptn >>= 1
    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
    
    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:
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: 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 L66 in L9:
    nc = len(L66[0])
    wh = 0
    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
    ans=min(wh,ans)
print(wh)

Submission status: Wrong Answer

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=0)).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: Wrong Answer

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


# white choco

cum = [[0 for i in range(W + 1)] for i in range(H + 1)]
for y in range(H):
    for x in range(W):
        cum[y + 1][x + 1] = cum[y][x + 1] + cum[y + 1][x] - cum[y][x] + int(s[y][x])

def get(x1, y1, x2, y2):
    # x1 += 1
    # y1 += 1
    # x2 += 1
    # y2 += 1
    return cum[y2][x2] - cum[y2][x1] - cum[y1][x2] + cum[y1][x1]

# for y in range(H + 1):
#     print([get(0, 0, x, y) for x in range(W + 1)])


ans = 1e50


def try_ptn(yptn):
    tans = len(yptn)
    yptn += [H]
    # print(yptn)
    bx = 0
    # (bx,x]が可能かどうか　bxは前回の切断ポイント不可能ならbx=xとして次は
    x = 1
    while x <= W:
        by = 0
        # (by,y]
        for y in yptn:
            # print(bx, by, x, y, get(bx, by, x, y))

            if get(bx, by, x, y) > K:
                # print('over :get=', get(bx, by, x, y))
                # 1列だけすらだめ
                if x == bx:
                    return 1e50
                # xで割る
                bx = x - 1
                tans += 1
                break
            by = y
        # else:
        x += 1

    return tans

for b in range((H - 1) ** 2):
    # yとy+1のとこで割る for y in yptn
    # (by,y]を求める
    yptn = [i + 1 for i in range(H - 1) if b & 1 << i]
    tans = try_ptn(yptn)
    # print(tans)
    ans = min(ans, tans)
print(ans)

Submission status: Wrong Answer

Solution code:
def chk(area):
    num=0
    l=len(area)
    cnt=[0 for _ in range(l)]

    for i in range(w):
        for j in range(h):
            cnt[area[j]]+=choko[i][j]

        if max(cnt)>k:
            if i>0: num+=1
            cnt=[0 for _ in range(l)]
            for j in range(h):
                cnt[area[j]]+=choko[i][j]
            if max(cnt)>k: return 10**10

    return num

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

area=[0 for i in range(h)]
ans=10**10

for v in range(0,2**(h-1)):
    p=bin(v)[2:].zfill(h-1)
    for i in range(h-1):
        if p[i]=="1": area[i+1]=area[i]+1

    tmp1=sum([int(p[i]) for i in range(h-1)])+chk(area)
    ans=min(ans,tmp1)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys


def input():
    return sys.stdin.readline()[:-1]

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

def count(s):
    H, W = s.shape[0], s.shape[1]
    ver = [0]*H
    hor = [0]*W
    for h in range(H):
        tmp =0
        for w in range(W):
            if s[h][w]==1:
                tmp+=1
        ver[h]=tmp

    for w in range(W):
        tmp = 0
        for h in range(H):
            if s[h][w]==1:
                tmp += 1
        hor[w]=tmp
    return ver, hor


ver, hor = count(s)
tmp = 0
cnt = 0
flag = True
while (sum(hor)>K and sum(ver)>K):
    for i in range(1, len(ver)):
        if (tmp + ver[i] <= K):
            tmp+=ver[i]
        else:
            s = s[i+1:, :]
            cnt += 1
            flag = False
            break
    if flag:
        for i in range(1, len(hor)):
            if (tmp + hor[i] <= K):
                tmp+=hor[i]
            else:
                s = s[:, i+1]
                cnt += 1
                break
    ver, hor = count(s)
print(cnt+1)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
import bisect
from operator import itemgetter
 
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):
    if a[i][j] == "1":
      nnn += 1
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]
    if a[i][j] == "0":
      rui[i][j+1] += 1

ans = MAX_INT
for i in range(1,H): # 1がたっている数
  n = (1 << i) - 1
  while n < (1 << H):
    x = n

    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
      for k in range(H):
        if a[k][w] == "1":
          judge += 1
      else:
        if judge > K:
          break

      f = 0
      cnt = 0
      for j in range(H):
        if (x >> j) & 1 == f: # 割らない 同じ
          cnt += rui[j][w+1] - rui[j][l+1] + int(a[j][w])
        else: # 割る
          cnt = 0
          cnt += rui[j][w+1] - rui[j][l+1] + int(a[j][w])
          f = 1
        if cnt >= K:
          num += 1
          l = w-1
    else:
      ans = min(ans, num)

    x = n & -n
    y = n + x
    n = ((n & ~y) // x >> 1) | y

print(ans)

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
            total[l] += tmp
            # print(total)
        if flag:
            break
        for m in total:
            if m > K:
                cnt += 1
                total = tmp_list
            elif m == K:
                cnt += 1
                total = [0]*len(new_s)
            else:
                pass
    ans = min(ans, cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
h,w,k=map(int,input().split())
s=[list(map(int,list(input()))) for i in range(h)]
s=np.array(s)
#print(s)
#print(np.sum(s,axis=0))
aaa=[]
for i in range(2**(h-1)):
  a=list(bin(i)[2:].zfill(h-1))
  #print(a)
  ss=[s[:1][0].tolist()]
  for j in range(h-1):
    if a[j]=='0':
      ss[-1]=np.sum(ss[-1]+s[j+1:j+2],axis=0).tolist()
    else:
      ss.append(s[j+1:j+2][0].tolist())
  #print(ss)
  n=len(ss)
  #print(n)
  tmp=[0]*n
  ans=0
  for x in range(w):
    for j in range(n):
      tmp[j]+=ss[j][x]
      #print(tmp,tmp[j])
      if tmp[j]>k:
        ans+=1
        tmp=[0]*n
        tmp[j]=ss[j][x]
        
  #print('ans',ans+sum(list(map(int,a))))
  aaa+=[ans+sum(list(map(int,a)))]
print(min(aaa))

Submission status: Wrong Answer

Solution code:
h,w,k = map(int, input().split())
grid = []
acc = [[0 for i in range(w+2)]]
d = {'0':0, '1':1}
row = [0] * h
col = [0] * w
for i in range(h):
    s = input()
    grid.append([])
    acc.append([0])
    for j,c in enumerate(map(d.get, s)):
        row[i] += c
        col[j] += c
        grid[i].append(c)
        acc[i+1].append(c)
acc.append([0 for i in range(w+2)])
ddd = sum(row)
cnt = 0
po = 2
ans = (ddd + k) // k
tmp = [1,1]
if ddd <= k:
    print(0)
    exit()
while ans > tmp[0] * tmp[1]:
    if tmp[0] > tmp[1]:
        tmp[1] += 1
    else:
        tmp[0] += 1
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
h,w,k=map(int,input().split())
s=[list(input()) for i in range(h)]
print(h-1)

Submission status: Wrong Answer

Solution code:
class Acc2D:
    def __init__(self, a):
        h, w = len(a), len(a[0])
        self.acc2D = self._build(h, w, a)

    def _build(self, h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + a[r][c]
                # 末項は必要に応じて改変すること
        return ret

    def get(self, r1, r2, c1, c2):
        # [r1,r2), [c1,c2) : 0-indexed
        if r1 >= r2 or c1 >= c2:
            return 0
        acc2D = self.acc2D
        return acc2D[r2][c2] - acc2D[r1][c2] - acc2D[r2][c1] + acc2D[r1][c1]


def main():
    from itertools import combinations

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

    tot = 0
    s = []
    for _ in range(H):
        *row, = map(int, input())
        tot += row.count(1)
        s.append(row)

    acc2D = Acc2D(s)
    # usage: acc2D.get(r1,r2,c1,c2)
    # 個数の二次元累積和

    if tot <= K:
        print(0)
        return

    ret = 0
    pc = 0
    for c in range(W + 1):  # 新しい区画の開始列
        a = acc2D.get(0, H, pc, c)
        if a > K:
            if pc == c - 1:
                ret = H * W
                break
            pc = c - 1
            ret += 1

    for row_cut in range(H - 2):
        for comb in combinations(range(1, H - 1), r=row_cut):
            tc = tuple(comb)
            t = len(tc)

            rs = (0,) + tc + (H,)
            pc = 0
            cc = 0
            while cc < W:
                for r1, r2 in zip(rs, rs[1:]):
                    a = acc2D.get(r1, r2, pc, cc + 1)
                    if a > K:
                        if pc > cc:
                            break
                        else:
                            pc = cc
                            t += 1
                else:
                    cc += 1
                    continue
                break
            else:
                ret = min(ret, t)

    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Wrong Answer

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

mat=[]
for i in range(H):
  array=[int(x) for x in input()]
  mat.append(array)
#print(mat)

wmat=mat.copy()
for i in range(H):
  for j in range(1,W):
    if mat[i][j]==0:
      wmat[i][j]=wmat[i][j-1]
    else:
      wmat[i][j]=wmat[i][j-1]+1
#print(wmat)
      
rmat=wmat.copy()
for i in range(1,H):
  for j in range(W):
    rmat[i][j]=wmat[i][j]+wmat[i-1][j]
#print(rmat)

i,j=0,0
while(True):
  if j<W-1 and rmat[i][j+1]<=K:
    j+=1
  else:
    break
while(True):
  if i<H-1 and rmat[i+1][j]<=K:
    i+=1
  else:
    break
    
#print(i,j)
print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys

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

c_w = [sum(c == '1' for c in s) for s in S]
total = sum(c_w)

if total == 0:
  print(0)
  sys.exit()

while 0 in c_w:
  i = c_w.index(0)
  del S[i]
  del c_w[i]

c_h = [sum(s[i] == '1' for s in S) for i in range(W)]

while 0 in c_h:
  i = c_h.index(0)
  S = [s[:i] + s[i+1:] for s in S]
  del c_h[i]

answer = H * W
for x in range(1, 10):
  DS = defaultdict(list)
  DC = defaultdict(int)
  i = 0
  t = 0
  ans = x - 1
  for s, c in zip(S, c_w):
    if t + c > total // x:
      i += 1
      t = 0
    DS[i].append(s)
  for j in range(len(S[0])):
    if any(DC[k] + sum(s[j] == '1' for s in s_list) > K for k, s_list in DS.items()):
      ans += 1
      DC = defaultdict(int)
    for k, s_list in DS.items():
      DC[k] += sum(s[j] == '1' for s in s_list)
  answer = min(answer, ans)

print(answer)

Submission status: Wrong Answer

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

white = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if i != 0:
            white[i][j] += white[i-1][j]
        if j != 0:
            white[i][j] += white[i][j-1]
        if i != 0 and j != 0:
            white[i][j] -= white[i-1][j-1]
        white[i][j] += choco[i][j]
ans = float('inf')
for i in range(2**(h-1)): #横に切る位置をbitでもつ
    temp = format(i,'b').count('1') # 横に何かいきるか
    hw = []#h == どこの下で切るか
    j = i
    cnt = 0
    while j >0:
        if j&1:
            hw.append(cnt)
        cnt += 1
        j = j >> 1
    hw.append(h-1)
    now = -1
    #if w == 1:
    flag = True
    for l in range(len(hw)):
        if l == 0:
            if white[hw[l]][0] > k:
                flag = False
                break
        else:
            if white[hw[l]][0] - white[hw[l-1]][0] > k:
                flag = False
                break
    if not flag:
        continue
    else:
        ans = min(ans,temp)
        continue
    for j in range(w-1):
        flag = True
        if now == -1:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l-1]][j+1] > k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
        else:
            for l in range(len(hw)):
                if l == 0:
                    if white[hw[l]][j+1] - white[hw[l]][now] > k:
                        flag = False
                        break
                else:
                    if white[hw[l]][j+1] - white[hw[l]][now] - white[hw[l-1]][j+1] + white[hw[l-1]][now]> k:
                        flag = False
                        break
            if not flag:
                now = j
                temp += 1
    ans = min(ans,temp)
print(ans)

Submission status: Wrong Answer

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

def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    cnt=[[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            flg=int(s[i][j])
            if i==0 and j==0:
                cnt[i][j]=flg
            elif i==0:
                cnt[i][j]=cnt[i][j-1]+flg
            elif j==0:
                cnt[i][j]=cnt[i-1][j]+flg
            else:
                cnt[i][j]=cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]+flg

    def chk(l,x,y):
        ans=0
        for i in range(x):
            a=0
            for j in range(y-1,-1,-1):
                if cnt[x-1][y-1]-cnt[i][j]>k:
                    continue
                else:
                    if j==y:
                        a=1+chk(s[i+1:][0:],x-i-1,y)
                    elif i==x:
                        a=1+chk(s[0:][j+1:],x,y-j-1)
                    else:
                        a=2+chk(s[i+1:][j+1:],x-i-1,y-j-1)+chk(s[i+1:][:j+1],x-i-1,j+1)+chk(s[:i+1][j+1:],i+1,y-j-1)
                    break
            if ans==0:
                ans=a
            else:
                ans=min(ans,a)
        return ans
    
    print(chk(s,h,w))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
H,W,K = list(map(int,input().split()))
# print("H,W,K={},{},{}".format(H,W,K))

S = [0]*H
for i in range(H):
    S[i] = list(map(int,list(input())))
# print(S)
S = np.array(S)
# print(S)
# print(np.sum(S[0:3,0:3]))

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

# n=1
for i in range(1,H):
    # print("i:",i)
    # print(S[:i,:],S[i:,:])
    if np.sum(S[:i,:])<=K and np.sum(S[i:,:])<=K:
        print(1)
        exit()

for i in range(1,W):
    # print("i:",i)
    # print(S[:,:i],S[:,i:])
    if np.sum(S[:,:i])<=K and np.sum(S[:,i:])<=K:
        print(1)
        exit()

# n=2
for i in range(1,H):
    for j in range(1,W):

        if np.sum(S[:i,:i])<=K and np.sum(S[i:,:i])<=K and np.sum(S[:i,i:])<=K and np.sum(S[i:,i:])<=K:
            print(2)
            exit()

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]
    length = 0
    for j in range(n):
        if ((i >> j) & 1):
            horizon.append(j + 1)
            length += 1
    horizon.append(H)
    vertical = 0
    y1 = 0
    for y2 in range(1, W + 1):
        for k in range(length - 1):
            x2 = horizon[k + 1]
            x1 = horizon[k]
            sq = s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
            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:
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)
print(ans)