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:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
"""
lst2 = [[0]*n for _ in range(n)]

for i in range(n): #座標
    for j in range(n): #もの
        lst2[i][j] = abs(i-j)*lst1[j]"""

unused = [1]*n
l = 0
r = n-1
g = 0
ans = 0
while l - r != 1:
    res = -10**9
    idx = None
    if g%2==0:
        for i in range(n):
            if unused[i] and abs(l-i)*lst1[i] >= res:
                if abs(l-i)*lst1[i] == res: #その値が小さい方優先
                    if lst1[i] < lst1[idx]:
                        idx = i
                else:
                    idx = i
                    res = abs(l-i)*lst1[i]
        unused[idx] = 0
        ans += res

        l += 1
    else:
        for i in range(n):
            if unused[i] and abs(r-i)*lst1[i] >= res:
                if abs(l-i)*lst1[i] == res:
                    if lst1[i] < lst1[idx]:
                        idx = i
                else:
                    idx = i
                    res = abs(r-i)*lst1[i]
        unused[idx] = 0
        ans += res

        r -= 1
    
    g += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
done = [False]*N
for i in range(N//2):
    j = N-1-i
    L = [(a*abs(k-i)*(1 - done[k]*2)-done[k],k) for k,a in enumerate(A)]
    R = [(a*abs(k-j)*(1 - done[k]*2)-done[k],k) for k,a in enumerate(A)]
    L.sort(reverse=True)
    R.sort(reverse=True)
    if L[0][1] != R[0][1]:
        ans += L[0][0] + R[0][0]
        done[L[0][1]] = True
        done[R[0][1]] = True
    else:
        if L[0][0] + R[1][0] > L[1][0] + R[0][1]:
            ans += L[0][0] + R[1][0]
            done[L[0][1]] = True
            done[R[1][1]] = True
        else:
            ans += L[1][0] + R[0][0]
            done[L[1][1]] = True
            done[R[0][1]] = True
if N%2==1:
    i = N//2
    k = done.index(False)
    ans += A[k]*abs(i-k)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
tmp=[(0,0)]
for i in range(N):
    tmp.append((A[i],i+1))
for _ in range(N):
    for _ in range(N):
        for i in range(1,N):
            Before=tmp[i][0]*abs(i-tmp[i][1])+tmp[i+1][0]*abs(i+1-tmp[i+1][1])
            After=tmp[i][0]*abs(i+1-tmp[i][1])+tmp[i+1][0]*abs(i-tmp[i+1][1])
            
            if After>Before:
                tmp[i],tmp[i+1]=tmp[i+1],tmp[i]
ans=0
for i in range(1,N+1):
    ans+=tmp[i][0]*abs(i-tmp[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())

dp = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        dp[i][j] = A[i] * abs(i - j)

ms = [max(dp[i]) for i in range(N)]
filled = [False] * N
ans = 0
for i, _ in sorted(enumerate(ms), key=lambda x: -x[1]):
    for j, v in sorted(enumerate(dp[i]), key=lambda x: -x[1]):
        if filled[j]:
            continue
            
        filled[j] = True
        ans += v
        break
        
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


def solve(n, a_list):
    # from left to right
    h_left = []
    res_left = [0] * n
    for i in range(n):
        r = 0
        for j in range(i):
            heappush(h_left, (-a_list[j], j))
        for k in range(i):
            a, j = heappop(h_left)
            r += (-a) * abs(n - 1 - j - k)
        assert len(h_left) == 0
        res_left[i] = r
    # print(res_left)

    # from right to left
    h_right = []
    res_right = [0] * n
    for i in range(n):
        r = 0
        for j in range(i, n):
            heappush(h_right, (-a_list[j], j))
        for k in range(n - i):
            a, j = heappop(h_right)
            r += (-a) * abs(j - k)
        res_right[i] = r
    # print(res_right)

    res = max([res_left[i] + res_right[i] for i in range(n)])
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
idx_list = [i for i in range(n)]
c = sorted(zip(a_list, idx_list),reverse=True)

start = 0
end = n-1
count = 0

for (num,idx) in c:
    # idx = a_list.index(num)
    if abs(idx - start) > abs(idx - end):
        count += num*abs(idx - start)
        # print("a:",idx,num,"_",start)
        start += 1
    elif abs(idx - start) < abs(idx - end):
        count += num*abs(idx - end)
        # print("b:",idx,num,"_",end)
        end -= 1
    else:
        if start > n-1-end:
            count += num*abs(idx - end)
            # print("c:",idx,num,"_",end)
            end -= 1
        else:
            count += num*abs(idx - start)
            # print("d:",idx,num,"_",start)
            start += 1

    # print(num,count)

print(count)

Submission status: Wrong Answer

Solution code:

N = int(input())

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

ans = 0
use = [True] * N

l = 0
r = N-1

for i in range(N):

    nmax = 0
    maxind = 0
    maxdir = 0

    for i in range(N):

        if use[i]:
            if nmax < abs(i - l)*A[i]:
                nmax = abs(i - l)*A[i]
                maxind = i
                maxdir = 0
            if nmax < abs(i - r)*A[i]:
                nmax = abs(i-r)*A[i]
                maxind = i
                maxdir = 1

    ans += nmax
    if maxdir == 0:
        l += 1
    if maxdir == 1:
        r -= 1
    use[maxind] = False

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 = []

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
K = []
used = [0]*N

for i in range(N):
    K.append([A[i],i])
K.sort(reverse=True)

ans = 0
mi = 0
ma = N-1
for i in K:
    n = i[1]
    if n - mi >= ma - n:
        ans += i[0]*(n-mi)
        mi += 1
    else:
        ans += i[0]*(ma-n)
        ma -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
tmp=[(0,0)]
for i in range(N):
    tmp.append((A[i],i+1))

for _ in range(N):
    for i in range(1,N):
        Before=tmp[i][0]*abs(i-tmp[i][1])+tmp[i+1][0]*abs(i+1-tmp[i+1][1])
        After=tmp[i][0]*abs(i+1-tmp[i][1])+tmp[i+1][0]*abs(i-tmp[i+1][1])
        
        if After>Before:
            tmp[i],tmp[i+1]=tmp[i+1],tmp[i]
ans=0
for i in range(1,N+1):
    ans+=tmp[i][0]*abs(i-tmp[i][1])
print(ans)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    res = 0

    heap = []
    for i in range(N):
        for j in range(N):
            ureshi = A[i] * abs(i - j)
            heapq.heappush(heap, (-ureshi, i, j))

    usedi = set()
    usedj = set()
    while heap:
        ureshi, i, j = heapq.heappop(heap)
        if i in usedi or j in usedj:
            continue
        usedi.add(i)
        usedj.add(j)
        res += -ureshi

    print(res)


# 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:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect
import numpy as np

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 = []

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

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

print(ans)

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):
    t = np.array([v if not selected[i] else 0 for i, v in enumerate(a)])
    d = np.array([max(abs(i - left), abs(right - i)) for i in range(n)])
    r = t * d
    index = np.where(r == np.max(r))[0][0]
    selected[index] = True
    ans += r[index]
    if abs(index - left) == abs(index - right):
        # print("select: ", index, ": ", left, "or", right)
        if np.sum(t[:index]) > np.sum(t[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 sys 
# try:
# 	sys.stdin = open('input.txt', 'r') 
# 	sys.stdout = open('output.txt', 'w')
# except:
# 	pass
input = sys.stdin.readline
for tt in range(1):
	n = int(input())
	# a,b = map(int,input().split())
	arr = list(map(int,input().split()))
	i = 0
	j = 1
	right = n-1
	left = 0
	arr = list(enumerate(arr))
	arr.sort(reverse = True, key = lambda x:x[1])
	# print(arr)
	ans = 0 
	while i<n and j<n:
		first = max(arr[i][1] * (abs(arr[i][0] - right)), arr[i][1] * (abs(arr[i][0] - left)))
		second = max(arr[j][1] * (abs(arr[j][0] - right)), arr[j][1] * (abs(arr[j][0] - left)))
		# print(first,second)
		if first > second:
			if abs(arr[i][0] - right) > abs(arr[i][0] - left):
				right -= 1
			else:
				left += 1
			ans += first
			i=j
			j+=1
		else:
			if abs(arr[j][0] - right) > abs(arr[j][0] - left):
				right -= 1
			else:
				left += 1
			j+=1
			ans += second
		# print("i and j", i,j)
		# print("Right Left", right, left)
		# print()
	if i<n:
		ans += max(arr[i][1] * (abs(arr[i][0] - right)), arr[i][1] * (abs(arr[i][0] - left)))
	else:
		ans += max(arr[j][1] * (abs(arr[j][0] - right)), arr[j][1] * (abs(arr[j][0] - left)))
	# print(i,j,right,left)
	print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = [int(s) for s in input().split()]

l = 0
r = N - 1

S = 0
for k in range(N):
    m, mp, il = 0, 0, False
    for p in range(N):
        v = As[p]

        tm = v * abs(r - p)
        if m < tm:
            m = tm
            mp = p
            il = False

        
        tm = v * abs(l - p)
        if m < tm:
            m = tm
            mp = p
            il = True

    S += m
    As[mp] = 0
    if il:
        l += 1
    else:
        r -= 1

print(S)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    ans=0
    #各ますに対する得点表を作っておく，取れる最大のマスカラ埋めていく？
    S=[[0]*N for _ in range(N)]
    #S[i][j]はi番目の数をj番目に持っていく
    for i in range(N):
        for j in range(N):
            S[i][j]=A[i]*abs(i-j)
            
    used=[0]*N#移動さきのマスjが使用済みか
    floor=0
    ceil=N-1
    #今移動できる両端
            
            
    def cle(ii,jj):
        for k in range(N):
            S[ii][k]=-1
            S[k][jj]=-1
            
    def se():
        maxx=-1
        maxi=-1
        maxj=-1
        for i in range(N):
            for k in range(2):
                if k==0:
                    j=floor
                else:
                    j=ceil
                temp=S[i][j]
                if temp>maxx:
                    maxx=temp
                    maxi=i
                    maxj=j
        return maxx,maxi,maxj
    
    ans=0
    for k in range(N):
        maxx,maxi,maxj=se()
        ans+=maxx
        cle(maxi,maxj)
        used[maxj]=1
        if maxj==ceil:
            for jj in range(ceil,-1,-1):
                if used[jj]==0:
                    ceil=jj
                    break
        if maxj==floor:
            for jj in range(floor,N,1):
                if used[jj]==0:
                    floor=jj
                    break
                


        
    
            
    print(ans)
        
        
        

main()

Submission status: Wrong Answer

Solution code:
import math

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

l, r = 0, N

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 - 1):
        x = abs(j - l) * A[j]
      else:
        x = abs(r - j - 1) * A[j]
      x2 = max(x2, x)
      
      if x2 == x:
        p = j

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from collections import deque
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
heap = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        heappush(heap, (-A[i] * abs(j-i), i, j))

answer = 0
i_used = set()
j_used = set()
while heap:
    happy, ip, jp= heappop(heap)
    if ip in i_used or jp in j_used:
        continue
    i_used.add(ip); j_used.add(jp)
    answer -= happy

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
"""
lst2 = [[0]*n for _ in range(n)]

for i in range(n): #座標
    for j in range(n): #もの
        lst2[i][j] = abs(i-j)*lst1[j]"""

unused = [1]*n
l = 0
r = n-1
g = 0
ans = 0
while l - r != 1:
    res = -10**9
    idx = None
    if g%2==0:
        for i in range(n):
            if unused[i] and abs(l-i)*lst1[i] >= res:
                if abs(l-i)*lst1[i] == res: #idx小さい方優先
                    idx = min(idx,i)
                else:
                    idx = i
                    res = abs(l-i)*lst1[i]
        unused[idx] = 0
        ans += res

        l += 1
    else:
        for i in range(n):
            if unused[i] and abs(r-i)*lst1[i] >= res:
                if abs(l-i)*lst1[i] == res: #idx大きい方優先
                    idx = max(idx,i)
                else:
                    idx = i
                    res = abs(r-i)*lst1[i]
        unused[idx] = 0
        ans += res

        r -= 1
    
    g += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
s = 0
AP = []
for a in A:
    s += 1
    AP.append((a, s))

AP.sort(reverse=True)

lst = [int(i) for i in range(1, N + 1)]
ans = 0
for a in AP:
    if abs(a[1] - lst[0]) >= abs(a[1] - lst[-1]):
        ans += abs(a[1] - lst.pop(0)) * a[0]
    else:
        ans += abs(a[1] - lst.pop(-1)) * a[0]
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [(i, ai) for i, ai in enumerate(map(int, input().split()))]
i = 0
while True:
    if not i <= n - 2:
        break
    x, ax = a[i]
    y, ay = a[i+1]
    current = ax * abs(x - i) + ay * abs(y - i - 1)
    ifswap = ax * abs(x-i-1) + ay * abs(y-i)
    if current < ifswap:
        a[i], a[i+1] = a[i+1], a[i]
        if i > 0:
            i -= 1
    else:
        i += 1

ans = sum(ai * abs(i - i_orig)  for i, (i_orig, ai) in enumerate(a))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [i for i in range(N)]
def score(X):
    s = 0
    for i in range(N):
        s += A[i]*abs(i-X[i])
    return s


flag = True
bestscore = 0
while flag:
    flag = False
    for i in range(N):
        for j in range(N):
            B[i], B[j] = B[j], B[i]
            sc = score(B)
            if sc > bestscore:
                bestscore = sc
                flag = True
            else:
                B[i], B[j] = B[j], B[i]
    
print(score(B))

Submission status: Wrong Answer

Solution code:
from collections import deque

n=int(input())
a=list(map(int,input().split()))
gg=a.copy()
tmp=a.copy()
tmp.sort()

ans=deque([tmp[0]])

for i in range(1,n):
    if a.index(tmp[i])<=n//2-1:
        ans.append(tmp[i])
        a[a.index(tmp[i])]+=float('inf')
    else:
        ans.appendleft(tmp[i])
        a[a.index(tmp[i])] += float('inf')

ans=list(ans)

cnt=0
for i in range(n):
    y=gg.index(ans[i])
    cnt+=abs(y-i)*ans[i]
    gg[y]+=float('inf')
if n%4!=0:
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
dp=np.array([[0 for _ in range(n)] for _ in range(n)])
for i in range(n):
    for j in range(n):
        dp[i][j]=abs(i-j)*a[i]
#print(dp)
ans=0
nu=n
for i in range(n):
    ind=np.argmax(dp)
    row=ind//nu
    col=ind%nu
    ans+=dp[row][col]
    dp=np.delete(dp,row,0)
    dp=np.delete(dp,col,1)
    nu-=1
    #print(dp)
    #print()

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a  = list(map(int,input().split()))
res = []
for i in range(n):
    res.append((a[i],i))
res.sort(reverse = True)
lcnt,rcnt = 0,0
ans = 0
for val,ind in res:
    if ind-lcnt < n-ind-1-rcnt:
        
        ans +=val*(n-ind-1-rcnt)
        rcnt+=1
    else:
        ans +=val*(ind - lcnt)
        lcnt+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def maximumIndices(liste):
  maxi = liste[0]
  indice = 0
  longueur=len(liste)
  for i in range(longueur):
    if liste[i] >= maxi:
      maxi = liste[i]
      indice = i
  return indice

N = int(input())
activity = input().split(" ")
for i in range(N):
  activity[i]=int(activity[i])
bornesup = N-1
borneinf = 0
total = 0
while borneinf<=bornesup:
  indice = maximumIndices(activity)
  distsup = bornesup-indice
  if indice<=distsup:
    total+=activity[indice]*distsup
    bornesup-=1
  else:
    total+=activity[indice]*indice
    borneinf+=1
  activity[indice]=0
total+=activity[borneinf]*borneinf
print(total-2)

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*(N-i-j)
    for i in range(len(B)):
        j, x = B[i]
        r += x*(j-(i+1))
    R = max(R, r)

print(R)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[i, x] for i, x in enumerate(A)]

for i in range(N):  # start
	for j in range(N-1):  # loop
		tmp1 = L[j][1]*abs(L[j][0]-j)+L[j+1][1]*abs(L[j+1][0]-(j+1))
		tmp2 = L[j][1]*abs(L[j][0]-(j+1))+L[j+1][1]*abs(L[j+1][0]-j)
		if  tmp2 > tmp1:
			L[j], L[j+1] = L[j+1], L[j]
ans = 0
for i, l in enumerate(L):
	ans += l[1]*abs(i-l[0])
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

l, r = 0, N

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 - 1):
        x = abs(j - l) * A[j]
      else:
        x = abs(r - j - 1) * A[j]
      x2 = max(x2, x)
      
      if x2 == x:
        p = j

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

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    res = 0

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

    heap = []
    for i in range(N):
        for j in range(N):
            ureshimat[i][j] = A[i] * abs(i - j)
            heapq.heappush(heap, (-ureshimat[i][j], i, j))

    usedi = set()
    usedj = set()
    while heap:
        ureshi, i, j = heapq.heappop(heap)
        if i in usedi or j in usedj:
            continue
        usedi.add(i)
        usedj.add(j)
        res += -ureshi

    print(res)


# 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:
from heapq import heappop, heappush


def solve(n, a_list):
    # from left to right
    h_left = []
    res_left = [0] * n
    for i in range(n):
        r = 0
        for j in range(i):
            heappush(h_left, (-a_list[j], j))
        for k in range(i):
            a, j = heappop(h_left)
            r += (-a) * abs(n - 1 - j - k)
        assert len(h_left) == 0
        res_left[i] = r
    # print(res_left)

    # from right to left
    h_right = []
    res_right = [0] * n
    for i in range(n):
        r = 0
        for j in range(i, n):
            heappush(h_right, (-a_list[j], j))
        for k in range(n - i):
            a, j = heappop(h_right)
            r += (-a) * abs(j - k)
        res_right[i] = r
    # print(res_right)

    res = max([res_left[i] + res_right[i] for i in range(n)])
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [(i, a[i]) for i in range(n)]
left, right = 0, n-1

ans = 0
while True:
    happiness = [max(c[0]-left, right-c[0]) * c[1] for c in b]
    # max/argmax
    tmp, argmax = 0, 0
    for i in range(len(b)):
        if happiness[i] > tmp:
            tmp, argmax = happiness[i], i
    if b[argmax][0]-left > right-b[argmax][0]:
        left += 1
    else:
        right -= 1
    ans += tmp
    del b[argmax]
    if left == right:
        break

ans += max(b[0][0]-left, right-b[0][0]) * b[0][1]
print(ans)

Submission status: Wrong Answer

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

l = 0; r = N-1
ans = 0
used = [False for _ in range(N)]
for _ in range(N):
    maxV = -1
    maxi = -1
    isr = False
    for i in range(N):
        if used[i]:
            continue
        if abs(r-i) >= abs(l-i):
            if maxV < A[i]*abs(r-i):
                isr = True
                maxV = A[i]*abs(r-i)
                maxi = i
        else:
            if maxV < A[i]*abs(l-i):
                isr = False
                maxV = A[i]*abs(l-i)
                maxi = i
    used[maxi] = True
    ans += maxV
    if isr:
        r -= 1
    else:
        l += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
aaa_with_idx = list(zip(aaa, range(n)))
n2 = n // 2
ans = 0
for i in range(n2 + 1):
    srt = sorted(aaa_with_idx[i:], reverse=True)
    left = srt[:n2]
    right = sorted(srt[n2:] + aaa_with_idx[:i])

    tmp = 0
    for j, (a, k) in enumerate(left):
        tmp += a * abs(j - k)
    for j, (a, k) in enumerate(right, start=n2):
        tmp += a * abs(j - k)

    ans = max(ans, tmp)
print(ans)

Submission status: Wrong Answer

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

a_set = set(a_list)
a_dict = {a:[] for a in a_set}
p_dict = {}
for position, activity in enumerate(a_list):
  a_dict[activity].append(position+1)
  p_dict[position+1] = activity

# print(a_list)
# print(a_dict)
# print(p_dict)

sorted_a = sorted(set(a_list), reverse=True)

l, r = 1, n
after_p_dict = {}
after_a_dict = {}
ret = 0
for sa in sorted_a:
#   print(100, l, r)
  
  p_list = sorted(a_dict[sa])
  l_dist_list = [(l-_p)**2 for _p in p_list]
  r_dist_list = [(r-_p)**2 for _p in p_list]
  inner_l, inner_r = 0, len(p_list)-1
  for i in range(len(p_list)):
    if l_dist_list[inner_l] >= r_dist_list[inner_r]:
      p = p_list[inner_l]
      inner_l += 1
    else:
      p = p_list[inner_r]
      inner_r -= 1
      
    if (l-p)**2 >= (r-p)**2:
      after_a_dict[sa] = l
      ret += abs(l-p)*sa
#       print(111, 'sa: {}, p→l: {}→{}, diff: {}'.format(sa, p,l, abs(l-p)*sa))
      l += 1
    else:
#       print(222, 'sa: {}, p→r: {}→{}, diff: {}'.format(sa, p, r, abs(r-p)*sa))
      after_a_dict[sa] = r
      ret += abs(r-p)*sa
      r -= 1
  
#     print(200, l, r)
#     if l > r:
#       print('end!')

print(ret)

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 #"現在地"


for _ in range(N):
    odr.sort(key=lambda x:x[2])
    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

#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:
#!/usr/bin/env python3
import sys
from itertools import accumulate
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
AA = list(enumerate(A))
acc = [0]+list(accumulate(A))


mt = -INF
for k in range(1, N):
    # k以降を手前へ, kまでを後ろへ
    kpre, kpost = AA[:k], AA[k:]
    kpre.sort(key=lambda x: x[1])
    kpost.sort(key=lambda x: x[1], reverse=True)
    tot = 0
    for ii, (i, v) in enumerate(kpre):
        tot += abs(ii+(N-k)-i)*v
    for ii, (i, v) in enumerate(kpost):
        tot += abs(ii-i)*v
    # print(kpre, kpost, tot)
    if tot > mt:
        mt = tot
        # print("!", kpost, kpre, tot)
print(mt)

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 * (i - l)

    right = ACM[N - 1] - ACM[i]
    right -= BIT_query(N) - BIT_query(i + 1)
    right += a * (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 sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	A = getlist()
	S = []
	for i in range(N):
		for j in range(N):
			S.append([A[i] * abs(i - j), -A[i], i, j])

	S = sorted(S)
	Ajudi = [0] * N
	Ajudj = [0] * N
	Lis = [0] * N
	ans = 0
	# print(S)
	for i in range(N ** 2):
		cur = N ** 2 - 1 - i
		if Ajudi[S[cur][2]] == 0 and Ajudj[S[cur][3]] == 0:
			Ajudi[S[cur][2]] = 1
			Ajudj[S[cur][3]] = 1
			Lis[S[cur][3]] = S[cur][0]
			ans += S[cur][0]

	# print(Lis)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

pq = []
for i in range(N):
    for j in range(N):
        heappush(pq, (-A[i] * abs(i - j), i, j))

used = [False] * N
filled = [False] * N
ans = 0
while pq:
    v, i, j = heappop(pq)
    if used[i] or filled[j]:
        continue

    ans += v
    used[i] = True
    filled[j] = True
    
print(-ans)