Problem:


Score : 800 points

Problem Statement

Mr. Takahashi has in his room an art object with H rows and W columns, made up of H \times W blocks.
Each block has a color represented by a lowercase English letter (a-z).
The color of the block at the i-th row and j-th column is c_{i,j}.  

Mr. Takahashi would like to dismantle the object, finding it a bit kitschy for his tastes.
The dismantling is processed by repeating the following operation:  

Choose one of the W columns and push down that column one row.
The block at the bottom of that column disappears.

Each time the operation is performed, a cost is incurred.
Since blocks of the same color have a property to draw each other together, the cost of the operation is the number of the pairs of blocks (p, q) such that:

The block p is in the selected column.

The two blocks p and q are horizontally adjacent (before pushing down the column).

The two blocks p and q have the same color.

Mr. Takahashi dismantles the object by repeating the operation H \times W times to get rid of all the blocks.
Compute the minimum total cost to dismantle the object.

Constraints

1 ≤ H ≤ 300

2 ≤ W ≤ 300

All characters c_{i,j} are lowercase English letters (a-z).

Partial Score

In test cases worth 300 points, W = 3.

Input

The input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2}..c_{1,W}
c_{2,1}c_{2,2}..c_{2,W}
:
c_{H,1}c_{H,2}..c_{H,W}

Output

Print the minimum total cost to dismantle the object.

Sample Input 1

2 3
rrr
brg

Sample Output 1

2

For example, the total cost of 2 can be achieved by performing the operation as follows and this is the minimum value.

Sample Input 2

6 3
xya
xya
ayz
ayz
xaz
xaz

Sample Output 2

0

The total cost of 0 can be achieved by first pushing down all blocks of the middle column, then all of the left column, and all of the right column.

Sample Input 3

4 2
ay
xa
xy
ay

Sample Output 3

0

The total cost of 0 can be achieved by the following operations:

pushing down the right column one row;

pushing down the left column one row;

pushing down all of the right column;

and pushing down all of the left column.

Sample Input 4

5 5
aaaaa
abbba
ababa
abbba
aaaaa

Sample Output 4

24

Sample Input 5

7 10
xxxxxxxxxx
ccccxxffff
cxxcxxfxxx
cxxxxxffff
cxxcxxfxxx
ccccxxfxxx
xxxxxxxxxx

Sample Output 5

130



Sample input:
2 3
rrr
brg


Sample output:
2

Submission status: Accepted

Solution code:
def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    grid = [[grid[j][i] for j in range(h)] for i in range(w)]
    ans = 0
    for i in range(w-1):
        same = [[0]*(h+1) for _ in [0]*(h+1)]
        for j in range(h-1, -1, -1):
            for k in range(h-1, -1, -1):
                same[j][k] += same[j+1][k+1]+(grid[i][-j-1] == grid[i+1][-k-1])
        dp = [[10**10]*(h+1) for _ in [0]*(h+1)]
        dp[0][0] = same[0][0]
        for j in range(h+1):
            for k in range(h+1):
                if j != 0:
                    dp[j][k] = min(dp[j][k], dp[j-1][k]+same[j][k])
                if k != 0:
                    dp[j][k] = min(dp[j][k], dp[j][k-1]+same[j][k])
        ans += dp[h][h]
    print(ans)


main()

Submission status: Accepted

Solution code:
import itertools


h, w = map(int, input().split())
c = [list(map(ord, input())) for i in range(h)]
c = list(itertools.chain.from_iterable(c))
INF = 10 ** 9
h2 = (h + 1) * (h + 1)

ans = 0
dq = [0] * h2
for wi in range(w - 1):
    for diff in range(h + 1):
        cnt1 = 0
        cnt2 = 0
        for i in range(h - diff):
            cnt1 += (c[i * w + wi] == c[(i + diff) * w + wi + 1])
            cnt2 += (c[(i + diff) * w + wi] == c[i * w + wi + 1])
        dq[diff * (h + 1)] = cnt1
        dq[diff] = cnt2
        for i in range(h - diff - 1):
            cnt1 -= (c[(h - i - 1 - diff) * w + wi] == c[(h - i - 1) * w + wi + 1])
            dq[(i + 1 + diff) * (h + 1) + i + 1] = cnt1
            cnt2 -= (c[(h - i - 1 - diff) * w + wi + 1] == c[(h - i - 1) * w + wi])
            dq[(i + 1) * (h + 1) + i + 1 + diff] = cnt2
            
    dp = [INF] * h2
    dp[0] = 0
    for i in range(h + 1):
        for j in range(h + 1):
            if i + 1 < h + 1:
                dp[(i + 1) * (h + 1) + j] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[(i + 1) *(h + 1) + j])
            if j + 1 < h + 1:
                dp[i * (h + 1) + j + 1] = min(dp[i * (h + 1) + j] + dq[i * (h + 1) + j], dp[i * (h + 1) + j + 1])
    ans += dp[-1]

print(ans)

Submission status: Accepted

Solution code:
def solve(k):
    dp = [[0] * (h + 1) for i in range(h + 1)]
    for i in range(h):
        for diff in range(h - i):
            dp[i + 1][i + 1 + diff] = dp[i][i + diff] + (s[i + diff][k] == s[i][k + 1])
            dp[i + 1 + diff][i + 1] = dp[i + diff][i] + (s[i][k] == s[i + diff][k + 1])

    dq = [[INF] * (h + 1) for i in range(h + 1)]
    dq[0][0] = 0
    for i in range(h):
        dq[i + 1][0] = dq[i][0] + dp[h - i][h]
        dq[0][i + 1] = dq[0][i] + dp[h][h - i]  
    for i in range(h):
        for j in range(h):
            dq[i + 1][j + 1] = min(dq[i + 1][j] + dp[h - (i + 1)][h - j],
                                   dq[i][j + 1] + dp[h - i][h - (j + 1)])

    return dq[h][h]


h, w = map(int, input().split())
s = [input() for i in range(h)]
INF = 10 ** 5
OFFSET = 500

ans = 0
for i in range(w - 1):
    ans += solve(i)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

c = []
for i in range(w):
    c.append(chr(150+i))

for i in range(h):
    inp = input()
    for j in range(w):
        c.append(inp[j])
h += 1
h2 = h**2
res = 0

for j in range(1,w):
    
    #d[x][y] : j列目x個とj-1列目y個の時の一致数
    d = [0]*(h2)

    for x in range(1,h):
        for y in range(1,h):
            if c[x*w+j] == c[y*w+j-1]:
                d[x*h+y] = d[x*h+y-h-1] + 1
            else:
                d[x*h+y] = d[x*h+y-h-1]
    
    #dp[x][y] : j列目x個とj-1列目y個までの最小一定数和
    dp = [10**10]*h2

    for i in range(h):
        dp[i] = dp[i*h] = 0

    for x in range(1,h):
        for y in range(1,h):
            if dp[x*h+y-1] < dp[x*h-h+y]:
                dp[x*h+y] = dp[x*h+y-1] + d[x*h+y]
            else:
                dp[x*h+y] = dp[x*h-h+y] + d[x*h+y]
    res += dp[-1]

print(res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    H, W = map(int, input().split())
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    le = [''] * H
    for i in range(H):
        le[i] = grid[i][0]

    ans = 0
    for w in range(1, W):
        ri = [''] * H
        for i in range(H):
            ri[i] = grid[i][w]
        cost = [[0] * (H+1) for _ in range(H+1)]
        for i in range(1, H+1):
            for j in range(1, H+1):
                cost[i][j] = cost[i-1][j-1] + int(le[i-1] == ri[j-1])

        inf = 1000000007
        dp = [[inf] * (H+1) for _ in range(H+1)]
        dp[0][0] = 0
        for i in range(H+1):
            for j in range(H+1):
                if i+1 <= H:
                    if dp[i][j] + cost[i+1][j] < dp[i+1][j]:
                        dp[i+1][j] = dp[i][j] + cost[i+1][j]
                if j+1 <= H:
                    if dp[i][j] + cost[i][j+1] < dp[i][j+1]:
                        dp[i][j+1] = dp[i][j] + cost[i][j+1]
        ans += dp[-1][-1]
        le = ri[:]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

inf = 10**9+7
def calc(W1, W2):
    H = len(W1)
    cost = [[0]*(1+H) for _ in range(1+H)]
    for i in range(H):
        for j in range(H):
            cost[i+1][j+1] = cost[i][j] + (1 if W1[i] == W2[j] else 0)
    dp = [[inf]*(1+H) for _ in range(1+H)]
    dp[H][H] = 0
    for s in range(2*H, 0, -1):
        for i1 in range(max(0, s-H), 1+min(s, H)):
            i2 = s - i1
            c = dp[i1][i2] + cost[i1][i2]
            if i1:
                dp[i1-1][i2] = min(dp[i1-1][i2], c)
            if i2:
                dp[i1][i2-1] = min(dp[i1][i2-1], c)
    return dp[0][0]

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

G = [list(map(lambda x:ord(x)-97, readline().strip())) for _ in range(H)]
G = list(map(list, zip(*G)))        
ans = 0
for i in range(W-1):
    ans += calc(G[i], G[i+1])
print(ans)

Submission status: Accepted

Solution code:
# 考えると、隣り合う列は結局 2*H 回ずることになり、
# それぞれの列間について最適な沈め順を見つけると、
# その順序関係を崩さないように全体の順番も構築できる（トポロジカルソートみたいに）ので、
# 各列間の最適解を求めて総和をとればいい

def accumulate_reverse(S1, S2):
    n = min(len(S1), len(S2))
    res = [0] * (n+1)
    c = 0
    for i in range(n):
        if S1[i] == S2[i]:
            c += 1
        res[n-i-1] = c
    return res

inf = 10**8
H, W = map(int, input().split())
C = [input() for _ in range(H)]
C_T = list(zip(*C))
C_T = ["".join(s) for s in C_T]
ans = 0
for C1, C2 in zip(C_T[:-1], C_T[1:]):
    # Z[i][j] := i 個ずれてて沈んでない方が j 個沈んでる状態の連結個数
    Z1 = []  # 左を押したとき（右が上にあるとき）
    Z2 = []  # 右を押したとき（左が上にあるとき）
    Z1.append(accumulate_reverse(C1, C2))
    for j in range(1, H+1):
        Z1.append(accumulate_reverse(C1, C2[j:]))
        Z2.append(accumulate_reverse(C1[j:], C2))
    Z1 += Z2[::-1]
    # dp[i][j] := 左を i 個、右を j 個沈めるまでの最小コスト  # 逆かも（どっちでもいい）
    dp = [[inf] * (H+2) for _ in range(H+2)]
    dp[0][0] = 0
    for j in range(H+1):
        for k in range(H+1):
            cost = dp[j][k] + Z1[j-k][min(j, k)]
            dp[j+1][k] = min(dp[j+1][k], cost)
            dp[j][k+1] = min(dp[j][k+1], cost)
    ans += dp[H][H]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)

Submission status: Accepted

Solution code:
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):u=C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);v=D[i][j]=min(D[i-1][j],D[i][j-1])+u
	r+=v
print(r)

Submission status: Accepted

Solution code:
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):u=C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+u
	r+=D[N-1][N-1]
print(r)

Submission status: Accepted

Solution code:
R=range
N,M,*S=open(0).read().split()
N=int(N)+1
M=int(M)-1
l=lambda:[[0]*N for _ in R(N)]
C=l()
D=l()
r=0
for t in R(M):
	for i in R(1,N):
		for j in R(1,N):C[i][j]=C[i-1][j-1]+(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N-1][N-1]
print(r)

Submission status: Accepted

Solution code:
N,M=map(int,input().split());C=[[0]*-~N for _ in range(N+1)];D=list(map(list,C));S=[input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print(r)

Submission status: Accepted

Solution code:
N,M=map(int,raw_input().split());C=[[0]*-~N for _ in range(N+1)];D=map(list,C);S=[raw_input()for _ in range(N)];r=0
for t in range(M-1):
	for i in range(1,N+1):
		for j in range(1,N+1):C[i][j]=C[i-1][j-1]+int(S[i-1][t]==S[j-1][t+1]);D[i][j]=min(D[i-1][j],D[i][j-1])+C[i][j]
	r+=D[N][N]
print r

Submission status: Accepted

Solution code:
H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = b
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans

Submission status: Runtime Error

Solution code:
def main():
    h, w = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    grid = [[grid[j][i] for j in range(h)] for i in range(w)]
    ans = 0
    for i in range(w-1):
        same = [[0]*(h+1) for _ in [0]*(w+1)]
        for j in range(h-1, -1, -1):
            for k in range(h-1, -1, -1):
                same[j][k] += same[j+1][k+1]+(grid[i][-j-1] == grid[i+1][-k-1])
        dp = [[10**10]*(h+1) for _ in [0]*(h+1)]
        dp[0][0] = same[0][0]
        for j in range(h+1):
            for k in range(h+1):
                if j != 0:
                    dp[j][k] = min(dp[j][k], dp[j-1][k]+same[j][k])
                if k != 0:
                    dp[j][k] = min(dp[j][k], dp[j][k-1]+same[j][k])
        ans += dp[h][h]
    print(ans)


main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

(C[:-1][:,:] == C[1:][:,r][])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
dp[:,H] = 0
for n in range(1,H+H+1):
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:-1] = np.minimum(dp[:,:-1],prev[:,1:])
    dp += dp_1[:,:,n]
answer = dp[:,H].sum()
print(answer)

Submission status: Runtime Error

Solution code:
import numpy as np
def inpl(): return list(map(int, input().split()))
def min(a, b): return a if a < b else b

H, W = inpl()
C = np.zeros((H, W), dtype=np.uint8)

for h in range(H):
    S = input()
    for w in range(W):
        C[w, h] = ord(S[w]) - 97

def calc_cost(L, R):
    def count(l, r):
        a = max(l-r, 0)
        b = max(r-l, 0)
        length = H-max(l, r)
        return np.sum(C[L, a:a+length] == C[R, b:b+length])

    DP = [[1000000]*(H+1) for _ in range(H+1)]
    DP[0][0] = 0
    
    for x in range(2*H+1):
        for y in range(max(0, x-H), min(x+1, H+1)):
            c = count(x-y, y)
            if x-y < H:
                DP[x-y+1][y] = min(DP[x-y+1][y], DP[x-y][y] + c)
            if y < H:
                DP[x-y][y+1] = min(DP[x-y][y+1], DP[x-y][y] + c)

    return DP[-1][-1]

ans = 0
for i in range(W-1):
    ans += calc_cost(i, i+1)
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
if w > 3: exit(1)
b=[[] for i in range(w+2)]
b[0] = [' ']*h
b[w+1] = [' ']*h
for y in range(h):
    r = list(input())
    for x in range(1, w+1):
        b[x].insert(0, r[x-1])

mem = {}

def rec(ls):
    if sum(ls[1:-1]) == 0: return 0
    if ''.join(map(chr,ls)) in mem: return mem[''.join(map(chr,ls))]
    cost = 10**9
    for x in range(1, w+1):
        if ls[x] <= 0: continue
        c = list(map(lambda a: a[0]==a[1], zip(b[x-1][h-ls[x-1]:], b[x][h-ls[x]:]))).count(True)
        c += list(map(lambda a: a[0]==a[1], zip(b[x][h-ls[x]:], b[x+1][h-ls[x+1]:]))).count(True)
        ls[x] -= 1
        cost = min(cost, c + rec(ls))
        ls[x] += 1
    mem[''.join(map(chr,ls))] = cost
    return cost

print(rec([len(c) for c in b]))

Submission status: Runtime Error

Solution code:
H, W = list(map(int, input().split()))
X = [input() for _ in range(H)]
Y = list(map(list, zip(*X)))


def get(A, B):
    cost = [[0 for _ in range(H + 2)] for _ in range(H + 2)]

    def calc(A, B, a_n, b_n):

        if a_n >= H or b_n >= H:
            return 0
        if (a_n, b_n) in cost:
            return cost[(a_n, b_n)]
        
    def set_cost(A, B, a_n, b_n):
        start = max(a_n, b_n)
        ans = 0
        for i in range(start, H):
            if A[i - a_n] == B[i - b_n]:
                ans += 1
            cost[(a_n + H - 1 - i, b_n + H - 1 - i)] = ans #cache

    for i in range(H):
        set_cost(A,B,0,i)
        set_cost(A,B,i,0)
        
    dp = [[999999999999999 for _ in range(H + 2)] for _ in range(H + 2)]
    dp[0][0] = 0

    for i in range(H + 1):
        for j in range(H + 1):
            dp[i + 1][j] = min(dp[i][j] + calc(A, B, i, j), dp[i + 1][j])
            dp[i][j + 1] = min(dp[i][j] + calc(A, B, i, j), dp[i][j + 1])
    # print(dp)

    return dp[H][H]


ans = 0
for i in range(W - 1):
    tmp = get(Y[i], Y[i + 1])
    ans += tmp
    # print(tmp)
print(ans)

Submission status: Runtime Error

Solution code:
class Bit:
    def __init__(self, n):
        sz = 1
        while n >= sz:
            sz *= 2
        self.size = sz
        self.data = [0]*sz

    def sum(self, i):
        assert i > 0
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def add(self, i, x):
        assert i > 0
        while i < self.size:
            self.data[i] += x
            i += i & -i

import bisect
N = int(raw_input())
a = [int(x)-1 for x in raw_input().split()]
weight = [1] * N
M = 10**9+7
def factorial(n):
    acc = 1
    for i in xrange(1, 1 + n):
        acc = (acc * i) % M
    return acc
def inv(n):
    return pow(n, M-2, M)
for i in xrange(N-1):
    weight[N-2-i] = (weight[N-1-i] * (i+1)) % M
missing = list(set(xrange(N)) - set(a))
missing.sort()
n_missing = len(missing)
sum_missing = sum(missing)
avg_missing = sum_missing * inv(n_missing)
n_present = N - n_missing
n_rows = factorial(n_missing)
acc = 0
i_missing = 0
i_present = 0
missing_lt_tot = 0
#present_values = []
present_values_bit = Bit(N+5)
inv_n_missing = inv(n_missing)
inv_2 = inv(2)
for i, (w, x) in enumerate(zip(weight, a)):
    if x == -1:
        ai = avg_missing
        bi = (i_missing * inv_2 + i_present - missing_lt_tot * inv_n_missing) % M
        i_missing += 1
    else:
        ai = x
        #bi = sum(1 for present_value in present_values if present_value < x)
        bi = present_values_bit.sum(x + 1)
        #present_values.append(x)
        present_values_bit.add(x + 2, 1)
        '''
        missing_lt = 0
        for j in missing:
            if j < a[i]:
                missing_lt += 1
        '''
        missing_lt = bisect.bisect(missing, a[i])
        missing_lt_tot += missing_lt
        #print '@', missing_lt, n_missing, i_missing, n_rows
        bi += missing_lt * inv_n_missing * i_missing
        bi %= M
        i_present += 1
    #print x, (ai * n_rows) % M, (bi * n_rows) % M, w
    acc = (acc + (((ai - bi) * n_rows) % M) * w) % M
print (acc + n_rows) % M

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
t=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
a_max=max(a)
t_max=max(t)
if a_max != t_max(t):
    print(0)
    sys.exit()
i=0
sum=1
while t[i]!=t_max:
    if t[i]==t[i+1]:
        sum*=t[i]
j=len(a)-1
while a[j]!=a_max:
    if a[j]==a[j-1]:
        sum*=a[j]
sum=sum*(a_max**(n-(i+j+1)))%((1e+9)+7)
print(sum)

Submission status: Runtime Error

Solution code:
h, w = map(int, raw_input().split())
a = []
for i in range(h):
    a[i] =  raw_input().split()

ans  = 0
for i in range(h):

    count = 0
    for j in range(h-i):
        if a[j][1] == a[j+i][0]:
            count += 1
        if a[j][1] == a[j+i][2]:
            count += 1

print ans