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:
#!/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
    def checkNext(i):
        maxScore = -1
        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)
            # print(f"down:{downIndex},up:{upIndex}")
            downIndex+=1
        else:
            result+=fromUp
            actual[upIndex] = A[ui]
            moved[ui] = True
            # print(f"Up{upIndex}:{ui} - {A[ui]}")
            # print(moved)
            # print(f"down:{downIndex},up:{upIndex}")
            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:
import heapq
n = int(input())
a = list(map(int, input().split()))
l, r = 0, len(a) - 1
ans = 0
while l <= r:
    cost_ls = [(-1 * a[i] * (i - l), i, False) if (i - l > r - i) else (-1 * a[i] * (r - i), i, True) for i in range(len(a))]
    heapq.heapify(cost_ls)
    cost, loc, is_right = heapq.heappop(cost_ls)
    # print(-cost, loc, a[loc], is_right)
    ans -= cost
    a[loc] = 0
    if is_right:
        r -= 1
    else:
        l += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
#show_flg=True

ans=0


n=I()
A=LI()
a=list(enumerate(A))
a.sort(key=lambda x:x[1])
show('a',a)

b=[[]for i in range(n)]
for i in range(n):
    for j in range(n):
        b[i].append(abs(i-j)*A[i])

for j in b:
    show('b',j)

l,r=0,n-1
rng=list(range(n))
skp=set()
for i in range(n):
    mx_l,mx_r=-1,-1
    for j in range(n):
        if j in skp:continue
        if b[j][l]>mx_l:
            mx_l=b[j][l]
            l_can=set()
            l_can.add(j)
        elif b[j][l]==mx_l:
            l_can.add(j)

        if b[j][r]>mx_r:
            mx_r=b[j][r]
            r_can=set()
            r_can.add(j)
        elif b[j][r]==mx_r:
            r_can.add(j)
    show('mx_l,mx_r',mx_l,mx_r)
    if mx_r>mx_l:
        ans+=mx_r
        r-=1
        mn_l=1<<63
        for x in r_can:
            if b[x][l]<mn_l:
                mn_l=b[x][l]
                r_skp=x
        skp.add(r_skp)
        show('r')
    elif mx_l>mx_r:
        ans+=mx_l
        l+=1
        mn_r=1<<63
        for x in l_can:
            if b[x][r]<mn_r:
                mn_r=b[x][r]
                l_skp=x
        skp.add(l_skp)
        show('l')
    elif mx_l==mx_r:
        ans+=mx_l
        l+=1
        mn_r=1<<63
        for x in l_can:
            if b[x][r]<mn_r:
                mn_r=b[x][r]
                l_skp=x
        skp.add(l_skp)
        show('=')
    show(skp,(l,r),ans)

print(ans)

Submission status: Wrong Answer

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

candidates = list(range(N))
order = [0] * N
order[::2] = candidates[N // 2:][::-1]
order[1::2] = candidates[:N // 2]
ans = 0
for i in order:
    max_h = -1
    max_j = 0
    for j in candidates:
        h = A[j] * abs(i - j)
        if h > max_h:
            max_j = j
            max_h = h
    ans += max_h
    candidates.remove(max_j)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
C=[False]*n

l,r=0,n-1
ans=0
for _ in range(n):
  score=0
  ii=0
  ss=0
  for i in range(n):
    if C[i]:
      continue
    else:
      a=A[i]
      if score<a*max(abs(l-i),abs(r-i)) or (score==a*max(abs(l-i),abs(r-i)) and ss<a):
        score=a*max(abs(l-i),abs(r-i))
        ii=i
        ss=a
        if abs(l-i)>abs(r-i):
          dir=-1
        else:
          dir=1

  ans+=score
  if dir==-1:
    l+=1
  else:
    r-=1
  C[ii]=True
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

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


def main():
    P = [(A[i], i) for i in range(N)]
    P.sort(reverse=True)

    left, right = 0, N - 1
    ans = 0
    for x, i in P:
        A[i] = 0
        t = (right - i) * x - (i - left) * x
        t += sum(A[i:])
        t -= sum(A[:i])
        if t > 0:
            ans += (right - i) * x
            right -= 1
        else:
            ans += (i - left) * x
            left += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

#greedyに解けるか?
#greedyで解けるならば計算量はN**2
#N<2000なので行ける1

selected = []

happy_sum = 0
for i in range(N):

    #まず左端から処理をする
    max_happy = 0
    max_happy_pos = -1
    for j in range(N):
        if j in selected:
            continue
        #移動距離 |i-j|*Ajが最高になるjを選ぶ
        distance = abs(i-j)
        if max_happy_pos>=0:
            if max_happy + As[max_happy_pos] < As[j]*distance  + As[j]:
                max_happy = As[j]*distance
                max_happy_pos = j
        else:
            if max_happy < distance*As[j]: 
                max_happy = distance*As[j]
                max_happy_pos=j
    selected.append(max_happy_pos)
    happy_sum += max_happy
    if len(selected) == N :
        break
    max_happy = 0
    max_happy_pos = -1

    #次に右端から見ていく
    for j in range(N):
        if j in selected:
            continue
        #移動距離 |i-j|*Ajが最高になるjを選ぶ
        distance = abs((N-i-1)-j)
        if max_happy_pos>=0:
            if max_happy + As[max_happy_pos] < As[j]*distance  + As[j]:
                max_happy = As[j]*distance
                max_happy_pos = j
        else:
            if max_happy < distance*As[j]: 
                max_happy = distance*As[j]
                max_happy_pos=j
    selected.append(max_happy_pos)
    happy_sum += max_happy
    if len(selected) == N :
        break

print(happy_sum)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=list(range(n))
for i,x in enumerate(a):
	for j in range(n):
		if abs(b[i]-i)*a[i]+abs(b[j]-j)*a[j]<abs(b[j]-i)*a[i]+abs(b[i]-j)*a[j]:
			b[i],b[j]=b[j],b[i]
for i,x in enumerate(a):
	for j in range(n):
		if abs(b[i]-i)*a[i]+abs(b[j]-j)*a[j]<abs(b[j]-i)*a[i]+abs(b[i]-j)*a[j]:
			b[i],b[j]=b[j],b[i]
print(sum(x*abs(i-b[i]) for i,x in enumerate(a)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = []
for i in range(n):
  d.append([a[i],i+1])
d.sort(reverse = True)
count = 0
left = 1
right = n
m = 0
h = 0
for i in range(n):
  k = d[i][0]
  v = d[i][1]  
  if (v-left) < (right-v):
    count += k*(right-v)
    right -= 1
  elif (v-left) == (right-v):
      if m>=h:
          count += k*(v-left)
          left += 1
      else:
          count += k*(right-v)
          right -= 1
  else:
    count += k*(v-left)
    left += 1
  if v-1 > n//2:
      m += 1
  else:
      h += 1
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a, reverse=True)
left, right = 0, 0
sum = 0
for i in range(n):
    index = a.index(b[i])
    a[index] = 0
    if index < n / 2:
        sum += b[i]*(((n - 1) - right) - index)
        right += 1
    else:
        sum += b[i]*(index - left)
        left += 1
print(sum)

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(N):
    ln += abs(N - r - j - 1) * A[j]
    rn += abs(l - j) * A[j]

  if na + ln > su + rn:
    ans += na
    l += 1
  else:
    ans += su
    r += 1

print(ans)

Submission status: Wrong Answer

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n = ii()
    a = lmi()
    left = 0
    right = n-1
    determined = [False] * n
    ans = 0
    for _ in range(n):
        memo = [[-1, None] for _ in range(n)]
        for j in range(n):
            if not determined[j]:
                dest = left if abs(j-left) > abs(right-j) else right
                memo[j][0] = a[j] * max(abs(j-left), abs(right-j))
                memo[j][1] = dest
        max_ind = 0
        max_val = -1
        for i, elm in enumerate(memo):
            if elm[0] > max_val:
                max_val = elm[0]
                max_ind = i
        ans += max_val
        determined[max_ind] = True
        dest = memo[max_ind][1]
        if dest == left:
            left += 1
        else:
            right -= 1
    print(ans)


    # def func(L, r_end):
    #     tmp = []
    #     ans = 0
    #     for i, elm in enumerate(L):
    #         tmp.append([elm, i])
    #     tmp.sort(reverse=True)
    #     # print(tmp)
    #     for k, elm in enumerate(tmp):
    #         ans += elm[0] * (r_end - elm[1] - k)
    #     return ans       

    # if n % 2 == 0:
    #     mid = n//2
    #     left = a[:mid]
    #     right = a[mid:]
    #     ans = 0
    #     r_end = n-1
    #     ans += func(left, r_end)
    #     # print(ans)
    #     ans += func(reversed(right), r_end)
    #     print(ans)



if __name__ == "__main__":
    main()

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 + n % 2):
    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)
    # print(left, right)

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

Submission status: Wrong Answer

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n = ii()
    a = lmi()
    left = 0
    right = n-1
    determined = [False] * n
    ans = 0
    for _ in range(n):
        memo = [[-1, None] for _ in range(n)]
        for j in range(n):
            if not determined[j]:
                dest = left if abs(j-left) > abs(right-j) else right
                memo[j][0] = a[j] * max(abs(j-left), abs(right-j))
                memo[j][1] = dest
        max_ind = 0
        max_val = -1
        for i, elm in enumerate(memo):
            if elm[0] > max_val:
                max_val = elm[0]
                max_ind = i
        ans += max_val
        determined[max_ind] = True
        dest = memo[max_ind][1]
        if dest == left:
            left += 1
        else:
            right -= 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 = [[A[i], i] for i in range(N)]
	for k in range(N):
		for i in range(N - 1):
			A1 = S[i][0]
			A2 = S[i + 1][0]
			x = S[i][1]
			y = S[i + 1][1]
			if A1 * abs(x - i) + A2 * abs(y - i - 1) < A1 * abs(x - i - 1) + A2 * abs(y - i):
				S[i + 1][0] = A1
				S[i][0] = A2
				S[i + 1][1] = x
				S[i][1] = y

	# print(S)

	ans = 0
	for i in range(N):
		a = S[i][0]
		x = S[i][1]
		ans += a * abs(x - i)

	print(ans)


if __name__ == '__main__':
	main()

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

    f = True
    while f:
        f = False
        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:
                f = True
                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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
start = 0
end = n - 1
ans = 0
for i in range(0, n):
    max_score = 0
    iti = -1
    flag = 0
    for j in range(0, n):
        if max_score < a_list[j] * abs(j - start):
            max_score = a_list[j] * abs(j - start)
            iti = j
            flag = -1
        if max_score < a_list[j] * abs(end - j):
            max_score = a_list[j] * abs(end - j)
            iti = j
            flag = 1
    a_list[iti] = 0
    if flag == -1:
        # print(iti+1, start+1, max_score)
        ans += max_score
        start += 1
        
    elif flag == 1:
        ans += max_score
        # print(iti+1, end+1, max_score)
        end -= 1
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 * abs(i - l)
        BIT_update(l+1, a)
        l += 1
    else:
        ans += a * abs(r - i)
        BIT_update(r+1, a)
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=list(range(n))
for i,x in enumerate(a):
	for j in range(n):
		if abs(b[i]-i)*a[i]+abs(b[j]-j)*a[j]<abs(b[j]-i)*a[i]+abs(b[i]-j)*a[j]:
			b[i],b[j]=b[j],b[i]
	for j in range(n):
		if abs(b[i]-i)*a[i]+abs(b[j]-j)*a[j]<abs(b[j]-i)*a[i]+abs(b[i]-j)*a[j]:
			b[i],b[j]=b[j],b[i]
print(sum(x*abs(i-b[i]) for i,x in enumerate(a)))

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+1)

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
for j in range(1,n):
  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:
# -*- coding: utf-8 -*-
import sys

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

B = []
for i,a in enumerate(A):
    B.append([a,i])
#%%
ans = 0
for i in range(1,max(2,N-1)):
    # しきりの位置
    
    res = 0
    left = 0
    right = N-1
    L = B[:i]
    L.sort(reverse = True)
    R = B[i:]
    R.sort(reverse = True)
    for val,idx in R:
        res += val*abs(idx-left)
        left += 1
    
    for val,idx in L:
        res += val*abs(right-idx)
        right -= 1
    ans = max(ans,res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))

    left = 0
    right = n - 1

    ans = 0
    used = [False] * n
    pos = [0] * n

    for _ in range(n):
        xmax = [0] * n

        for i in range(n):
            if used[i]:
                continue

            l = abs(i - left) * a[i]
            r = abs(i - right) * a[i]

            if l > r:
                xmax[i] = l
                pos[i] = True
            else:
                xmax[i] = r
                pos[i] = False

        m = max(xmax)
        ans += m
        idx = xmax.index(m)
        used[idx] = True

        if pos[idx]:
            left += 1
        else:
            right -= 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

AL = [0]*N
used = [False]*N

l = 0
r = N-1
ans = 0
for _ in range(N):
    maxp = 0
    for i, a in enumerate(A):
        if used[i]:
            continue
        p = max(i-l, r-i)*a
        if p >= maxp:
            if p > maxp:
                maxp = p
                ml = []
                mr = []

            if i-l >= r-i:
                ml.append((i-l, i, l))
            elif i-l <= r-i:
                mr.append((r-i, i, r))

    if len(ml) == 1:
        d, i, to = ml[0]
    elif len(mr) == 1:
        d, i, to = mr[0]
    else:
        d, i, to = sorted(ml+mr)[0]

    ans += d*A[i]
    AL[to] = A[i]
    used[i] = True
    if to == l:
        l += 1
    else:
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E - Active Infants
# モジュールのインポート
import math

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
A1,A2 = {},{}
divisor = 0
sum_A = sum(A)
for i,a in enumerate(A):
    if divisor >= math.ceil(sum_A/2):
        A2[i] = a
    else:
        A1[i] = a
    divisor += a

result = 0
sorted_A1 = sorted(A1.items(), key=lambda x:x[1], reverse=True)
y1 = N
for x1,a1 in sorted_A1:
    result += a1 * abs(x1+1-y1)
    y1 -= 1

sorted_A2 = sorted(A2.items(), key=lambda x:x[1], reverse=True)
y2 = 1
for x2,a2 in sorted_A2:
    result += a2 * abs(x2+1-y2)
    y2 += 1

print(result)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
used = [False] * N
fixed = [0, N-1]
ans = 0
for _ in range(N):
    h = (-float('inf'), -1, -1)
    for i in range(N):
        if used[i]:
            continue

        val = 0
        r = 1
        if A[i] * abs(i-fixed[0]) >= A[i] * abs(i - fixed[1]):
            val = A[i] * abs(i - fixed[0])
            r = 0
        else:
            val = A[i] * abs(i - fixed[1])
            r = 1

        h = (val, i, r) if val > h[0] else h
    val, index, r = h
    ans += val
    used[index] = True
    if r == 0:
        fixed[0] += 1
    else:
        fixed[1] -= 1
    # print(val, index, used)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n =int(sys.stdin.readline())
l = list(map(int,sys.stdin.readline().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
sys.stdout.write((str(ans)+'\n'))

Submission status: Wrong Answer

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

import heapq

ans = 0
doneX = [False]*N
doneY = [False]*N
hq = []
hpush = heapq.heappush
hpop = heapq.heappop
for x,a in enumerate(A):
    for y in range(N):
        hpush(hq,(-a*abs(x-y),x,y))

while hq:
    a,x,y = hpop(hq)
    if doneX[x] or doneY[y]:continue
    ans -= a
    doneX[x] = True
    doneY[y] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
As = np.array(list(map(int, input().split())))

origs = As.copy()
idxs = np.argsort(origs)[::-1]
head, tail = 0, N - 1

res = 0
#tmp = np.zeros(N)
for idx in idxs:
    ai = origs[idx]
    ptl = ai * (idx - head)
    ptr = ai * (tail - idx)
    sumr = origs[idx+1:].sum()
    suml = origs[:idx].sum()
    if (ptr - suml) > (ptl - sumr):#右に行くとお得
        #tmp[tail] = ai
        tail -= 1
        res += ptr
    else:
        #tmp[head] = ai
        head += 1
        res += ptl
    origs[idx] = 0
    #sys.exit()
print(res)

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
for j in range(1,n-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)