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: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(200000)
def main():
    input = sys.stdin.readline
    #n = int(input())
    n,d = map(int,input().split())
    a = list(map(int,input().split()))
    ans = 0
    kore = []
    class UnionFind():
        def __init__(self,size):
            self.table = [-1 for _  in range(size)]
        def find(self,x):
            while self.table[x] >= 0:
                x = self.table[x]
            return x
    
        def union(self,x,y):
            s1 = self.find(x)
            s2 = self.find(y)
            if s1 != s2:
                if self.table[s1] != self.table[s2]:
                    if self.table[s1] < self.table[s2]:
                        self.table[s2] = s1
                    else:
                        self.table[s1] = s2
                else:
                    self.table[s1] += -1
                    self.table[s2] = s1
            return

    N0 = 2**(n).bit_length()
    INF = (2**31-1)
    data = [[INF]*4 for i in range(2*N0)]
    def update(k, x,y,z):
        k += N0-1
        data[k] = [x,z,y,z]
        while k >= 0:
            k = (k - 1) // 2
            if data[2*k+1][0] > data[2*k+2][0]:
                data[k][:2] =  data[2*k+2][:2]
            else:
                data[k][:2] =  data[2*k+1][:2]
            if data[2*k+1][2] > data[2*k+2][2]:
                data[k][2:] =  data[2*k+2][2:]
            else:
                data[k][2:] =  data[2*k+1][2:]
    def query(l, r,z):
        L = l + N0; R = r + N0
        s = [INF,INF]
        while L < R:
            if R & 1:
                R -= 1
                if s[0] > data[R-1][z*2]:
                    s = data[R-1][z*2:z*2+2]
    
            if L & 1:
                if s[0] > data[L-1][z*2]:
                    s = data[L-1][z*2:z*2+2]
                L += 1
            L >>= 1; R >>= 1
        return s
    b = []
    for i in range(n):
        b.append([a[i],i])
    b.sort()
    kimeta = UnionFind(n)
    for i in range(n):
        c = b[i]
        hidari = query(0,c[1],0)
        migi = query(c[1],n,1)
        if hidari[1] != INF:
            kore.append([a[hidari[1]]+c[0]+d*abs(c[1]-hidari[1]),c[1],hidari[1]])
        if migi[1] != INF:
            kore.append([a[migi[1]]+c[0]+d*abs(migi[1]-c[1]),c[1],migi[1]])
        update(c[1],c[0]+d*(n-c[1]),d*c[1]+c[0],c[1])  
    kore.sort()
    bpoint = 0
    for i,j,k in kore:
        if kimeta.find(j) != kimeta.find(k):
            kimeta.union(j,k)
            ans += i
            bpoint += 1
        if bpoint >= n-1:
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
#n = int(input())
n,d = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
kore = []
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return

N0 = 2**(n).bit_length()
INF = (2**31-1)
data = [[INF]*4 for i in range(2*N0)]
def update(k, x,y,z):
    k += N0-1
    data[k] = [x,z,y,z]
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1][0] > data[2*k+2][0]:
            data[k][:2] =  data[2*k+2][:2]
        else:
            data[k][:2] =  data[2*k+1][:2]
        if data[2*k+1][2] > data[2*k+2][2]:
            data[k][2:] =  data[2*k+2][2:]
        else:
            data[k][2:] =  data[2*k+1][2:]
def query(l, r,z):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            if s[0] > data[R-1][z*2]:
                s = data[R-1][z*2:z*2+2]
 
        if L & 1:
            if s[0] > data[L-1][z*2]:
                s = data[L-1][z*2:z*2+2]
            L += 1
        L >>= 1; R >>= 1
    return s
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
kimeta = UnionFind(n)
for i in range(n):
    c = b[i]
    hidari = query(0,c[1],0)
    migi = query(c[1],n,1)
    if hidari[1] != INF:
        kore.append([a[hidari[1]]+c[0]+d*abs(c[1]-hidari[1]),c[1],hidari[1]])
    if migi[1] != INF:
        kore.append([a[migi[1]]+c[0]+d*abs(migi[1]-c[1]),c[1],migi[1]])
    update(c[1],c[0]+d*(n-c[1]),d*c[1]+c[0],c[1])  
kore.sort()
for i,j,k in kore:
    if kimeta.find(j) != kimeta.find(k):
        kimeta.union(j,k)
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [(sys.maxsize, -1)] * (self.__N * 2 - 1)

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            if self.__table[i][0] < self.__table[pi][0]:
                self.__table[pi] = self.__table[i]
            else:
                break
            i = pi

    def __query(self, a, b, k, l, r):
        ans = sys.maxsize
        if r <= a or b <= l:
            return (sys.maxsize, -1)
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return min(vl, vr, key=lambda x: x[0])

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)

def Prim(g):
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v.keys()))
    V = list(set(V))

    used = set([])
    q = []
    heapq.heappush(q, (0, V[0]))

    ret = 0
    while q:
        c, v = heapq.heappop(q)

        if v in used:
            continue
        used.add(v)
        ret += c
        for u in g[v]:
            heapq.heappush(q, (g[v][u], u))
    return ret

@mt
def slv(N, D, A):
    ans = 0
    AA = [(a, i) for i, a in enumerate(A)]
    AA.sort()

    st_l = SegmentTree(N)
    st_r = SegmentTree(N)
    g = defaultdict(dict)
    for a, i in AA:
        
        l = st_l.query(0, i)
        r = st_r.query(i, N)
        if l[1] != -1:
            j = l[1]
            g[i][j] = D*(abs(i-j))+A[i]+A[j]
            g[j][i] = g[i][j]
        if r[1] != -1:
            j = r[1]
            g[i][j] = D*(abs(i-j))+A[i]+A[j]
            g[j][i] = g[i][j]
        st_r.update(i, (D*i+a,i))
        st_l.update(i, (D*(N-i)+a,i))


    return Prim(g)


def main():
    N, D = read_int_n()
    A = read_int_n()

    print(slv(N, D, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
#n = int(input())
n,d = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
kore = []
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return

N0 = 2**(n).bit_length()
INF = (2**31-1)
data = [[INF]*2 for i in range(2*N0)]
data2 = [[INF]*2 for i in range(2*N0)]
def update(k, x,y):
    k += N0-1
    data[k] = [x,y]
    while k >= 0:
        k = (k - 1) // 2
        if data[2*k+1][0] > data[2*k+2][0]:
            data[k] =  data[2*k+2]
        else:
            data[k] =  data[2*k+1]
def query(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            if s[0] > data[R-1][0]:
                s = data[R-1]
 
        if L & 1:
            if s[0] > data[L-1][0]:
                s = data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s
def update2(k, x,y):
    k += N0-1
    data2[k] = [x,y]
    while k >= 0:
        k = (k - 1) // 2
        if data2[2*k+1][0] > data2[2*k+2][0]:
            data2[k] =  data2[2*k+2]
        else:
            data2[k] =  data2[2*k+1]
def query2(l, r):
    L = l + N0; R = r + N0
    s = [INF,INF]
    while L < R:
        if R & 1:
            R -= 1
            if s[0] > data2[R-1][0]:
                s = data2[R-1]
 
        if L & 1:
            if s[0] > data2[L-1][0]:
                s = data2[L-1]
            L += 1
        L >>= 1; R >>= 1
    return s
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
kimeta = UnionFind(n)
for i in range(n):
    c = b[i]
    hidari = query(0,c[1])
    migi = query2(c[1],n)
    if hidari[1] != INF:
        kore.append([a[hidari[1]]+c[0]+d*abs(c[1]-hidari[1]),c[1],hidari[1]])
    if migi[1] != INF:
        kore.append([a[migi[1]]+c[0]+d*abs(migi[1]-c[1]),c[1],migi[1]])
    update(c[1],c[0]+d*(n-c[1]),c[1])
    update2(c[1],c[0]+d*c[1],c[1])    
kore.sort()
for i,j,k in kore:
    if kimeta.find(j) != kimeta.find(k):
        kimeta.union(j,k)
        ans += i
print(ans)

Submission status: Time Limit Exceeded

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))
    matrix = [[0]*Num for i in range(Num)]

    for i in range(Num):
        # ai = np.empty(Num)
        ai = [0]*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 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]:
                    if matrix[i][j] >= matrix[j][k] and matrix[i][j] >= matrix[i][k]:
                        # ResultMatrix[i,j] = 0
                        ResultMatrix[i][j] = 0
                    # elif matrix[j,k] > matrix[i,j] and matrix[j,k] >= matrix[i,k]:
                    elif matrix[j][k] > matrix[i][j] and matrix[j][k] >= matrix[i][k]:
                        # ResultMatrix[j,k] = 0
                        ResultMatrix[j][k] = 0
                    # elif matrix[i,k] > matrix[i,j] and matrix[i,k] > matrix[j,k]:
                    elif matrix[i][k] > matrix[i][j] and matrix[i][k] > matrix[j][k]:
                        # ResultMatrix[i,k] = 0
                        ResultMatrix[i][k] = 0
    # if np.sum(ResultMatrix != matrix) != 0:
    if ResultMatrix != matrix:
        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)
Amount = [sum(_) for _ in AnswerMatrix]
Amount = sum(Amount)
print(int(Amount))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import numpy as np
import heapq

def solve():
    N, D = map(int,input().split())
    A = np.array([0]+list(map(int,input().split())))
    V0 = set(range(1,N+1))
    V = {1,}
    C = 0
    E = list()
    i = 1
    for j in V0-V:
        heapq.heappush(E,(abs(j-i)*D + A[i] + A[j], (i,j)))
    heapq.heapify(E)
    while len(V) < N:
        e = heapq.heappop(E)
        if len(set(e[1])&V) == 1:
            i = (set(e[1])-V).pop()
            V |= set(e[1])
            C += e[0]
            for j in V0-V:
                heapq.heappush(E,(abs(j-i)*D + A[i] + A[j], (i,j)))
    res = C
    return str(res)

if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections
import heapq


AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
INF = 2 ** 31 - 1
NO_VERTEX = -1


# Prim法で頂点0からの最小全域木を求める
def compute_mst_prim(max_v, adj_list):
    # pred[u]は頂点uの「ひとつ前」の頂点を表す
    pred = collections.defaultdict(lambda: NO_VERTEX)
    # uとpred[u]を結ぶ辺の重みがkey[u]に入る
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    # 二分ヒープを優先度付きキューとして用いる
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    # 優先度付きキューに頂点が入っているかを示す配列
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


def main():
    adjacency_list = collections.defaultdict(set)
    max_v, D = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))
    edges = []
    for i, Ai in enumerate(A):
        for j, Aj in enumerate(A):
            if j > i:
                w = (j-i)*D + Ai + Aj
                adjacency_list[j].add(AdjacentVertex(i, w))
                adjacency_list[i].add(AdjacentVertex(j, w))


    (_, key) = compute_mst_prim(max_v, adjacency_list)
    print(sum(key.values()))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
NM = raw_input().split()
NM = [int(x) for x in NM]
N = NM[0]
D = NM[1]
a_list = raw_input().split()
a_list = [int(x) for x in a_list]
place_attended = set([0])
place_not_attended = set(range(1, N))
sum_cost = 0
while len(place_attended) < N:
    min_idx = -1
    min_cost = -1
    for i in place_attended:
        for j in place_not_attended:
            cur_cost = abs(i-j) * D + a_list[i] + a_list[j]
            if min_cost < 0 or cur_cost < min_cost:
                min_cost = cur_cost
                min_idx = j
    sum_cost += min_cost
    place_attended.add(min_idx)
    place_not_attended.remove(min_idx)
print sum_cost

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
def input(): return sys.stdin.readline()
from collections import defaultdict
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return
def f(nb, nc):
    if nb != N-1:
        return (nb+1, nc)
    return 0
def g(nb, nc):
    if nc != N-1:
        return (nb, nc+1)
    return 0
def inpl(): return [int(i) for i in input().split()]

N, D = inpl()
A = inpl()
B = [(i*D + v, i) for i, v in enumerate(A, 1)]
C = [(-i*D + v, i) for i, v in enumerate(A, 1)]
B.sort()
C.sort()
Z = UnionFind(N+1)
Q = []
ctr = 0
ans = 0
H = defaultdict(lambda: False)
heapq.heappush(Q, (C[0][0] + B[0][0], (0, 0)))
H[(0, 0)] = True
H[0] = True
while ctr < N-1:
    v, (bi, ci) = heapq.heappop(Q)
    _, bj = B[bi]
    _, cj = C[ci]
    if not H[f(bi, ci)]:
        H[(bi+1, ci)] = True
        heapq.heappush(Q, (B[bi+1][0] + C[ci][0], (bi+1, ci)))
    if not H[g(bi, ci)]:
        H[(bi, ci+1)] = True
        heapq.heappush(Q, (B[bi][0] + C[ci+1][0], (bi, ci+1)))
    if bj <= cj:
        continue
    if Z.find(bj) == Z.find(cj):
        continue
    Z.union(bj, cj)
    ans += v
    ctr += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return
def f(nb, nc):
    if nb != N-1:
        return (nb+1, nc)
    return 0
def g(nb, nc):
    if nc != N-1:
        return (nb, nc+1)
    return 0
def inpl(): return [int(i) for i in input().split()]

N, D = inpl()
A = inpl()
B = [(i*D + v, i) for i, v in enumerate(A, 1)]
C = [(-i*D + v, i) for i, v in enumerate(A, 1)]
B.sort()
C.sort()
Z = UnionFind(N+1)
Q = []
ctr = 0
ans = 0
H = defaultdict(lambda: False)
heapq.heappush(Q, (C[0][0] + B[0][0], (0, 0)))
H[(0, 0)] = True
H[0] = True
while ctr < N-1:
    v, (bi, ci) = heapq.heappop(Q)
    _, bj = B[bi]
    _, cj = C[ci]
    if not H[f(bi, ci)]:
        H[(bi+1, ci)] = True
        heapq.heappush(Q, (B[bi+1][0] + C[ci][0], (bi+1, ci)))
    if not H[g(bi, ci)]:
        H[(bi, ci+1)] = True
        heapq.heappush(Q, (B[bi][0] + C[ci+1][0], (bi, ci+1)))
    if bj <= cj:
        continue
    if Z.find(bj) == Z.find(cj):
        continue
    Z.union(bj, cj)
    ans += v
    ctr += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
#sys.setrecursionlimit(200000)
input = sys.stdin.readline
#n = int(input())
n,d = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
kore = []
class UnionFind():
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]
    def find(self,x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                self.table[s1] += -1
                self.table[s2] = s1
        return
kimeta = UnionFind(n)
for i in range(n):
    if i > 0:
        kore.append([a[i] + d+a[i-1],i-1,i])
    if i < n-1:
        kore.append([a[i] + d+a[i+1],i+1,i])
    for j in range(i+2,n):
        if a[i] + (j-i)*d < a[j-1]+d:
            kore.append([a[i] + (j-i)*d+a[j],j,i])
    for j in range(i-2,-1,-1):
        if a[i] + (i-j)*d < a[j+1]+d:
            kore.append([a[i] + (i-j)*d+a[j],j,i])
kore.sort()
for i,j,k in kore:
    if kimeta.find(j) != kimeta.find(k):
        kimeta.union(j,k)
        ans += i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
NM = raw_input().split()
NM = [int(x) for x in NM]
N = NM[0]
D = NM[1]
a_list = raw_input().split()
a_list = [int(x) for x in a_list]
place_attended = [0]
place_not_attended = range(1, N)
sum_cost = 0
while len(place_attended) < N:
    min_idx = -1
    min_cost = -1
    for i in place_attended:
        for j in place_not_attended:
            cur_cost = abs(i-j) * D + a_list[i] + a_list[j]
            if min_cost < 0 or cur_cost < min_cost:
                min_cost = cur_cost
                min_idx = j
    sum_cost += min_cost
    place_attended.append(min_idx)
    place_not_attended.remove(min_idx)
print sum_cost

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
import collections


Edge = collections.namedtuple("Edge", "start end weight")


class UnionFind(object):

    def __init__(self, number_of_nodes):  # 初期化
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for i in range(number_of_nodes)))

    def root(self, node):  # 根を求める
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r  # 経路圧縮
            return r

    def in_the_same_set(self, node1, node2):  # 同じ集合に属するか
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):  # 属する集合を併合
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


# Kruskal法により最小全域木を求める
def compute_mst_kruskal(max_v, edges):
    edges.sort(key=lambda edge: edge.weight)
    uf = UnionFind(max_v)
    mst = []
    for edge in edges:
        if not uf.in_the_same_set(edge.start, edge.end):
            uf.unite(edge.start, edge.end)
            mst.append(edge)
    return mst


def main():
    N, D = map(int, input().split(' '))
    A = list(map(int, input().split(' ')))
    edges = []
    for i, Ai in enumerate(A):
        for j, Aj in enumerate(A):
            if j > i:
                edges.append(Edge(i, j, (j-i)*D + Ai + Aj))

    mst = compute_mst_kruskal(N, edges)
    print(sum(edge.weight for edge in mst))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def abs(n):
    if n<0:
        return -n
    else:
        return n

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

cost=[[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        if i!=j:
            cost[i][j]=abs(i-j)*d+a[i]+a[j]

edge=[]
for i in range(n):
    for j in range(n):
        edge.append((cost[i][j],i,j))
edge.sort()

class UnionFind():
    def __init__(self,n):
        self.par=[i for i in range(n)]
        self.rank=[0 for i in range(n)]
    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 unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same(self,x,y):
        return self.find(x)==self.find(y)

t=UnionFind(n)
res=0
for e in edge:
    cost=e[0]
    v=e[1]
    u=e[2]

    if not t.same(v,u):
        #print(v,u,cost)
        #print('par['+str(v)+']=',t.find(v),'par['+str(u)+']=',t.find(u))
        t.unite(v,u)
        res+=cost

print(res)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop, heapify
from collections import defaultdict

"""
・最小値のある場所を調べる。左右にまたがる辺は結ばない。
・最小値の両隣は必ず最小値と結ぶ。
・結んだあと1点に縮約していく。
"""

N,D,*A = map(int,read().split())

A = [0] + A + [0] # 番兵

# (value<<32) + (index)
mask = (1<<32)-1
q = [(x<<32)+i for i,x in enumerate(A[1:-1],1)]
heapify(q)
removed = defaultdict(int)

cost = []
while q:
    while q:
        x = q[0]
        if not removed[x]:
            break
        heappop(q); removed[x] -= 1
    if not q:
        break
    x = heappop(q)
    val,ind = x>>32, x&mask
    L = A[ind-1]; R = A[ind+1]
    if L:
        cost.append(L+val+D)
        # Lの値を書き換える
        newL = val+D
        if L > newL:
            A[ind-1] = newL
            removed[(L<<32)+(ind-1)] += 1
            heappush(q,(newL<<32)+(ind-1))
    if R:
        cost.append(R+val+D)
        # Lの値を書き換える
        newR = val+D
        if R > newR:
            A[ind+1] = newR
            removed[(R<<32)+(ind+1)] += 1
            heappush(q,(newR<<32)+(ind+1))
    A[ind] = 0

answer = sum(cost)
print(answer)

Submission status: Accepted

Solution code:
from operator import itemgetter
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if x == y:
        return float('inf')
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(map(itemgetter(1), itertools.accumulate(Right, min)))
Left = list(map(itemgetter(1), itertools.accumulate(Left, min)))[::-1]
ans = 0
hub = []
for i, (l, r) in enumerate(zip(Left, Right)) :
    if i == l == r:
        hub.append(i)
    else:
        ans += min(cost(i, r), cost(i, l))
print(ans + sum([cost(i, j) for i, j in zip(hub, hub[1:])]))

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import itemgetter

n, d = map(int, input().split())
aaa = list(map(int, input().split()))
costs_l = [(-i * d + a, i) for i, a in enumerate(aaa)]
costs_r = [(i * d + a, i) for i, a in enumerate(aaa)]

costs_l = list(accumulate(costs_l, min))
costs_r = list(accumulate(reversed(costs_r), min))
costs_r.reverse()

hubs = set(map(itemgetter(1), costs_l))
hubs.intersection_update(map(itemgetter(1), costs_r))
hubs.add(0)
hubs.add(n - 1)
hubs = sorted(hubs)

ans = sum(aaa) - aaa[-1]
s = hubs[0]
for t in hubs[1:]:
    cls = costs_l[s][0]
    crt = costs_r[t][0]
    ans += crt - s * d
    ans += sum(min(cls + i * d, crt - i * d) for i in range(s + 1, t))
    s = t
print(ans)

Submission status: Accepted

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[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)