Problem:


Score : 1000 points

Problem Statement

Note the unusual memory limit.

For a rectangular grid where each square is painted white or black, we define its complexity as follows:

If all the squares are black or all the squares are white, the complexity is 0.

Otherwise, divide the grid into two subgrids by a line parallel to one of the sides of the grid, and let c_1 and c_2 be the complexities of the subgrids. There can be multiple ways to perform the division, and let m be the minimum value of \max(c_1, c_2) in those divisions. The complexity of the grid is m+1.

You are given a grid with H horizontal rows and W vertical columns where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

Find the complexity of the given grid.

Constraints

1 \leq H,W \leq 185

A_{ij} is # or ..

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the complexity of the given grid.

Sample Input 1

3 3
...
.##
.##

Sample Output 1

2

Let us divide the grid by the boundary line between the first and second columns.
The subgrid consisting of the first column has the complexity of 0, and the subgrid consisting of the second and third columns has the complexity of 1, so the whole grid has the complexity of at most 2.

Sample Input 2

6 7
.####.#
#....#.
#....#.
#....#.
.####.#
#....##

Sample Output 2

4



Sample input:
3 3
...
.##
.##


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[0]*w for _ in [0]*h] for _ in [0]*h] #複雑度、上、下、横
    tate=[[[0]*h for _ in [0]*w] for _ in [0]*w] #複雑度、左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2
        yoko[i][i][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[i][i][j]=cnt
                cnt+=1
            else:
                yoko[i][i][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[i][i][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[i][i][j]=cnt
                cnt+=1
            else:
                tate[i][i][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[i][i][k]
            for j in range(i+1,h):
                if grid[j][k]!=grid[j-1][k]:
                    break
                m=min(yoko[j][j][k],m)
                #print(m) #ここに本来なら来るはず、おかしい
                yoko[i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[i][i][k]
            for j in range(i+1,w):
                if grid[k][j]!=grid[k][j-1]:
                    break
                m=min(tate[j][j][k],m)
                tate[i][j][k]=m
    #y=yoko[0][0][0][0]
    #y=yoko[0][0][1][0]
    #print(y)
    
    #終わるまでやる
    #yoko= #複雑度、上、下、横
    #tate= #複雑度、左、右、縦
    for c in range(1,18):
        #y=yoko[c-1][0][1][0]
        #print(y)
        if yoko[0][h-1][0]==w:
            print(c-1)
            break
        yoko2=[[[0]*w for _ in [0]*h] for _ in [0]*h] #複雑度、上、下、横
        tate2=[[[0]*h for _ in [0]*w] for _ in [0]*w] #複雑度、左、右、縦
        for i in range(h):
            for j in range(i,h):
                for k in range(w):
                    temp=yoko[i][j][k]
                    if temp+k==w:
                        yoko2[i][j][k]=temp
                    else:
                        yoko2[i][j][k]=max(temp+yoko[i][j][k+temp],yoko2[i][j][k])
                    if j!=h-1:
                        temp2=tate[k][k+temp-1][j+1]
                        yoko2[i][j+temp2][k]=max(temp,yoko2[i][j+temp2][k])
        
        for i in range(w):
            for j in range(i,w):
                for k in range(h):
                    temp=tate[i][j][k]
                    if temp+k==h:
                        tate2[i][j][k]=temp
                    else:
                        tate2[i][j][k]=max(temp+tate[i][j][k+temp],tate2[i][j][k])
                    if j!=w-1:
                        temp2=yoko[k][k+temp-1][j+1]
                        tate2[i][j+temp2][k]=max(temp,tate2[i][j+temp2][k])
        yoko=yoko2
        tate=tate2
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w=map(int,input().split())
    grid=[input() for _ in [0]*h]
    yoko=[[[[0]*w for _ in [0]*h] for _ in [0]*h] for _ in [0]*17] #複雑度、上、下、横
    tate=[[[[0]*h for _ in [0]*w] for _ in [0]*w] for _ in [0]*17] #複雑度、左、右、縦
    
    #初期化
    
    for i in range(h):
        cnt=2
        yoko[0][i][i][w-1]=1
        for j in range(w-2,-1,-1):
            if grid[i][j]==grid[i][j+1]:
                yoko[0][i][i][j]=cnt
                cnt+=1
            else:
                yoko[0][i][i][j]=1
                cnt=2
    for i in range(w):
        cnt=2
        tate[0][i][i][h-1]=1
        for j in range(h-2,-1,-1):
            if grid[j+1][i]==grid[j][i]:
                tate[0][i][i][j]=cnt
                cnt+=1
            else:
                tate[0][i][i][j]=1
                cnt=2
    
    for k in range(w):
        for i in range(h-1):
            m=yoko[0][i][i][k]
            for j in range(i+1,h):
                if grid[j][k]!=grid[j-1][k]:
                    break
                m=min(yoko[0][j][j][k],m)
                #print(m) #ここに本来なら来るはず、おかしい
                yoko[0][i][j][k]=m
    
    for k in range(h):
        for i in range(w-1):
            m=tate[0][i][i][k]
            for j in range(i+1,w):
                if grid[k][j]!=grid[k][j-1]:
                    break
                m=min(tate[0][j][j][k],m)
                tate[0][i][j][k]=m
    #y=yoko[0][0][0][0]
    #y=yoko[0][0][1][0]
    #print(y)
    
    #終わるまでやる
    #yoko= #複雑度、上、下、横
    #tate= #複雑度、左、右、縦
    for c in range(1,18):
        #y=yoko[c-1][0][1][0]
        #print(y)
        if yoko[c-1][0][h-1][0]==w:
            print(c-1)
            break
        for i in range(h):
            for j in range(i,h):
                for k in range(w):
                    temp=yoko[c-1][i][j][k]
                    if temp+k==w:
                        yoko[c][i][j][k]=temp
                    else:
                        yoko[c][i][j][k]=max(temp+yoko[c-1][i][j][k+temp],yoko[c][i][j][k])
                    if j!=h-1:
                        temp2=tate[c-1][k][k+temp-1][j+1]
                        yoko[c][i][j+temp2][k]=max(temp,yoko[c][i][j+temp2][k])
        
        for i in range(w):
            for j in range(i,w):
                for k in range(h):
                    temp=tate[c-1][i][j][k]
                    if temp+k==h:
                        tate[c][i][j][k]=temp
                    else:
                        tate[c][i][j][k]=max(temp+tate[c-1][i][j][k+temp],tate[c][i][j][k])
                    if j!=w-1:
                        temp2=yoko[c-1][k][k+temp-1][j+1]
                        tate[c][i][j+temp2][k]=max(temp,tate[c][i][j+temp2][k])
        
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    for j in range(w - 2, -1, -1):
        if fi[j] != fi[j + 1]:
            curr = hi[j][i] = j
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in range(i + 1, h):
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hij[k] == -1:
                continue
            nxtr = hij[k] + 1
            dr = nxtr - curr
            if dr > 0:
                vij[curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                for l in range(curr, h_ijk + 1):
                    vij[l] = max(vij[l], k)
                curr = h_ijk + 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                for l in range(curb, v_ijk + 1):
                    hij[l] = max(hij[l], k)
                curb = v_ijk + 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HI = [0] * h
WI = [0] * w

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WI] for _ in HI]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WI] for _ in HI]  # ver[top][left][right] = bottom

for i in range(h):
    curr = hor[i][-1][i] = w - 1
    for j in range(w - 2, -1, -1):
        if field[i][j] != field[i][j + 1]:
            curr = hor[i][j][i] = j
        else:
            hor[i][j][i] = curr

for i in range(h):
    for j in range(w):
        curr = hor[i][j][i]
        top_left = field[i][j]
        for k in range(i + 1, h):
            if field[k][j] != top_left:
                break
            curr = hor[i][j][k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hor[i][j][k] == -1:
                continue
            nxtr = hor[i][j][k] + 1
            dr = nxtr - curr
            if dr > 0:
                ver[i][j][curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in range(h):
        for j in range(w):
            hij = hor[i][j]
            vij = ver[i][j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hor[i][h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                for l in range(curr, h_ijk + 1):
                    vij[l] = max(vij[l], k)
                curr = h_ijk + 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                for l in range(curb, v_ijk + 1):
                    hij[l] = max(hij[l], k)
                curb = v_ijk + 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
A_list = [[0]*W for _ in range(H)]
for h in range(H):
    s = list(input())
    for w in range(W):
        if s[w] == "#":
            A_list[h][w] = 1


entropie_dict = dict()

def entropie(p, q, r, s):
    # p, q : H
    # r, s : W

    # find hash
    hash_ = "".join(["".join([str(A_list[h][w]) for h in range(p, q)]) for w in range(r, s)]) + str(q - p) + str(s - r)
    val = entropie_dict.get(hash_, -1)
    if val != -1:
        return val
    S = sum([sum([A_list[h][w] for h in range(p, q)]) for w in range(r, s)])
    if S == 0:
        entropie_dict[hash_] = 0
        return 0
    elif S == (q - p) * (s - r):
        entropie_dict[hash_] = 0
        return 0
    else:
        if p + 1 == q:
            res_1 = 100000000
        else:
            res_1 = min([max(entropie(p, u, r, s), entropie(u, q, r, s)) + 1 for u in range(p+1, q)])
        if r + 1 == s:
            res_2 = 100000000
        else:
            res_2 = min([max(entropie(p, q, r, v), entropie(p, q, v, s)) + 1 for v in range(r+1, s)])
        res = min(res_1, res_2)
        entropie_dict[hash_] = res
        return res

print(entropie(0, H, 0, W))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    Xi = X[i]
    Yi = Y[i]
    for j in range(W):
        Xi[j][i] = j
        Yi[j][j] = i
for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W-1)[::-1]:
        if Ai[j] == Ai[j+1]:
            Xi[j][i] = Xi[j+1][i]
for i in range(H-1)[::-1]:
    Yi = Y[i]
    Yi1 = Y[i+1]
    Ai = A[i]
    Ai1 = A[i+1]
    for j in range(W):
        if Ai[j] == Ai1[j]:
            Yi[j][j] = Yi1[j][j]

for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W):
        Xij = Xi[j]
        for ii in range(i+1, H):
            if A[ii][j] != Ai[j]:
                break
            Xij[ii] = min(Xij[ii-1], X[ii][j][ii])
for i in range(H):
    Yi = Y[i]
    Ai = A[i]
    for j in range(W):
        Yij = Yi[j]
        for jj in range(j+1, W):
            if Ai[jj] != Ai[j]:
                break
            Yij[jj] = min(Yij[jj-1], Yi[jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if j <= jj > Xij[ii]:
                    Xij[ii] = jj
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if i <= ii > Yij[jj]:
                    Yij[jj] = ii

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    Xi = X[i]
    Yi = Y[i]
    for j in range(W):
        Xi[j][i] = j
        Yi[j][j] = i
for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W-1)[::-1]:
        if Ai[j] == Ai[j+1]:
            Xi[j][i] = Xi[j+1][i]
for i in range(H-1)[::-1]:
    Yi = Y[i]
    Yi1 = Y[i+1]
    Ai = A[i]
    Ai1 = A[i+1]
    for j in range(W):
        if Ai[j] == Ai1[j]:
            Yi[j][j] = Yi1[j][j]

for i in range(H):
    Xi = X[i]
    Ai = A[i]
    for j in range(W):
        Xij = Xi[j]
        for ii in range(i+1, H):
            if A[ii][j] != Ai[j]:
                break
            Xij[ii] = min(Xij[ii-1], X[ii][j][ii])
for i in range(H):
    Yi = Y[i]
    Ai = A[i]
    for j in range(W):
        Yij = Yi[j]
        for jj in range(j+1, W):
            if Ai[jj] != Ai[j]:
                break
            Yij[jj] = min(Yij[jj-1], Yi[jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if jj >= j:
                    Xij[ii] = max(Xij[ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if ii >= i:
                    Yij[jj] = max(Yij[jj], ii)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
A = [[1 if a == "#" else 0 for a in input()] for _ in range(H)]
X = [[[-2] * (H + 2) for _ in range(W + 2)] for _ in range(H + 2)]
Y = [[[-2] * (W + 2) for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(H):
    for j in range(W):
        X[i][j][i] = j
        Y[i][j][j] = i
for i in range(H):
    for j in range(W-1)[::-1]:
        if A[i][j] == A[i][j+1]:
            X[i][j][i] = X[i][j+1][i]
for i in range(H-1)[::-1]:
    for j in range(W):
        if A[i][j] == A[i+1][j]:
            Y[i][j][j] = Y[i+1][j][j]

for i in range(H):
    for j in range(W):
        for ii in range(i+1, H):
            if A[ii][j] != A[i][j]:
                break
            X[i][j][ii] = min(X[i][j][ii-1], X[ii][j][ii])
for i in range(H):
    for j in range(W):
        for jj in range(j+1, W):
            if A[i][jj] != A[i][j]:
                break
            Y[i][j][jj] = min(Y[i][j][jj-1], Y[i][jj][jj])

for k in range(16):
    if X[0][0][H-1] == W-1:
        print(k)
        break
    elif k == 15:
        print(16)
        break
    for i in range(H):
        Xi = X[i]
        Yi = Y[i]
        for j in range(W):
            Xij = Xi[j]
            Yij = Yi[j]
            for ii in range(i, H):
                Xijii = Xij[ii]
                if Xijii >= 0 and X[i][Xijii + 1][ii] >= 0:
                    Xij[ii] = X[i][Xijii + 1][ii]
            for jj in range(j, W):
                Yijjj = Yij[jj]
                if Yijjj >= 0 and Y[Yijjj + 1][j][jj] >= 0:
                    Yij[jj] = Y[Yijjj + 1][j][jj]
            
            jj = W - 1
            for ii in range(i, H):
                while jj >= j and Yij[jj] < ii:
                    jj -= 1
                if jj >= j:
                    Xij[ii] = max(Xij[ii], jj)
            
            ii = H - 1
            for jj in range(j, W):
                while ii >= i and Xij[ii] < jj:
                    ii -= 1
                if ii >= i:
                    Yij[jj] = max(Yij[jj], ii)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))
WR2 = list(range(w - 2, -1, -1))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    curc = fi[-1]
    for j in WR2:
        if fi[j] != curc:
            curr = hi[j][i] = j
            curc = fi[j]
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in HR[i + 1:]:
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            h_ijk = hij[k]
            if h_ijk == -1:
                continue
            while curr <= h_ijk:
                vij[curr] = k
                curr += 1

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in HR[i:]:
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in WR[j:]:
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                while curr <= h_ijk:
                    vij[curr] = max(vij[curr], k)
                    curr += 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                while curb <= v_ijk:
                    hij[curb] = max(hij[curb], k)
                    curb += 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
field = [input() for _ in [0] * h]
HR = list(range(h))
WR = list(range(w))
WR2 = list(range(w - 2, -1, -1))

# horizontal dp, vertical dp
hor = [[[-1] * h for _ in WR] for _ in HR]  # hor[top][left][bottom] = right
ver = [[[-1] * w for _ in WR] for _ in HR]  # ver[top][left][right] = bottom

for i in HR:
    hi = hor[i]
    fi = field[i]
    curr = hi[-1][i] = w - 1
    curc = fi[-1]
    for j in WR2:
        if fi[j] != curc:
            curr = hi[j][i] = j
            curc = fi[j]
        else:
            hi[j][i] = curr

for i in HR:
    hi = hor[i]
    vi = ver[i]
    fi = field[i]
    for j in WR:
        hij = hi[j]
        vij = vi[j]
        fij = fi[j]
        curr = hij[i]
        for k in range(i + 1, h):
            if field[k][j] != fij:
                break
            curr = hij[k] = min(curr, hor[k][j][k])
        curr = j
        for k in range(h - 1, i - 1, -1):
            if hij[k] == -1:
                continue
            nxtr = hij[k] + 1
            dr = nxtr - curr
            if dr > 0:
                vij[curr:nxtr] = [k] * dr
                curr = nxtr

ans = 0
while True:
    if hor[0][0][-1] == w - 1:
        break
    for i in HR:
        hi = hor[i]
        vi = ver[i]
        for j in WR:
            hij = hi[j]
            vij = vi[j]

            # print(ans + 1, i, j, 'first')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using hor, ver using ver
            for k in range(i, h):
                h_ijk = hij[k]
                if h_ijk == -1:
                    break
                if h_ijk == w - 1:
                    continue
                hij[k] = max(h_ijk, hi[h_ijk + 1][k])
            for k in range(j, w):
                v_ijk = vij[k]
                if v_ijk == -1:
                    break
                if v_ijk == h - 1:
                    continue
                vij[k] = max(v_ijk, ver[v_ijk + 1][j][k])

            # print(ans + 1, i, j, 'before')
            # print(hor[i][j])
            # print(ver[i][j])

            # Update hor using ver, ver using hor
            curr = j
            for k in range(h - 1, i - 1, -1):
                h_ijk = hij[k]
                if h_ijk == -1:
                    continue
                while curr <= h_ijk:
                    vij[curr] = max(vij[curr], k)
                    curr += 1
            curb = i
            for k in range(w - 1, j - 1, -1):
                v_ijk = vij[k]
                if v_ijk == -1:
                    continue
                while curb <= v_ijk:
                    hij[curb] = max(hij[curb], k)
                    curb += 1

            # print(ans + 1, i, j, 'after')
            # print(hor[i][j])
            # print(ver[i][j])
    ans += 1

print(ans)

Submission status: Runtime Error

Solution code:

def f(q, t, count, i, j):
    if t[i][j] == '.':
        t[i][j] = '#'
        q.append((i, j))
        used[(i, j)] = count

h, w = map(int, input().split(" "))

t = [[-1] * (w+2)]
for _ in range(h):
    t.append([ -1] + list(input()) + [-1])
t.append([-1] * (w+2))

q = []
used = {}
for i, row in enumerate(t):
    for j, col in enumerate(row):
        if t[i][j] == '#':
            q.append((i, j))
            used[(i, j)] = 0

while len(q) != 0:
    i, j = q.pop(0)
    count = used[(i, j)]
    f(q, t, count+1, i-1, j)
    f(q, t, count+1, i+1, j)
    f(q, t, count+1, i, j-1)
    f(q, t, count+1, i, j+1)

print(max(used.values()))

Submission status: Runtime Error

Solution code:
def f(q, t, count, i, j):
    if t[i][j] == '.':
        t[i][j] = '#'
        q.append((i, j))
        used[(i, j)] = count

h, w = map(int, input().split(" "))

t = [[-1] * (w+2)]
for row in range(1, w + 1):
    t.append([ -1] + list(input()) + [-1])
t.append([-1] * (w+2))

q = []
used = {}
for i, row in enumerate(t):
    for j, col in enumerate(row):
        if t[i][j] == '#':
            q.append((i, j))
            used[(i, j)] = 0

while len(q) != 0:
    i, j = q.pop(0)
    count = used[(i, j)]
    f(q, t, count+1, i-1, j)
    f(q, t, count+1, i+1, j)
    f(q, t, count+1, i, j-1)
    f(q, t, count+1, i, j+1)

print(max(used.values()))

Submission status: Runtime Error

Solution code:
import math
N = int(input())
result = 0

root = math.ceil(math.sqrt(N) - 1)
for i in range(root):
    if N % (i + 1) == 0:
        result += N // (i + 1) - 1

print(result)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
result = 0

root = math.ceil(math.sqrt(N))
for i in range(root):
    if N % (i + 1) == 0:
        result += N / (i + 1) - 1

print(result)

Submission status: Runtime Error

Solution code:
import numpy as np

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

v = np.zeros(H + 1, dtype=np.int)
h = np.zeros(W + 1, dtype=np.int)
u = np.zeros(H + 1, dtype=np.int)
a = np.zeros(W + 1, dtype=np.int)

for i in range(H):
	a[0] = 0
	for j, c in enumerate(input()):
		a[j+1] = a[j] + (1 if c == '#' else 0)
	h[i + 1] = a[-1]
	for j in range(W + 1):
		v[j] = abs(a[j] - (a[-1] - a[j]))
for i in range(H + 1):
	u[i] = abs(h[i] - (h[-1] - a[i]))

print(max(np.max(v), np.max(u)))

Submission status: Runtime Error

Solution code:
import numpy as np

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

v = np.zeros(H + 1, dtype=np.int)
h = np.zeros(W + 1, dtype=np.int)
u = np.zeros(W + 1, dtype=np.int)
a = np.zeros(W + 1, dtype=np.int)

for i in range(H):
	a[0] = 0
	for j, c in enumerate(input()):
		a[j+1] = a[j] + (1 if c == '#' else 0)
	h[i + 1] = a[-1]
	for j in range(W + 1):
		v[j] = abs(a[j] - (a[-1] - a[j]))
for i in range(H + 1):
	u[i] = abs(h[i] - (h[-1] - a[i]))

print(max(np.max(v), np.max(u)))

Submission status: Runtime Error

Solution code:

H, W = map(int, input().split())
A_list = [[0]*W for _ in range(H)]
for h in range(H):
    s = list(input())
    for w in range(W):
        if s[w] == "#":
            A_list[h][w] = 1


entropie_list = [[[[-1]*(W+1) for _ in range(W+1)] for _ in range(H+1)] for _ in range(H+1)]

def entropie(p, q, r, s):
    # p, q : H
    # r, s : W
    if entropie_list[p][q][r][s] != -1:
        return entropie_list[p][q][r][s]
    S = sum([sum([A_list[h][w] for h in range(p, q)]) for w in range(r, s)])
    if S == 0:
        entropie_list[p][q][r][s] = 0
        return 0
    elif S == (q - p) * (s - r):
        entropie_list[p][q][r][s] = 0
        return 0
    else:
        if p + 1 == q:
            res_1 = 100000000
        else:
            res_1 = min([max(entropie(p, u, r, s), entropie(u, q, r, s)) + 1 for u in range(p+1, q)])
        if r + 1 == s:
            res_2 = 100000000
        else:
            res_2 = min([max(entropie(p, q, r, v), entropie(p, q, v, s)) + 1 for v in range(r+1, s)])
        res = min(res_1, res_2)
        entropie_list[p][q][r][s] = res
        return res

print(entropie(0, H, 0, W))