Problem:


Score : 600 points

Problem Statement

There are N cities in Republic of AtCoder. The size of the i-th city is A_{i}.
Takahashi would like to build N-1 bidirectional roads connecting two cities so that any city can be reached from any other city by using these roads.

Assume that the cost of building a road connecting the i-th city and the j-th city is |i-j| \times D + A_{i} + A_{j}.
For Takahashi, find the minimum possible total cost to achieve the objective.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq D \leq 10^9

1 \leq A_{i} \leq 10^9

A_{i} and D are integers.

Input

Input is given from Standard Input in the following format:

N D
A_1 A_2 ... A_N

Output

Print the minimum possible total cost.

Sample Input 1

3 1
1 100 1

Sample Output 1

106

This cost can be achieved by, for example, building roads connecting City 1, 2 and City 1, 3.

Sample Input 2

3 1000
1 100 1

Sample Output 2

2202

Sample Input 3

6 14
25 171 7 1 17 162

Sample Output 3

497

Sample Input 4

12 5
43 94 27 3 69 99 56 25 8 15 46 8

Sample Output 4

658



Sample input:
3 1
1 100 1


Sample output:
106

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  xC = 0
  while T[xR] != xR:
    xC += 1
    xR = T[xR]
  yR = y
  yC = 0
  while T[yR] != yR:
    yC += 1
    yR = T[yR]
  if xR != yR:
    if xC < yC:
      T[xR] = yR
    else:
      T[yR] = xR
  return xR != yR

N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = (N - 1) * D + A[N - 1]
Ll = [N - 1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t
    
Ll = tuple(Ll)
Lr = tuple(Lr)
    
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
 
cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  L.append((A[i] + A[t] + (i - t) * D, t, i))
 
L = list(set(L))  
L.sort()
L = tuple(L)

T = [i for i in range(N)]
C = 0
A = 0

for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = (N - 1) * D + A[N - 1]
Ll = [N - 1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t
    
Ll = tuple(Ll)
Lr = tuple(Lr)
    
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
 
cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  L.append((A[i] + A[t] + (i - t) * D, t, i))
 
L = list(set(L))  
L.sort()
L = tuple(L)

T = [[i, 0] for i in range(N)]
C = 0
A = 0

for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
# TLEテスト
N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = (N - 1) * D + A[N - 1]
Ll = [N - 1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t
    
Ll = tuple(Ll)
Lr = tuple(Lr)
    
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
 
cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  L.append((A[i] + A[t] + (i - t) * D, t, i))
 
L = list(set(L))  
L.sort()
L = tuple(L)

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  L.append((i, Ll[cnt]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  L.append((Lr[cnt], i))

L = tuple(set(L))
L2 = []
for i in range(len(L)):
  a = L[i][0]
  b = L[i][1]
  L2.append((A[a] + A[b] + (b - a) * D,) + L[i])
  
L2.sort()

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0

for i in L2:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
# TLEテスト
N, D = tuple(map(int,input().split()))
A = tuple(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  L.append((0, i, Ll[cnt]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  L.append((0, Lr[cnt], i))

L = tuple(set(L))
L2 = []
for i in range(len(L)):
  a = L[i][1]
  b = L[i][2]
  L2.append((A[a] + A[b] + (b - a) * D , ) + L[i])
  
L2.sort()

Submission status: Wrong Answer

Solution code:
# TLEテスト
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  L.append((0, i, Ll[cnt]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  L.append((0, Lr[cnt], i))

L = list(set(L))  
for i in range(len(L)):
  L[i] = list(L[i])
  a = L[i][1]
  b = L[i][2]
  L[i][0] = A[a] + A[b] + (b - a) * D
  
L.sort()

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    T[T[xR][0]][1] = T[xR][1] + 1
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    T[T[yR][0]][1] = T[yR][1] + 1
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      if T[yR][1] < T[xR][1] + 1:
        T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      if T[xR][1] < T[yR][1] + 1:
        T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  L.append((A[i] + A[t] + (i - t) * D, t, i))

L = list(set(L))  
L.sort()

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
#TLE　テスト
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = A[i]
  if rt > t + (k - i) * D:
    Lr.append(i)
    k = i
    rt = t

Ch = [[0] * N for i in range(N)]
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
  Ch[i][t] = 1

Submission status: Wrong Answer

Solution code:
# TLEテスト
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i]  
  if rt > t - (k - i) * D :
    Ll.append(i)
    k = i
    rt = t

Submission status: Wrong Answer

Solution code:
# TLEテスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = A[i] - (k - i) * D 
  if rt > t:
    Ll.append(i)
    k = i
    rt = A[i]

rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = (k - i) * D + A[i]
  if rt > t:
    Lr.append(i)
    k = i
    rt = A[i]

Ch = [[0] * N for i in range(N)]
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  t = Ll[cnt]
  L.append((A[i] + A[t] + (t - i) * D, i, t))
  Ch[i][t] = 1

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  t = Lr[cnt]
  if Ch[t][i] == 0:
  	L.append((A[i] + A[t] + (i - t) * D, t, i))
   
L.sort()

Submission status: Wrong Answer

Solution code:
#TLE テスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [N-1]
k = N - 2
for i in range(N - 2, 0, -1):
  t = (i - k) * D + A[i]
  if rt > t:
    Ll.append(i)
    k = i
    rt = A[i]
    
rt = (N - 1) * D + A[0]
Lr = [0]
k = 0
for i in range(1, N - 1):
  t = (k - i) * D + A[i]
  if rt > t:
    Lr.append(i)
    k = i
    rt = A[i]

Ch = [[0] * N for i in range(N)]
L = []
cnt = -1
for i in range(N-1):
  if i >= Ll[cnt]:
    cnt -= 1
  L.append((A[i] + A[Ll[cnt]] + (Ll[cnt] - i) * D, i, Ll[cnt]))
  Ch[i][Ll[cnt]] = 1

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt]:
    cnt -= 1
  if Ch[Lr[cnt]][i] == 0:
  	L.append((A[i] + A[Lr[cnt]] + (i - Lr[cnt]) * D, Lr[cnt], i))
  
L.sort()

Submission status: Wrong Answer

Solution code:


class Unionfindtree:
    def __init__(self, number):
        self.par = [i for i in range(number)]
        self.rank = [0] * (number)

    def find(self, x):  # 親を探す
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):  # x,yを繋げる
        px = self.find(x)
        py = self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            self.par[px] = py
        else:
            self.par[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

    def connect(self, x, y):  # 親が同じかみる
        return self.find(x) == self.find(y)

class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [10**22] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] = min(x,self.list[i])
            i += i & -i

    def search(self, i):  # 1-i min
        s = 10**22
        while i > 0:
            s = min(s,self.list[i])
            i -= i & -i
        return s


N,D=map(int,input().split())
A=[int(i) for i in input().split()]
lefttree = BIT(N)
dd={}
table=[]
for i in range(N):
    lefttree.add(i+1,A[i]+(N-1-i)*D)
    dd[A[i]+(N-1-i)*D]=i
    if i>0:
        s=lefttree.search(i)
        y=dd[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
#print(table)
righttree = BIT(N)
dr={}
for i in range(N-1,-1,-1):
    righttree.add(N-i,A[i]+i*D)
    dr[A[i]+i*D]=i
    if i<N-1:
        s=righttree.search(N-1-i)
        #print(i, dr,s)
        y=dr[s]
        table.append((A[i]+A[y]+D*abs(i-y),i,y))
#print(table)

#print(table)
#print(dr)
table.sort()
uniontrees=Unionfindtree(N)
ans=0
for cost,s,t in table:
    if not uniontrees.connect(s,t):
        ans+=cost
        uniontrees.union(s,t)
print(ans)

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, -1, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t
    
rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t

lf = Ll[-1][1]
ri = Lr[-1][1]

L = []
cnt = -1
for i in range(ri):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, lf, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

#print(L)

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[xR][0] = yR
      T[yR][1] = T[xR][1] + 1
    else:
      T[yR][0] = xR
      T[xR][1] = T[yR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
    
L = []
cnt = -1
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

#print(L)

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
## TLEテスト
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
    
L = []
cnt = -1
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

Submission status: Wrong Answer

Solution code:
def judT(x, y):
  xR = x
  while T[xR][0] != xR:
    xR = T[xR][0]
  yR = y
  while T[yR][0] != yR:
    yR = T[yR][0]
  if xR != yR:
    if T[xR][1] < T[yR][1]:
      T[yR][0] = xR
      T[xR][1] = T[yR][1] + 1
    else:
      T[xR][0] = yR
      T[yR][1] = T[xR][1] + 1
  return xR != yR

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

rt = (N-1) * D + A[N-1]
Ll = [(rt, N-1)]
for i in range(N-2, 0, -1):
  t = i * D + A[i]
  if rt > t:
    Ll.append((t, i))
    rt = t

rt = (N-1) * D + A[0]
Lr = [(rt, 0)]
for i in range(1, N-1):
  t = (N - 1 - i) * D + A[i]
  if rt > t:
    Lr.append((t, i))
    rt = t
    
L = []
cnt = -1
for i in range(N - 1):
  if i >= Ll[cnt][1]:
    cnt -= 1
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = -1
for i in range(N-1, 0, -1):
  if i <= Lr[cnt][1]:
    cnt -= 1
  L.append((A[i] + Lr[cnt][0] - (N - 1 - i) * D, Lr[cnt][1], i))

L = list(set(L))
L.sort()

#print(L)

T = [[i, 0] for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
## TLEテスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

L = []
LC = 0
cnt = 0
while True:
  while Ll[cnt][1] > LC:
    L.append((A[LC] + Ll[cnt][0] - LC * D, LC, Ll[cnt][1]))
    LC += 1
  if LC == N-1:
    break
  while Ll[cnt][1] <= LC:
    cnt += 1

cnt = 0
RC = N-1
while True:
  while Lr[cnt][1] < RC:
    L.append((A[RC] + Lr[cnt][0] - (N - 1 - RC) * D, Lr[cnt][1], RC))
    RC -= 1
  if RC == 0:
    break
  while Lr[cnt][1] >= RC:
    cnt += 1

L = list(set(L))
L.sort()

Submission status: Wrong Answer

Solution code:
## LTEテスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

L = []
CL = 0
CR = 0
for i in range(0, N-1):
  while Ll[CL][1] <= i:
    CL+=1
  L.append((A[i] + Ll[CL][0] - i * D, i, Ll[CL][1]))
  R = N-1-i
  while Lr[CR][1] >= R:
    CR+=1
  L.append((A[R] + Lr[CR][0] - i * D, Lr[CR][1], R))

L = list(set(L))
L.sort()

Submission status: Wrong Answer

Solution code:
## TLEテスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

L = []
cnt = 0
for i in range(0, N-1):
  while True:
    if Ll[cnt][1] <= i:
      cnt+=1
    else:
      break
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = 0
for i in range(N-1, 0, -1):
  while True:
    if Lr[cnt][1] >= i:
      cnt+=1
    else:
      break
  L.append((A[i] + Lr[cnt][0] - (N -1 - i) * D, i, Lr[cnt][1]))

L.sort()

Submission status: Wrong Answer

Solution code:
## TLEテスト

N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

Submission status: Wrong Answer

Solution code:
def getR(x):
  if T[x] == x:
    return x
  return getR(T[x])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    T[xR] = yR
  return xR != yR
 
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))

Ll = [(A[i] + i * D, i) for i in range(1, N)]
Lr= [(A[i] + (N-i-1) * D, i) for i in range(0, N-1)]
Ll.sort()
Lr.sort()

L = []
cnt = 0
for i in range(0, N-1):
  while True:
    if Ll[cnt][1] <= i:
      cnt+=1
    else:
      break
  L.append((A[i] + Ll[cnt][0] - i * D, i, Ll[cnt][1]))

cnt = 0
for i in range(N-1, 0, -1):
  while True:
    if Lr[cnt][1] >= i:
      cnt+=1
    else:
      break
  L.append((A[i] + Lr[cnt][0] - (N -1 - i) * D, i, Lr[cnt][1]))

L.sort()

T = [i for i in range(N)]
 
C = 0
A = 0
 
for i in L:
  if judT(i[1], i[2]):
    C += 1
    A += i[0]
    #print(i)
    if C == N-1:
      break
 
print(A)

Submission status: Wrong Answer

Solution code:
##TLE確認

def getR(x):
  if T[x] == x:
    return x
  return getR(T[x])
 
def judT(x, y):
  xR = getR(x)
  yR = getR(y)
  if xR != yR:
    T[xR] = yR
  return xR != yR
 
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))
 
L = [((j-i) * D + A[i] + A[j], i, j) for i in range(N) for j in range(i+1, N)]
 
L.sort()
 
T = [i for i in range(N)]
 
C = 0
A = 0
 
print(A)

Submission status: Wrong Answer

Solution code:
N, D = list(map(int,input().split()))
A = list(map(int, input().split()))
L = [[(abs(j-i) * D + A[i] if i != j else pow(10,10), i) for i in range(N)] for j in range(N)]

for i in range(len(L)):
  L[i].sort()

cnt = 0
T = []
for i in range(len(L)):
  if i not in T:
    cnt += A[i]
    T.append(i)
    T.append(L[i][0][1])
    cnt += L[i][0][0]

print(cnt)

Submission status: Wrong Answer

Solution code:
N, D = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N-1).bit_length()
INF = (10**18, -1)
ldata = [INF]*(2*N0)
rdata = [INF]*(2*N0)

for i in range(N):
    ldata[i+N0-1] = ((N-1-i)*D + A[i], i)
    rdata[i+N0-1] = (i*D + A[i], i)
for i in range(N0-2, -1, -1):
    ldata[i] = min(ldata[2*i+1], ldata[2*i+2])
    rdata[i] = min(rdata[2*i+1], rdata[2*i+2])

def query(data, l, r):
    if l >= r:
        return INF
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

E = []
for i in range(N):
    c, k = query(ldata, 0, i)
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], i, k))
    c, k = query(rdata, i+1, N)
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
print(ans)

Submission status: Wrong Answer

Solution code:
N, D = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N-1).bit_length()
INF = (2**31-1, -1)
ldata = [INF]*(2*N0)
rdata = [INF]*(2*N0)

for i in range(N):
    ldata[i+N0-1] = ((N-1-i)*D + A[i], i)
    rdata[i+N0-1] = (i*D + A[i], i)
for i in range(N0-2, -1, -1):
    ldata[i] = min(ldata[2*i+1], ldata[2*i+2])
    rdata[i] = min(rdata[2*i+1], rdata[2*i+2])

def query(data, l, r):
    if l >= r:
        return INF
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])

        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

E = []
for i in range(N):
    c, k = query(ldata, 0, i)
    if k != -1:
        c -= (N-1-i)*D
        E.append((c + A[i], i, k))
    c, k = query(rdata, i+1, N)
    if k != -1:
        c -= i*D
        E.append((c + A[i], i, k))

*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

E.sort()
ans = 0
for c, i, j in E:
    if unite(i, j):
        ans += c
print(ans)

Submission status: Wrong Answer

Solution code:
N,D=map(int,input().split())
A=list(map(int,input().split()))
B=list(range(N))
A=[(b,a) for b,a in zip(B,A)]

for i in range(N-2,-1,-1):
    for j in range(i,-1,-1):
        if (abs(A[j-1][0]-A[j+1][0])-abs(A[j-1][0]-A[j][0]))*D+A[j+1][1]-A[j][1]<0:
            A[j],A[j+1]=A[j+1],A[j]
ans=0
for i in range(N-1):
    ans += abs(A[i+1][0]-A[i][0])*D+A[i][1]+A[i+1][1]
print(ans)

Submission status: Wrong Answer

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

N,D=map(int,input().split())
A=list(map(int,input().split()))

#cost=abs(i-j)*D+A[i]+A[j]

SUMDA=[D*i-A[-i] for i in range(1,N+1)]
SUMDA.reverse()


MIN=SUMDA[-1]
MININD=[None]*N
MININD[N-1]=N-1
for i in range(N-2,-1,-1):
    if SUMDA[i]<MIN:
        MIN=SUMDA[i]
        MININD[i]=i
    else:
        MININD[i]=MININD[i+1]

SUMA=sum(A)
ANS=float("inf")
for i in range(N-2):
    cost=0
    k=MININD[i+1]

    cost=D*(N-1)+D*(N-1-abs(k-i))+SUMA*2-A[i]-A[k]
    #print(cost)

    if ANS>cost:
        ANS=cost

print(ANS)

Submission status: Wrong Answer

Solution code:
n, d = map(int, input().split())
a = list(map(int, input().split()))

s = 0
a1 = a[0]
a2 = a[-1]
cost1 = [0, 0]
cost1_2 = [0, 0]
cost2 = [n-1, 0]
cosr2_2 = [n-1, 0]

for i, v in enumerate(a):
    s += v
    c1 = d * i - v + a1
    
    if c1 < cost1[1]:
        cost1_2 = cost1.copy()
        cost1 = [i, c1]

ans = s * 2 - a1 - a2 + d * (n-1)

for i , v in enumerate(reversed(a)):
    c2 = d * i - v + a2
    
    if c2 < cost2[1]:
        cost2_2 = cost2.copy()
        cost2 = [n-1-i, c2]

if cost1[0] == cost2[0]:
    ad = min(cost1_2[1] + cost2[1], cost1[1] + cost2_2[1])
else:
    ad = cost1[1] + cost2[1]

ans = ans + ad

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

N, D= list(map(int, input().split()))
A = list(map(int, input().split()))

total = 0
# M = [ (A[i] - (i + 1) * D, i) for i in range(len(A))]
C = []
for i in range(N):
    cost = A[i] - (i + 1) * D
    index = bisect.bisect_left(C, cost)
    C.insert(index, cost)
    if i != 0:
        # if index == 0:
        #     index = 1
        # else:
        index = index - 1
        total += C[index] + A[i] + (i + 1) * D

print(total)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,D=list(map(int,input().split()))
A=np.array(list(map(int,input().split())))
sum=np.sum(A)
AnsList=np.array([])
for i in range(N-1):
    for j in range(i+1,N):
        tmp=2*sum-A[i]-A[j]
        tmp+=D*(2*N+i-j-2)
        AnsList=np.append(AnsList,[tmp])
AnsList=np.sort(AnsList)
print(int(AnsList[0]))

Submission status: Wrong Answer

Solution code:
n,d = map(int, input().split())
aList = list(map(int, input().split()))
basePoint=sum(aList)*2+(n-1)*d
print(basePoint)

ansi=0
ansj=0
ansSaPoint=100000000000
for i in range(n):
    for j in range(i+1,n):

        sa=((i+1-1)+(n-(j+1)))*d-(aList[i]+aList[j])
        print(i,j,sa)
        if(sa<ansSaPoint):
            ansSaPoint=sa
            ansi=i
            ansj=j

ans=basePoint+ansSaPoint
print(ans)

Submission status: Wrong Answer

Solution code:
# E
N, D = map(int, input().split())
A_list = list(map(int, input().split()))

# minimum spanning tree

res = 0

# Prim based
B_list = [0]*N
for i in range(N):
    B_list[i] = A_list[i] + D*i
    
C_list = [0]*N
for i in range(N):
    C_list[i] = A_list[i] + D*(N-i)
    
# cummin seen from left
B_cummmin = [0]*N
R = B_list[N-1]
BA = N-1
for i in range(N-1, -1, -1):
    if B_list[i] <= R:
        R = B_list[i]
        BA = i
    B_cummmin[i] = BA

# cummin seen from right
C_cummmin = [0]*N
R = C_list[0]
CA = 0
for i in range(N):
    if C_list[i] <= R:
        R = C_list[i]
        CA = i
    C_cummmin[i] = CA

# start from 0
start = 0
while start < N-1:
    end = B_cummmin[start+1]
    target = C_cummmin[end-1]
    if target > start:
        target = start
    res += D*(end - target) + A_list[target] + A_list[end]
    for i in range(start+1, end):
        target = C_cummmin[i-1]
        ds = D*(i - target) + A_list[target] + A_list[i]
        de = D*(end - i) + A_list[end] + A_list[i]
        res += min(ds, de)
    start = end

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

a = list(map(int, input().split()))
n, d = a[0], a[1]
A = np.array(list(map(int, input().split())))
map = np.array([abs(i//n - i%n) * d + A[i//n] + A[i%n] for i in range(n * n)])
order = map.argsort()
score = sorted(map)
city = []
ans = 0
idx = 0
while True:
    if len(city) == n:
        break
    i, j = order[idx] // n, order[idx] % n
    if i == j:
        idx += 1
        continue
    if i in city and j in city:
        idx += 1
        continue
    else:
        if i not in city:
            city.append(i)
        if j not in city:
            city.append(j)
        ans += score[idx]
        idx += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# E
N, D = map(int, input().split())
A_list = list(map(int, input().split()))

# minimum spanning tree

res = 0

# Prim based
B_list = [0]*N
for i in range(N):
    B_list[i] = A_list[i] + D*i
    
C_list = [0]*N
for i in range(N):
    C_list[i] = A_list[i] + D*(N-i)
    
# cummin seen from left
B_cummmin = [0]*N
R = B_list[N-1]
BA = N-1
for i in range(N-1, -1, -1):
    if B_list[i] <= R:
        R = B_list[i]
        BA = i
    B_cummmin[i] = BA

# cummin seen from right
C_cummmin = [0]*N
R = C_list[0]
CA = 0
for i in range(N):
    if C_list[i] <= R:
        R = C_list[i]
        CA = i
    C_cummmin[i] = CA

# start from 0
start = 0
while start < N-1:
    end = B_cummmin[start+1]
    target = C_cummmin[end-1]
    if target > start:
        target = start
    res += D*(end - target) + A_list[target] + A_list[end]
    for i in range(start+1, end):
        ds = D*(i - target) + A_list[target] + A_list[i]
        de = D*(end - i) + A_list[end] + A_list[i]
        res += min(ds, de)
    start = end

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,d=map(int,input().split())
a=np.array(list(map(int,input().split())))

c=a[0]
link=[i*d+c+a[i] for i in range(1,n)]

for i in range(1,n):
    e=a[i]
    for j in range(i+1,n):
        f=(j-i)*d+e+a[j]
        if link[i] > f:
            link[i] = f

print(sum(link))