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: Runtime Error

Solution code:
import numpy as np

InputData1 = input()
InputData2 = input()

Lines = [data.split(" ") for data in [InputData1, InputData2]]
InputNumbers = [int(numbers) for line in Lines for numbers in line]

N = InputNumbers[0]
D = InputNumbers[1]
A = InputNumbers[2:]
# print(N, D, A)


def NetworkMatrix(Num, vector):
    matrix = np.empty((Num, Num))
    for i in range(Num):
        ai = np.empty(Num)
        for j in range(Num):
            if i < j:
                aij = (j-i)*D + vector[i] + vector[j]
            else:
                aij = 0
            ai[j] = aij
        matrix[i] = ai
    return matrix

def Explore(Num, matrix):
    ResultMatrix = matrix
    for i in range(Num):
        # ResultVector[i] = min(matrix.T[i])
        for j in range(Num):
            for k in range(Num):
                if i < j and j < k and min([matrix[i,j], matrix[j,k], matrix[i,k]]) != 0:
                    if matrix[i,j] >= matrix[j,k] and matrix[i,j] >= matrix[i,k]:
                        ResultMatrix[i,j] = 0
                    elif matrix[j,k] > matrix[i,j] and matrix[j,k] >= matrix[i,k]:
                        ResultMatrix[j,k] = 0
                    elif matrix[i,k] > matrix[i,j] and matrix[i,k] > matrix[j,k]:
                        ResultMatrix[i,k] = 0
    if np.sum(ResultMatrix != matrix) != 0:
        ResultMatrix = Explore(Num, matrix)
    return ResultMatrix

    



Matrix = NetworkMatrix(N, A)
# print(Matrix)
# Raveled = Matrix.ravel()
# Answer = sum(sorted(Raveled)[:N-1])
AnswerMatrix=Explore(N, Matrix)
# print(AnswerMatrix)
print(int(np.sum(AnswerMatrix)))

Submission status: Runtime Error

Solution code:
import numpy as np

InputData1 = input()
InputData2 = input()

Lines = [data.split(" ") for data in [InputData1, InputData2]]
InputNumbers = [int(numbers) for line in Lines for numbers in line]

N = InputNumbers[0]
D = InputNumbers[1]
A = InputNumbers[2:]
# print(N, D, A)


def NetworkMatrix(Num, vector):
    matrix = np.empty((Num, Num))
    for i in range(Num):
        ai = np.empty(Num)
        for j in range(Num):
            if i < j:
                aij = (j-i)*D + vector[i] + vector[j]
            else:
                aij = 0
            ai[j] = aij
        matrix[i] = ai
    return matrix

def Explore(Num, matrix):
    ResultMatrix = matrix
    for i in range(Num):
        # ResultVector[i] = min(matrix.T[i])
        for j in range(Num):
            for k in range(Num):
                if i < j < k and min([matrix[i,j], matrix[j,k], matrix[i,k]]) != 0:
                    if matrix[i,j] >= matrix[j,k] and matrix[i,j] >= matrix[i,k]:
                        ResultMatrix[i,j] = 0
                    elif matrix[j,k] > matrix[i,j] and matrix[j,k] >= matrix[i,k]:
                        ResultMatrix[j,k] = 0
                    elif matrix[i,k] > matrix[i,j] and matrix[i,k] > matrix[j,k]:
                        ResultMatrix[i,k] = 0
    if np.sum(ResultMatrix != matrix) != 0:
        ResultMatrix = Explore(Num, matrix)
    return ResultMatrix

    



Matrix = NetworkMatrix(N, A)
# print(Matrix)
# Raveled = Matrix.ravel()
# Answer = sum(sorted(Raveled)[:N-1])
AnswerMatrix=Explore(N, Matrix)
# print(AnswerMatrix)
print(int(np.sum(AnswerMatrix)))

Submission status: Runtime Error

Solution code:
import numpy as np
N,D = map(int(input().split()))
A = np.array(list(map(int(input().split()))))
count = np.arange(A.shape[0])
totalcost = 0
cities = np.hstack([count[:,np.newaxis],A[:,np.newaxis]])
def cost(x,y):
    return np.abs(x[:,0]-y[:,0])*D+x[:,1]+y[:,1]
to = np.zeros(N-1)
fro = np.arange(1,N)
costs = cost(cities[to],cities[fro])
totalcost = costs.sum()
while True:
    target = np.argmax(costs)
    targetfro = fro[target]
    targetto = to[target]
    thinkcost = cost(cities[targetfro],cities[np.delete(count,targetto,0)])
    if thinkcost.min() < costs[target]:
        targetto[target] = np.argmin(thinkcost)
        costs = cost(cities[to],cities[fro])
    else:
        break
totalcost = costs.sum()
print(totalcost)

Submission status: Runtime Error

Solution code:
N,D=input().split()
N=int(N)
D=int(D)
A=[int(x) for x in input().split()]
final_list=[x+1 for x in range(N)]
final_cost_list=[0]*N


def Check(to,i):
  to=final_list[to]
  if to==i:
    return False
  if to>i:
    return to
  else:
    return Check(to,i)

for i in range(N-1):
  cost_list=[]
  for j in range(N):
    if j==i:
      print('con',j)
      continue
    cost_list.append(abs(i-j)*D+A[i]+A[j])

  large=max(cost_list)+1
  while True:
    min_cost=min(cost_list)
    to=cost_list.index(min_cost)
    if to>=i:
      final_list[i]=to
      final_cost_list[i]=min_cost
      break
    r=Check(to,i)
    if(r):
      final_list[i]=to
      final_cost_list[i]=min_cost
      break
    cost_list[to]=large
  print(final_list)
  
print(sum(final_cost_list))