Problem:


Score : 500 points

Problem Statement

There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
right = 0
left = n-1
stay = []
l = []
ans = 0
for i in range(n):
    l.append([a[i],i])
l.sort(reverse=True)
for i in range(n):
    l0 = 0
    r0 = 0
    for j in range(l[i][1]-1):
        r0 = max(r0,a[j])
    for j in range(l[i][1]+1,n):
        l0 = max(l0,a[j])
    r0 = l[i][0] - r0
    l0 = l[i][0] - l0
    #print(l0,r0)
    if len(stay) == 0:
        if (left - l[i][1])*r0 > (l[i][1] - right)*l0:
            ans += l[i][0]*(left - l[i][1])
            left -= 1
        elif (left - l[i][1])*r0 < (l[i][1] - right)*l0:
            ans += l[i][0]*(l[i][1]-right)
            right += 1
        else:
            stay.append(l[i])
        a[l[i][1]] = 0
    else:
        k = len(stay)
        if (left - l[i][1]-k//2)*r0 > (l[i][1] - right - k//2)*l0:
            for j in range(k):
                if j % 2 == 0:
                    ans += (stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0]
                    right += 1
                else:
                    ans += (left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0]
                    left -= 1
            ans += l[i][0]*(left - l[i][1])
            left -= 1
            stay = []
        elif (left - l[i][1] - k//2)*r0 < (l[i][1] - right - k//2)*l0:
            for j in range(k):
                if j % 2 == 1:
                    ans += abs((stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0])
                    right += 1
                else:
                    ans += abs((left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0])
                    left -= 1
            ans += l[i][0]*(l[i][1]-right)
            right += 1
            stay = []
        else:
            stay.append(l[i])
        a[l[i][1]] = 0
    #print(stay,ans)
if len(stay) > 0:
    k = len(stay)
    for j in range(k):
        if j % 2 == 0:
            ans += abs((stay[k-1-j][1] - right - k//2+j)*stay[k-1-j][0])
            right += 1
        else:
            ans += abs((left - stay[k-1-j][1]-k//2 + j)*stay[k-1-j][0])
            left -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A_ans, ori, ans = [A[0]], [0], 0

def switch(i, a):
    gain, index = 0, i
    for j in range(i):
        temp = A_ans[j]*((i - ori[j]) - abs(j - ori[j])) + a*(i - j)
        if gain < temp:
            gain, index = temp, j
    return index, gain

def push_away(i, a):
    gain = [0]
    for j in range(1, i+1):
        gain.append(a + gain[j-1])
        k = i - j
        gain[j] += (2 * int(ori[k] < k + 1) - 1) * A_ans[k]
    index = gain.index(max(gain))

    return index, gain[index]

for i in range(1, N):
    a = A[i]
    i_s, g_s = switch(i, a)
    i_p, g_p = push_away(i, a)

    if g_s > g_p:
        ans += g_s
        A_ans.append(A_ans[i_s])
        A_ans[i_s] = a
        ori.append(ori[i_s])
        ori[i_s] = i
    else:
        ans += g_p        
        index = i - i_p
        A_ans = A_ans[:index] + [a] + A_ans[index:]
        ori = ori[:index] + [i] + ori[index:]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N = ii()
A = lmii()

scoret = set()

for i in range(N):
    for j in range(N):
        scoret.add((i, j, A[i] * abs(i-j)))

scoret = list(scoret)
scoret.sort(key=lambda x: -x[2])
done_s = set()
done_t = set()
ans = 0
cnt = 0
for s, t, score in scoret:
    if cnt == N:
        break
    if s in done_s or t in done_t:
        continue
    ans += score
    done_s.add(s)
    done_t.add(t)
    cnt += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,*a = map(int,open(0).read().split())
a = list(zip(a,range(n)))
m = n // 2
ans = 0
l = n//3
for j in range(m-l,m+l+1):
  a1 = sorted(a[j:n],key=lambda x:x[0],reverse=True)+sorted(a[0:j],key=lambda x:x[0])
  ans = max(ans,sum([a1[i][0]*abs(i-a1[i][1]) for i in range(n)]))
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

n=int(input())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  for j in range(n):
    heapq.heappush(q,(-arr[j]*abs(j-i),i,j))
ans=0
cnt=0
checked1=set()
checked2=set()
while 1:
  val,i,j=heapq.heappop(q)
  if i not in checked1 and j not in checked2:
    checked1.add(i)
    checked2.add(j)
    ans-=val
    cnt+=1
  if cnt==n:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
n =int(input())
l = list(map(int,input().split()))
dp = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        dp[i][j] = l[j]*abs(i-j)
idone = {}
jdone = {}
got = 0
ans = 0
while got<n:
    local = 0
    for i in range(n):
        for j in range(n):
            if i not in idone and j not in jdone:
                if local<dp[i][j]:
                    ido = i
                    jdo = j
                    local = dp[i][j]
    idone[ido] = 1
    jdone[jdo] = 1
    ans += local
    got += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
IA = [(i, a) for i, a in enumerate(map(int, input().split()))]

Submission status: Wrong Answer

Solution code:
import heapq
n=int(input())
arr=list(map(int,input().split()))
q=[]
for i in range(n):
  for j in range(n):
    heapq.heappush(q,(-arr[j]*abs(j-i),i,j))
ans=0
cnt=0
checked1=set()
checked2=set()
while 1:
  val,i,j=heapq.heappop(q)
  if i not in checked1 and j not in checked2:
    checked1.add(i)
    checked2.add(j)
    ans-=val
    cnt+=1
  if cnt==n:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N = ii()
A = lmii()

scoret = set()

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        scoret.add((i, j, A[i] * abs(i-j)))

scoret = list(scoret)
scoret.sort(key=lambda x: -x[2])
done_s = set()
done_t = set()
ans = 0
cnt = 0
for s, t, score in scoret:
    if cnt == N:
        break
    if s in done_s or t in done_t:
        continue
    ans += score
    done_s.add(s)
    done_t.add(t)
    cnt += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = [(i+1, x) for i, x in enumerate(map(int, input().split()))]
R = 0
for i in range(1, N):
    A, B = X[:i], X[i:]
#    print(A, B)
    A = sorted(A, key=lambda x: x[1])[::-1]
    B = sorted(B, key=lambda x: x[1])[::-1]
    r = 0
    for i in range(len(A)):
        j, x = A[i]
        r += x*abs(N-i-j)
    for i in range(len(B)):
        j, x = B[i]
        r += x*abs(j-(i+1))
    R = max(R, r)

print(R)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
for i,a in enumerate(map(int,input().split())):
  A.append([a,i])
A=sorted(A,key=lambda x:x[0], reverse=True)
r,l=0,N-1
ans=0
for a,i in A:
  if (l+r)//2<=i:
    ans+=a*(i-r)
    r+=1
  else:
    ans+=a*(l-i)
    l-=1
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

S = [[] for _ in range(N)]
for i, a in enumerate(A):
    for j in range(N):
        S[i].append(abs(j-i)*a)

left = 0
right = N - 1
is_used = [False] * N
ans = 0
for i in range(N):
    temp = []
    for j in range(N):
        if is_used[j]:
            continue
        heapq.heappush(temp, [-S[j][left], 'l', j])
        heapq.heappush(temp, [-S[j][right], 'r', j])
    
    s, pos, j = heapq.heappop(temp)
    ans -= s
    is_used[j] = True
    if pos == 'l':
        left += 1
    else:
        right -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
def valMove(i,val):
	global farR
	global farL
	left = abs(farR-i)
	right = abs(farL-i)
	return max(val*right,val*left)

def allmoved(moved):
	for i in moved:
		if not moved[i]:
			return False
	return True

# py abc163e.py
n = int(input())
arr = list(map(int,input().split()))
moved = {}
for i in range(n):
	moved[i] = False

farR = n-1
farL = 0

ans = 0

while not (allmoved(moved)):
	toMove = -1
	for i in range(n):
		if not moved[i]:
			toMove = i
			moved[i] = True
			break

	direction = -1
	if abs(farR - toMove) > abs(farL - toMove):
		direction = 1 #right
	else:
		direction = 0 #left

	for i in range(n):
		if valMove(toMove,arr[toMove]) < valMove(i,arr[i]):
			toMove = i
			if abs(farR - toMove) > abs(farL - toMove):
				direction = 1 #right
			else:
				direction = 0 #left

	ans+= valMove(toMove,arr[toMove])
	arr[toMove] = -1
	if direction == 1:
		farR-=1
	else:
		farL+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
N = int(input())
A = list(map(int, input().split()))
work = []
for i in range(N):
    work.append([A[i], i])
work.sort(key=lambda x:x[0], reverse=True)
result = 0
left = 0
right = N-1
for a, i in work:
    temp1 = abs(i-left)
    temp2 = abs(right-i)
    sumright = sum(A[i+1:])
    sumleft = sum(A[:i])
    if temp1<temp2 and (sumleft<=a or sumright>=sumleft):
        result += temp2*a
        right -= 1
    else:
        result += temp1*a
        left += 1
print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    res = [(i, a) for i, a in enumerate(A)]

    for i in range(N):
        current_index, current = res[i]
        old_current = current * abs(current_index - i)
        maxj = None
        max_d = 0
        for j in range(N):
            original_index, target = res[j]
            old_target = target * abs(original_index - j)
            new_current_score = current * abs(current_index - j)
            new_other_score = target * abs(original_index - i)

            new_score = new_current_score + new_other_score
            old_score = old_current + old_target
            d = new_score - old_score
            if d > max_d:
                max_d = d
                maxj = j

        if max_d > 0:
            res[i], res[maxj] = res[maxj], res[i]

    score = sum([current * abs(current_index - i) for i, (current_index, current) in enumerate(res)])
    print(score)

    # @lru_cache(None)
    # def f(i, j):
    #     if i < 0 or j < 0:
    #         return -INF
    #     if i == 0:
    #         return -INF
    #     if abs(j - i // 2 - 1) >= 2:
    #         return -INF
    #     if j == 0:
    #         return 0
    #     if j == 1:
    #         return max(A[:i])
    #     return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))
    #
    # print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
n = int(input())
a = np.array(list(map(int, input().split())))

selected = [False]*n
left = 0
right = n-1
ans = 0
for u in range(n):
    d = np.array([max(abs(i - left), abs(right - i)) for i in range(n)])
    r = a * d
    index = np.where(r == np.max(r))[0]
    if len(index) > 1:
        index = index[-1]
    else:
        index = index[0]
    selected[index] = True
    a[index] = 0
    ans += r[index]
    if abs(index - left) == abs(index - right):
        # print("select: ", index, ": ", left, "or", right)
        if np.sum(a[:index]) > np.sum(a[index+1:]):
            right -= 1
        else:
            left += 1
    elif d[index] == abs(index - left):
        left += 1
    else:
        right -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
N = int( input())
a = list(map(int, input().split(' ')))
l = [0]*N

p = numpy.argsort(a)[::-1]
a = numpy.sort(a)[::-1]
maxmin = [1, N]
s = 0
for i, a_i in enumerate(a):
    if p[i] + 1 > N/2 :
        s += (p[i] + 1  - maxmin[0])*a_i
        maxmin[0] = maxmin[0] + 1
        
    else:
        s += (maxmin[1]-p[i]-1)*a_i
        maxmin[1] = maxmin[1] - 1
        
print(s)

Submission status: Wrong Answer

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

ans = 0
l = 0
r = 0
for i in D:
  t, k = i
  na = abs(t - l) * k
  su = abs(N - t - r - 1) * k
  A[t] = 0
  if l > t:
    ans += su
    r += 1
    continue
  if N - r - 1 < t:
    ans += na
    l += 1
    continue

  ln = 0
  rn = 0
  for j in range(t):
    ln += A[j]
  for j in range(t, N):
    rn += A[j]
  if na + ln > su + rn:
    ans += na
    l += 1
  else:
    ans += su
    r += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
out = 0
l = 0
r = N-1
while True:
    maxP = 0
    for i in range(N):
        P = A[i]*abs(l-i)
        if P > maxP:
            maxP = P
            maxi = i
    A[maxi] = 0
    out += maxP
    l+=1
    if l==r:
        break

    maxP = 0
    for i in range(N):
        P = A[i]*abs(r-i)
        if P > maxP:
            maxP = P
            maxi = i
    A[maxi] = 0
    out += maxP
    r+=-1
    if l==r:
        break
maxP=0
for i in range(N):
    P = A[i]*abs(r-i)
    if P > maxP:
        maxP = P
        maxi = i
A[maxi] = 0
out += maxP

print(out)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    b.append([a[i],i])
b.sort(reverse=True)
b=[]
for i in range(n):
    b.append([a[i],i])
b.sort(reverse=True)
ans1=[-1 if i!=0 else b[0][0]*b[0][1] for i in range(n)]
ans2=[-1 if i!=n-1 else b[0][0]*abs(b[0][1]-(n-1)) for i in range(n)]
for i in range(1,n):
    mai=[b[i][1],0]
    for j in range(n):
        if ans1[j]==-1:
            if mai[1]<abs(b[i][1]-j):
                mai[0]=j
                mai[1]=abs(b[i][1]-j)
    ans1[mai[0]]=mai[1]*b[i][0]
for i in range(1,n):
    mai=[b[i][1],0]
    for j in range(n):
        if ans2[j]==-1:
            if mai[1]<abs(b[i][1]-j):
                mai[0]=j
                mai[1]=abs(b[i][1]-j)
    ans2[mai[0]]=mai[1]*b[i][0]
print(max(sum(ans1),sum(ans2)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)


class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost):
        # [to, cap, cost, rev]
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**9+7

        res = 0
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            if dist[t] == INF:
                return -1

            d = f; v = t
            while v != s:
                d = min(d, G[prevv[v]][preve[v]][1])
                v = prevv[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prevv[v]][preve[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prevv[v]
        return res


def solve(N: int, A: "List[int]"):
    n = 2 * N + 2
    g = MinCostFlow(n)
    S, G = 0, 1
    for i in range(N):
        g.addEdge(S, 2 + i, 1, 0)
        g.addEdge(N + 2 + i, G, 1, 0)

    for i in range(N):
        for j in range(N):
            c = A[i] * abs(j - i)
            ii = 2 + i
            jj = N + 2 + j
            g.addEdge(ii, jj, 1, -c)
            #print(i, N + j, c)
    ret = g.minCostFlow(S, G, N)
    print(-ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from collections import defaultdict
    from operator import itemgetter

    N = int(input())
    *a, = map(int, input().split())

    d = defaultdict(int)
    for i, x in enumerate(sorted(a), 1):
        d[x] = i

    left = []
    right = []
    for i, x in enumerate(a):
        if N - d[x] < i:
            left.append((x, i))
        else:
            right.append((x, i))

    left.sort(key=itemgetter(0), reverse=True)
    right.sort(key=itemgetter(0))

    ans = 0
    for j, (x, i) in enumerate(left + right):
        ans += x * abs(j - i)
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()

Submission status: Wrong Answer

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

ans = 0

#SEIRETSU = []
#for _ in range(N):
  #SEIRETSU.append(0)

left = 0
right = N-1


for i in range(N):
  LR = 0
  tmp = 0
  J = 0
  for j in range(N):
    if tmp < (A[j]*abs(j-left)):
      tmp = A[j]*abs(j-left)
      LR = 0
      J = j
    
    if tmp < (A[j]*abs(j-right)):
      tmp = A[j]*abs(j-right)
      LR = 1
      J = j

  ans += tmp
  if LR == 0:
    A[J] = 0
    #SEIRETSU[left] = tmp
    left += 1

  else:
    A[J] = 0
    #SEIRETSU[right] = tmp
    right -= 1

  #print(SEIRETSU)
  #print(A)


print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    moved = [False]*N
    result = 0
    actual =[""]*N
    upIndex = N-1
    downIndex = 0
    up = True
    def checkNext(i):
        maxScore = 0
        maxScoreIndex = -1
        for j in range(N):
            if not moved[j] and maxScore < abs(i - j) * A[j]:
                maxScoreIndex = j
                maxScore = abs(i - j) * A[j]
        return (maxScore,maxScoreIndex)
    while upIndex >= downIndex:
        fromDown,di = checkNext(downIndex)
        fromUp,ui = checkNext(upIndex)
        if fromDown > fromUp:
            result+= fromDown
            actual[downIndex] = A[di]
            moved[di] = True
            # print(f"Down{downIndex}:{di} - {A[di]}")
            # print(moved)
            downIndex+=1
        else:
            result+=fromUp
            actual[upIndex] = A[ui]
            moved[ui] = True
            # print(f"Up{upIndex}:{ui} - {A[ui]}")
            # print(moved)
            upIndex-=1
    # print(actual)
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
flag = [1 for i in range(N)]
left = 0
right = N - 1
ans = 0
for i in range(N):
    index = 0
    MAX = -1
    for j in range(N):
        if flag[j] and MAX < abs(A[j] * (abs(j - left) - abs(j - right))):
            MAX = abs(A[j] * (abs(j - left) - abs(j - right)))
            index = j
    flag[index] = 0
    ans += A[index] * max(abs(index - left), abs(index - right))
    if abs(index - left) > abs(index - right):
        left += 1
    else:
        right -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import random
import time
def LI():return list(map(int,input().split()))
start=time.time()
n=int(input()) # 2000 O(nn?),O(nlogn)
l=[i for i in range(n)]
a=LI()
ans=0
while True:
    if time.time()-start>1.85:
        print(ans)
        exit()
    random.shuffle(l)
    tmp=0
    for i,(j,k) in enumerate(zip(a,l)):
        tmp+=j*abs(i-k)
    ans=max(ans,tmp)

Submission status: Wrong Answer

Solution code:
def valMove(i,val):
	global farR
	global farL
	left = abs(farR-i)
	right = abs(farL-i)
	return max(val*right,val*left)

# py abc163e.py
n = int(input())
arr = list(map(int,input().split()))
moved = {}
for i in range(n):
	moved[i] = False

farR = n-1
farL = 0

ans = 0

while True:
	toMove = -1
	for i in range(n):
		if not moved[i]:
			toMove = i
			moved[i] = True
			break
	if (toMove == -1):
		break

	direction = -1
	if abs(farR - toMove) > abs(farL - toMove):
		direction = 1 #right
	else:
		direction = 0 #left

	for i in range(n):
		if valMove(toMove,arr[toMove]) < valMove(i,arr[i]):
			toMove = i
			if abs(farR - toMove) > abs(farL - toMove):
				direction = 1 #right
			else:
				direction = 0 #left

	ans+= valMove(toMove,arr[toMove])
	arr[toMove] = -1
	if direction == 1:
		farR-=1
	else:
		farL+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import pi
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    left = 0
    right = N-1
    ans = 0
    used = [False]*N
    while right - left >0:
        l_max = -1
        l_index = 0
        r_max = -1
        r_index = 0
        for i in range(N):
            if used[i] == False:
                l = A[i] * abs(left-i)
                r = A[i] * abs(right - i)
                if l_max<l:
                    l_index = i
                    l_max = l
                if r_max<r:
                    r_index = i
                    r_max = r
        if l_index == r_index:
            if l_max>=r_max:
                ans += l_max
                used[l_index]=True
                left += 1
            else:
                ans += r_max
                used[r_index]=True
                right -= 1
        else:
            ans += l_max + r_max
            used[r_index]=True
            used[l_index]=True
            left += 1
            right -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
IA = [(i, a) for i, a in enumerate(map(int, input().split()))]

B = []
for i, a in IA:
    for j in range(N):
        B.append((i, j, a))
B.sort(key=lambda a: a[2] * abs(a[0] - a[1]), reverse=True)

confilm = set()
ans = [-1] * N
for i, j, a in B:
    if i in confilm or ans[j] != -1:
        continue
    ans[j] = (i, a)
    confilm.add(i)

res = 0
for j, (i, a) in enumerate(ans):
    res += a * abs(j - i)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = 1 if len(set(A)) != N else 0
A = sorted([(a, i) for i, a in enumerate(A)], key=lambda x: (x[0], x[1]), reverse=True)

ans = 0
left, right = 0, N - 1
for a, i in A:
    left_v = (i - left)
    right_v = (right - i)
    #print(a, i, left, right, left_v, right_v)
    if left_v >= right_v:
        ans += a * left_v
        left += 1

    else:
        ans += a * right_v
        right -= 1

print(ans + X)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


from heapq import heapify, heappop, heappush, heappushpop


class PriorityQueue:
    def __init__(self, heap):
        '''
        heap ... list
        '''
        self.heap = heap
        heapify(self.heap)

    def push(self, item):
        heappush(self.heap, item)

    def pop(self):
        return heappop(self.heap)

    def pushpop(self, item):
        return heappushpop(self.heap, item)

    def __call__(self):
        return self.heap

    def __len__(self):
        return len(self.heap)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N = read_a_int()
A = read_ints()
# O(NN)解法
# priority queue使うと楽かなぁ
pq = PriorityQueue([])
for i, j in product(range(N), repeat=2):
    pq.push((-A[i] * abs(i - j), i, j))

is_used_i = [False] * N
is_used_j = [False] * N
ans = 0
while pq:
    happiness, i, j = pq.pop()
    if is_used_i[i] or is_used_j[j]:
        continue
    ans += -happiness
    is_used_i[i] = True
    is_used_j[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
A = list(map(int, input().split()))
ACM = np.cumsum(A)


# A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)


# A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx & (-idx)
    return res_sum


# Ai += x O(logN)
def BIT_update(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx & (-idx)
    return


i_to_a = [[a, i] for i, a in enumerate(A)]
i_to_a.sort(reverse=True)

ans = 0
l = 0
r = N-1

for a, i in i_to_a:
    left = ACM[i] - a
    left -= BIT_query(i+1)
    left += a * abs(i - l)

    right = ACM[N - 1] - ACM[i]
    right -= BIT_query(N) - BIT_query(i + 1)
    right += a * abs(r - i)

    if right < left:
        ans += a * (i - l)
        BIT_update(l+1, a)
        l += 1
    else:
        ans += a * (r - i)
        BIT_update(r+1, a)
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

l, r = 0, N - 1

ans = [0] * N
end = [0] * N
for i in range(N):
  x2 = 0
  p = "a"
  for j in range(N):
    if end[j] == 1:
      continue
    else:
      if abs(j - l) > abs(r - j):
        x = abs(j - l) * A[j]
      elif abs(j - l) == abs(r - j):
        if l < N - 1 - r:
          x = abs(j - l) * A[j]
          q = 0
        else:
          x = abs(r - j) * A[j]  
          q = 1
      else:
        x = abs(r - j) * A[j]
      x2 = max(x2, x)
      
      if x2 == x:
        p = j

  ans[p] = x2
  end[p] = 1
  
  if abs(p - l) > abs(r - p):
    l += 1
  elif abs(p - l) == abs(r - p):
    if q == 0:
      l += 1
    else:
      r += 1
  else:
    r -= 1
  #print(i, ans, end, l, r)    
  
print(sum(ans))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,(input().split())))
odr = [[0]*3 for _ in range(N)]
for i in range(N):
    odr[i][0] = A[i]
    odr[i][1] = i
    odr[i][2] = i #"現在地"

c = 1
while c:
    odr.sort(key=lambda x:x[2])
    c = 0
    for i in range(N-1):
        t = 0
        if odr[i][2] >= odr[i][1]:
            t += odr[i][0]
        else:
            t -= odr[i][0]
        if odr[i+1][2] <= odr[i+1][1]:
            t += odr[i+1][0]
        else:
            t -= odr[i+1][0]
        if t > 0:
            odr[i][2] += 1
            odr[i+1][2] -= 1
            c += 1 #入れ替えた証

#print(odr)
ans = 0
for i in range(N):
    ans += abs(odr[i][1] - odr[i][2])*odr[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
import math

NN = 202020
MOD = 10**9+7
# MOD = 998244353
INF = float("inf")

n = int(input())
A = list(map(int, input().split()))
arr = [[] for _ in range(n)]

for i in range(n):
    for j in range(n):
        arr[i].append((-A[i]*abs(i-j), i, j))
    heapq.heapify(arr[i])

que = []
for i in range(n):
    heapq.heappush(que, heapq.heappop(arr[i]))

ans = [-1]*n
seen = set()
while que:
    val, i, j = heapq.heappop(que)
    if ans[j] == -1:
        ans[j] = -val
        seen.add(i)
    else:
        heapq.heappush(que, heapq.heappop(arr[i]))
    # print(val, i, j, ans, que)
    if len(seen) >= n:
        break

print(sum(ans))