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:
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix

n, d = map(int, input().split())
a = [0] + list(map(int, input().split()))

row = []
col = []
cost = []
for i, e in enumerate(a[1:], 1):
    if i == 1:
        mn = a[i] - i * d
        mn_i = i

    else:
        row.append(i)
        col.append(mn_i)
        cost.append(a[i] + i * d + mn)

        if a[i] - i * d < mn:
            mn = a[i] - i * d
            mn_i = i

for i, e in enumerate(a[1:][::-1]):
    ri = n - i
    if ri == n:
        mn = a[ri] + ri * d
        mn_i = ri

    else:
        row.append(ri)
        col.append(mn_i)
        cost.append(a[ri] - ri * d + mn)

        if a[ri] + ri * d < mn:
            mn = a[ri] + ri * d
            mn_i = ri

g = csr_matrix((cost, (row, col)), shape=(n + 1, n + 1))
mst = minimum_spanning_tree(g).astype(int)
ans = mst.sum()
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 6)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if self.table[s1] > self.table[s2]:
			self.table[s2] = s1
			self.table[s1] -= 1
		else:
			self.table[s1] = s2
			self.table[s2] -= 1
		return

n, d = map(int, input().split())
a = list(map(int, input().split()))
uf = UnionFind(n)
cost_left_num = [x for x in a]
cost_left_id = [i for i in range(n)]
cost_right_num = [x for x in a]
cost_right_id = [i for i in range(n)]
limit_left = [i for i in range(n)]
limit_right = [i for i in range(n)]
q = []
for i in range(n-1):
	heappush(q, (a[i] + a[i+1])*(10**12) + i * (10**6) + i+1)

cnt = n
ans = 0
while cnt > 1:
	l = heappop(q)
	c = l // (10**12)
	i = (l - c * (10**12)) // (10**6)
	j = l % 10**6
	if uf.same(i, j):
		continue
	else:
		cnt -= 1
		x, y = uf.find(i), uf.find(j)
		#print(c, x, y)
		uf.unite(x, y)
		z = uf.find(x)
		ans += d + c
		limit_right[z] = limit_right[y]
		limit_left[z] = limit_left[x]

		if a[cost_left_id[x]] + d * (cost_left_id[x] - limit_left[z]) <= a[cost_left_id[y]] + d * (cost_left_id[y] - limit_left[z]):
			cost_left_num[z] = cost_left_num[x]
			cost_left_id[z] = cost_left_id[x]
		else:
			cost_left_num[z] = a[cost_left_id[y]] + d * (cost_left_id[y] - limit_left[z])
			cost_left_id[z] = cost_left_id[y]

		if a[cost_right_id[y]] + d * (limit_right[z] - cost_right_id[y]) <= a[cost_right_id[x]] + d * (limit_right[z] - cost_right_id[x]):
			cost_right_num[z] = cost_right_num[y]
			cost_right_id[z] = cost_right_id[y]
		else:
			cost_right_num[z] = a[cost_right_id[x]] + d * (limit_right[z] - cost_right_id[x])
			cost_right_id[z] = cost_right_id[x]

		if limit_left[z] > 0:
			w = uf.find(limit_left[z]-1)
			heappush(q, (cost_left_num[z] + cost_right_num[w]) * (10**12) + w * (10**6) + z)

		if limit_right[z] < n-1:
			w = uf.find(limit_right[z]+1)
			heappush(q, (cost_left_num[w] + cost_right_num[z]) * (10**12) + z * (10**6) + w)
		
		#print(*limit_left)
		#print(*limit_right)
		#print("-----")

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, D = map(int, input().split())
a = list(map(int, input().split()))
dl = [0] * N
dr = [0] * N
base = 10 ** 6
for i in range(N):
  dl[i] = ((N - i) * D + a[i]) * base + i
  dr[i] = (i * D + a[i]) * base + i
e = dd(list)
class SegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
lseg = SegTree(N, pow(10, 20), dl)
rseg = SegTree(N, pow(10, 20), dr)
for i in range(N):
  l = lseg.query(0, i)
  r = rseg.query(i + 1, N)
  e[i].append((l % base, a[i] + l // base - D * (N - i)))
  e[l % base].append((i, a[i] + l // base - D * (N - i)))
  e[i].append((r % base, a[i] + r // base - D * i))
  e[r % base].append((i, a[i] + r // base - D * i))
import heapq

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 6)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
#print(e)
pri = prim(N, e)
print(pri.MSTcost())

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, D = map(int, input().split())
a = list(map(int, input().split()))
dl = [0] * N
dr = [0] * N
base = 10 ** 6
for i in range(N):
  dl[i] = ((N - i) * D + a[i]) * base + i
  dr[i] = (i * D + a[i]) * base + i
e = dd(list)
class SegTree:
  def segfunc(self, x, y):
    return min(x, y)
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
lseg = SegTree(N, pow(10, 20), dl)
rseg = SegTree(N, pow(10, 20), dr)
for i in range(N):
  l = lseg.query(0, i)
  r = rseg.query(i + 1, N)
  e[i].append((l % base, a[i] + l // base - D * (N - i)))
  e[l % base].append((i, a[i] + l // base - D * (N - i)))
  e[i].append((r % base, a[i] + r // base - D * i))
  e[r % base].append((i, a[i] + r // base - D * i))
import heapq

class prim:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def MSTcost(self):
    h = []
    visited = [0] * (self.n + 1)
    ks = list(self.e.keys())
    b = pow(10, 16)
    for edge in self.e[ks[0]]:
      heapq.heappush(h, edge[1] * b + edge[0])
    res = 0
    visited[ks[0]] = 1
    while len(h):
      p = heapq.heappop(h)
      p0 = p // b
      p1 = p % b
      if visited[p1]: continue
      visited[p1] = 1
      for q in self.e[p1]:
        if visited[q[0]]:
          continue
        heapq.heappush(h, q[1] * b + q[0])
      res += p0
    return res
#print(e)
pri = prim(N, e)
print(pri.MSTcost())

Submission status: Wrong Answer

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

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index:
                index = index >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L < R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                #self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

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

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = defaultdict(int)
    val2idx_minus = defaultdict(lambda: N+3)
    edge_append = edge.append
    inf = 10**15
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        i_ori = val2idx_plus[val_plus]
        if i > i_ori:
            val2idx_plus[val_plus] = i
        i_ori = val2idx_minus[val_minus]
        if i < i_ori:
            val2idx_minus[val_minus] = i
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < inf:
            j_plus = val2idx_plus[plus_min]
            edge_append((i, j_plus, A[i-1] + A[j_plus-1] + D*(j_plus - i)))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < inf:
            j_minus = val2idx_minus[minus_min]
            edge_append((i, j_minus, A[i-1] + A[j_minus-1] + D * (i - j_minus)))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    from heapq import heappush, heappop
    input = sys.stdin.buffer.readline

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

    class SegTree():
        def __init__(self, N):
            # N:  処理する区間の長さ
            self.N0 = 2 ** (N - 1).bit_length()
            self.INF = 10**15
            self.seg_min = [self.INF] * (2 * self.N0)

        def update(self, index, value):
            index += self.N0 - 1
            self.seg_min[index] = value
            while index > 0:
                index = (index - 1) >> 1
                L = self.seg_min[index * 2 + 1]
                R = self.seg_min[index * 2 + 2]
                if L < R:
                    self.seg_min[index] = L
                else:
                    self.seg_min[index] = R
                #self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

        def query(self, first, last):
            first += self.N0 - 1
            last += self.N0 - 1
            ret = self.INF
            while first <= last:
                if not first & 1:
                    ret_new = self.seg_min[first]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[first])
                if last & 1:
                    ret_new = self.seg_min[last]
                    if ret_new < ret:
                        ret = ret_new
                    #ret = min(ret, self.seg_min[last])
                first = first >> 1
                last = (last >> 1) - 1
            return ret

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

    tmp = [(a, i+1) for i, a in enumerate(A)]
    tmp.sort(key=lambda x: x[0])
    segtree_plus = SegTree(N+5)
    segtree_minus = SegTree(N+5)
    edge = []
    val2idx_plus = {}
    val2idx_minus = {}
    for a, i in tmp:
        val_plus = a+D*i
        val_minus = a-D*i
        segtree_plus.update(i, val_plus)
        segtree_minus.update(i, val_minus)
        if val_plus not in val2idx_plus:
            val2idx_plus[val_plus] = i
        else:
            i_ori = val2idx_plus[val_plus]
            if i > i_ori:
                val2idx_plus[val_plus] = i
        if val_minus not in val2idx_minus:
            val2idx_minus[val_minus] = i
        else:
            i_ori = val2idx_minus[val_minus]
            if i < i_ori:
                val2idx_minus[val_minus] = i
        plus_min = segtree_plus.query(i+1, N+2)
        if plus_min < 10**15:
            j_plus = val2idx_plus[plus_min]
            heappush(edge, (A[i-1] + A[j_plus-1] + D*(j_plus - i), i, j_plus))
        minus_min = segtree_minus.query(1, i-1)
        if minus_min < 10 ** 15:
            j_minus = val2idx_minus[minus_min]
            heappush(edge, (A[i-1] + A[j_minus-1] + D * (i - j_minus), i, j_minus))

    #edge.sort(key=lambda x: x[2])
    UF = UnionFind(N + 1)
    ans = 0
    while edge:
        cost, u, v = heappop(edge)
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
        print(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.root = [-1] * (n + 1)
            self.rnk = [0] * (n + 1)

        def find_root(self, x):
            if self.root[x] < 0:
                return x
            else:
                self.root[x] = self.find_root(self.root[x])
                return self.root[x]

        def unite(self, x, y):
            x = self.find_root(x)
            y = self.find_root(y)
            if x == y:
                return
            elif self.rnk[x] > self.rnk[y]:
                self.root[x] += self.root[y]
                self.root[y] = x
            else:
                self.root[y] += self.root[x]
                self.root[x] = y
                if self.rnk[x] == self.rnk[y]:
                    self.rnk[y] += 1

        def isSameGroup(self, x, y):
            return self.find_root(x) == self.find_root(y)

        def size(self, x):
            return -self.root[self.find_root(x)]

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

    A_plus = [0] * N
    A_minus = [0] * N
    for i in range(N):
        A_plus[i] = A[i] + D*i
        A_minus[i] = A[i] - D*i

    edge = []
    m = float('inf')
    m_idx = 0
    for i in range(N-1):
        if A_minus[i] < m:
            m = A_minus[i]
            m_idx = i
        edge.append((m_idx+1, i+2, A_plus[i+1] + A_minus[m_idx]))
    m = float('inf')
    m_idx = 0
    for i in range(N-1, 0, -1):
        if A_plus[i] < m:
            m = A_plus[i]
            m_idx = i
        edge.append((m_idx+1, i, A_plus[m_idx] + A_minus[i-1]))

    edge.sort(key=lambda x: x[2])
    UF = UnionFind(N+1)
    ans = 0
    for u, v, cost in edge:
        if UF.isSameGroup(u, v):
            continue
        ans += cost
        UF.unite(u, v)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,d = LI()
    a = LI()
    b = [a[i]+d*i for i in range(n)]
    mb = [[None]*2 for i in range(n)]
    mb[n-1][0] = b[n-1]
    mb[n-1][1] = n-1
    for i in range(n-1)[::-1]:
        if b[i] < mb[i+1][0]:
            mb[i][0] = b[i]
            mb[i][1] = i
        else:
            mb[i][0] = mb[i+1][0]
            mb[i][1] = mb[i+1][1]
    a = [a[i]-d*i for i in range(n)]
    ma = [[None]*2 for i in range(n)]
    ma[0][0] = a[0]
    ma[0][1] = 0
    for i in range(n-1):
        if a[i+1] < ma[i][0]:
            ma[i+1][0] = a[i+1]
            ma[i+1][1] = i+1
        else:
            ma[i+1][0] = ma[i][0]
            ma[i+1][1] = ma[i][1]
    par = [i for i in range(n)]
    rank = [0]*n
    q = []
    for i in range(n):
        if i < n-1:
            q.append((a[i]+mb[i+1][0],i,mb[i+1][1]))
        if i > 0:
            q.append((b[i]+ma[i-1][0],i,ma[i-1][1]))
    q.sort()
    ans = 0
    k = 0
    for nd,x,y in q:
        if root(x) != root(y):
            k += 1
            unite(x,y)
            ans += nd
            if k == n-1:
                break
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,d = LI()
    a = LI()
    b = [a[i]+d*i for i in range(n)]
    mb = [[None]*2 for i in range(n)]
    mb[n-1][0] = b[n-1]
    mb[n-1][1] = n-1
    for i in range(n-1)[::-1]:
        if b[i] < mb[i+1][0]:
            mb[i][0] = b[i]
            mb[i][1] = i
        else:
            mb[i][0] = mb[i+1][0]
            mb[i][1] = mb[i+1][1]
    a = [a[i]-d*i for i in range(n)]
    ma = [[None]*2 for i in range(n)]
    ma[0][0] = a[0]
    ma[0][1] = 0
    for i in range(n-1):
        if a[i+1] < ma[i][0]:
            ma[i+1][0] = a[i+1]
            ma[i+1][1] = i+1
        else:
            ma[i+1][0] = ma[i][0]
            ma[i+1][1] = ma[i][1]
    par = [i for i in range(n)]
    rank = [0]*n
    q = []
    for i in range(n):
        if i < n-1:
            q.append((a[i]+mb[i+1][0],i,mb[i+1][1]))
        if i > 0:
            q.append((b[i]+ma[i-1][0],i,ma[i-1][1]))
    q.sort()
    ans = 0
    k = 0
    for nd,x,y in q:
        if root(x) != root(y):
            k += 1
            unite(x,y)
            ans += nd
            if k == n-1:
                break
    else:
        print(ans/0)
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,d = LI()
    a = LI()
    b = [a[i]+d*i for i in range(n)]
    mb = [[None]*2 for i in range(n)]
    mb[n-1][0] = b[n-1]
    mb[n-1][1] = n-1
    for i in range(n-1)[::-1]:
        if b[i] < mb[i+1][0]:
            mb[i][0] = b[i]
            mb[i][1] = i
        else:
            mb[i][0] = mb[i+1][0]
            mb[i][1] = mb[i+1][1]
    a = [a[i]-d*i for i in range(n)]
    ma = [[None]*2 for i in range(n)]
    ma[0][0] = a[0]
    ma[0][1] = 0
    for i in range(n-1):
        if a[i+1] < ma[i][0]:
            ma[i+1][0] = a[i+1]
            ma[i+1][1] = i+1
        else:
            ma[i+1][0] = ma[i][0]
            ma[i+1][1] = ma[i][1]
    par = [i for i in range(n)]
    rank = [0]*n
    q = []
    for i in range(n):
        if i < n-1:
            q.append((a[i]+mb[i+1][0],i,mb[i+1][1]))
        if i > 0:
            q.append((b[i]+ma[i-1][0],i,ma[i-1][1]))
    q.sort()
    ans = 0
    k = 0
    for nd,x,y in q:
        if root(x) != root(y):
            k += 1
            unite(x,y)
            ans += nd
            if k == n-1:
                break
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    n,d = LI()
    a = LI()
    b = [a[i]+d*i for i in range(n)]
    mb = [[None]*2 for i in range(n)]
    mb[n-1][0] = b[n-1]
    mb[n-1][1] = n-1
    for i in range(n-1)[::-1]:
        if b[i] < mb[i+1][0]:
            mb[i][0] = b[i]
            mb[i][1] = i
        else:
            mb[i][0] = mb[i+1][0]
            mb[i][1] = mb[i+1][1]
    a = [a[i]-d*i for i in range(n)]
    ma = [[None]*2 for i in range(n)]
    ma[0][0] = a[0]
    ma[0][1] = 0
    for i in range(n-1):
        if a[i+1] < ma[i][0]:
            ma[i+1][0] = a[i+1]
            ma[i+1][1] = i+1
        else:
            ma[i+1][0] = ma[i][0]
            ma[i+1][1] = ma[i][1]
    par = [i for i in range(n)]
    rank = [0]*n
    q = []
    for i in range(n):
        if i < n-1:
            q.append((a[i]+mb[i+1][0],i,mb[i+1][1]))
        if i > 0:
            q.append((b[i]+ma[i-1][0],i,ma[i-1][1]))
    q.sort()
    ans = 0
    for nd,x,y in q:
        if root(x) != root(y):
            unite(x,y)
            ans += nd
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N,D=map(int,input().split())
alist=list(map(int,input().split()))

tree_flg=[False]*N

all_dist = 0
for i in range(N):
  if tree_flg[i]:
    continue
    
  min_dist=10**15
  min_index=-1
  for j in range(N):
    if i==j:
      continue
    if min_dist > abs(j-i)*D+alist[i]+alist[j]:
      min_dist = abs(j-i)*D+alist[i]+alist[j]
      min_index = j
    #if min_dist<(j-i)*D+alist[i]+1:
    #  break
   
  all_dist += min_dist
  tree_flg[i]=True
  tree_flg[min_index]=True
  #print("{} {} {}".format(i,min_index,min_dist))
  
print(all_dist)