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:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(key=lambda x:x[0]*3000+round(abs(x[1]-(N//2))) if N%2 else min(round(abs(x[1]-(N//2))),round(abs(x[1]-(N//2-1)))) )
c=0
for i in range(N//2):
    a1,i1=A.pop()
    a2,i2=A.pop()
    b=(N-1-i)
    c+=max(a1*round(abs(i-i1))+a2*round(abs(b-i2)),a1*round(abs(b-i1))+a2*round(abs(i-i2)))
if N%2:
    a1,i1=A.pop()
    b=(N-1)//2
    c+=a1*round(abs(b-i1))
print(c)

Submission status: Wrong Answer

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

total_joy = 0
afterA = [0] * n
for i in range(n):
    M = max(A)
    idx = A.index(M)

    if idx <= (n-1) / 2:
        j = n-1
        while(afterA[j] != 0):
            j -= 1
        
        total_joy += M * (j - idx)
        afterA[j] = 1

    else:
        j = 0
        while(afterA[j] != 0):
            j += 1
            
        total_joy += M * (idx - j)
        afterA[j] = 1

    A[idx] = 0

print(total_joy)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
from collections import deque

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

values = []
num_indcies = {}
for i, a in enumerate(A):
    if not a in num_indcies:
        num_indcies[a] = [i]
        values.append(a)
    else:
        num_indcies[a].append(i)

values = sorted(values, reverse=True)
ans = 0
L = 0
R = N-1

ans = 0
for i, val in enumerate(values):
    indices = deque(num_indcies[val])
    print(i, val, ans, L , R)
    while len(indices) > 1:
        if abs(R - indices[0]) < abs(indices[-1] - L):
            ans += val *  abs(indices[-1]-L)
            indices.pop()
            L += 1
        else:
            ans += val *  abs(R-indices[0])
            indices.popleft()
            R -= 1
        print("indices", indices)
        print("内部", i, val, ans, L , R)
    if abs(R - indices[0]) < abs(indices[-1] - L):
        ans += val *  abs(indices[-1]-L)
        indices.pop()
        L += 1
    elif abs(R - indices[0]) > abs(indices[-1] - L):
        ans += val *  abs(R-indices[0])
        indices.popleft()
        R -= 1
    else:
        ans += val *  abs(indices[-1]-L)
        if i == len(values) -1:
            continue
        _indices = deque(num_indcies[values[i+1]])
        if abs(R - _indices[0]) < abs(_indices[-1] - L):
            L += 1
        else:
            R -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split(" ")))
A_before_old = []
for i in range(N):
    A_before_old.append((A[i], i))
A_before = sorted(A_before_old, reverse=True)
A_after = [-1] * N
s = 0
deg = [(0, 0)] * N
l = 0
while l < N:
    calc_list = []
    while True:
        calc_list.append(A_before[l])
        if l + 1 >= N: break
        if A_before[l][0] != A_before[l + 1][0]: break
        l += 1
    if calc_list[0][1] < N // 2:
        calc_list = sorted(calc_list)
    for i in range(len(calc_list)):
        diff = max(calc_list[i][1], N - calc_list[i][1] + 1)
        ok = 0
        for j in range(N):
            for k in [1, -1]:
                offset = (diff - j) * k
                idx = calc_list[i][1] + offset
                if idx < 0 : continue
                if idx >= N : continue
                if A_after[idx] == -1:
                    deg[idx] = calc_list[i]
                    A_after[idx] = calc_list[i][0]
                    s += calc_list[i][0] * abs(offset)
                    ok = 1
                if ok == 1: break
            if ok == 1: break
    l += 1
print(s)

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

lst = [int(i) for i in range(1, N + 1)]
ans = 0
dp = [[[0 for _ in range(N)] for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == 0:
            dp[j][j][i] = AP[i][0] * abs(AP[i][1] - j)
        else:
            if j - i >= 0:
                dp[j - i][j][i] = dp[j - i + 1][j][i - 1] + AP[i][0] * abs(AP[i][1] - (j - i))
            if j + i < N:
                dp[j + i][j][i] = dp[j - i + 1][j][i - 1] + AP[i][0] * abs(AP[i][1] - (j + i))
for i in range(N):
    ans = max(ans, dp[0][N-1][i])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
pos=[i for i in range(n)]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
ans=0
for i in range(n):
  ans+=arr[i]*abs(i-pos[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0] * N
for i in range(N):
    B[i] = (A[i] << 36) +i

B.sort(reverse = True)

l = 0
r = N-1
m = (1<< 36) -1
ans = 0
for i in range(N):
    b = B[i]
    s = (b&m)
    a = A[s]
    L = abs(l-s) 
    R = abs(s-r)
    if L >= R:    
        #print(a,s,l,L,ans)
        ans += L*a
        l += 1
    else:
        #print(a,s,r,R,ans)
        ans += R*a
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [a for a in enumerate(list(map(int, input().split())))]
A.sort(key=lambda x: x[1], reverse=True)
ans = 0
start = 0
end = N - 1
for i in range(N):
    d_start = abs(A[i][0] - start)
    d_end = abs(A[i][0] - end)
    if d_start > d_end:
        ans += A[i][1] * d_start
        start += 1
    elif d_start < d_end:
        ans += A[i][1] * d_end
        end -= 1
    else:
        ans += A[i][1] * d_end
        if not i < N - 1:
            continue
        _d_start = abs(A[i + 1][0] - start)
        _d_end = abs(A[i + 1][0] - end)
        if _d_start > _d_end:
            end -= 1
        else:
            start += 1
print(ans)

Submission status: Wrong Answer

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

def counter(l):
    c=0
    for i in range(N):
        c+=L[i][0]*abs(L[i][1]-i)
    return c

point=0
for k in range(2):
    for i in range(N):
        for j in range(N)[::-1]:
            
            unchange=L[i][0]*abs(L[i][1]-i) + L[j][0]*abs(L[j][1]-j)
            change=L[i][0]*abs(L[i][1]-j) + L[j][0]*abs(L[j][1]-i)
            
            if change>unchange:
                L[i][0],L[j][0]=L[j][0],L[i][0]
                L[i][1],L[j][1]=L[j][1],L[i][1]

print(counter(L))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
# 単純なのはN_P_Nとおり,つまりN!とおりすべて調べること
# 貪欲的にかく位置にたいしてその位置に移動した時のスコアの変動を選ぶ
# 最適マッチング的にとけんじゃね？ かく子供は自分の最も好きなところを選ぶ．
# もし仮にすでにその場所が占拠されているときは，すでに選挙しているスコアの人のところを選んで自分のスコアと比較する
# 自分のスコアがより高ければその場所を占拠する(すでに選挙していひとはまたプールに戻る)．もし自分のスコアが低ければ別の候補を選ぶ
from collections import deque
Machi = deque(list(range(N)))
Result =[[-1,-100] for i in range(N)] # -1はだれにも占領されていないことを表す
Scores = [[abs(pos-i)*A[pos] for i in range(N)] for pos in range(N)]
while Machi:
    pos = Machi.popleft()
    Score = Scores[pos]
    while True:
        max_score = max(Score)
        max_index = Score.index(max_score)
        if Result[max_index][1]<max_score:
            Result[max_index][1]=max_score
            loser = Result[max_index][0]
            Result[max_index][0]=pos
            if not loser==-1:
                Machi.appendleft(loser)
            break
        Score[max_index]=-1
res=0
for r in Result:
    res+=r[1]
print(res)

Submission status: Wrong Answer

Solution code:
import random
n=int(input())
arr=list(map(int,input().split()))
pos=[i for i in range(n)]
for _ in range(10**6):
  i=random.randint(0,n-1)
  j=random.randint(0,n-1)
  if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
    pos[i],pos[j]=pos[j],pos[i]
ans=0
for i in range(n):
  ans+=arr[i]*abs(i-pos[i])
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:
n = int(input())
a = []
for ind, i in enumerate(input().split()):
    a.append((ind, int(i)))

def search_next(x):
    if abs(x-l)>abs(x-r):
        return 'r'
    elif abs(x-l)<abs(x-r):
        return 'l'
    else:
        raise RuntimeError()

a.sort(key=lambda x:x[1]*max(x[0], n-x[0]), reverse=True)
l=0
r=n-1
ans = 0
for ind, (x, i) in enumerate(a):
    if abs(x-l)>abs(x-r) or ind==n-1:
        ans += i*abs(x-l)
        l += 1
    elif abs(x-l)<abs(x-r):
        ans += i*abs(x-r)
        r -= 1
    elif search_next(a[ind+1][0])=='l':
        ans += i*abs(x-l)
        l += 1
    else:
        ans += i*abs(x-r)
        r -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**4)


def dfs(sude,sho,dai,ki):
    #print("新しい",sude,sho,dai,ki)
    global a,n
    #print(a,n)
    if(n==ki):
        return 0
    koho=[]
    saidai=-1
    for i in range(n):
        if(sude[i]):
            continue
        mae=abs(sho-i)
        usiro=abs(dai-i)
        #print(sho,dai,i,mae,usiro)
        if(mae<usiro):
            if(a[i]*usiro>saidai):
                koho=[[i,1]]
                saidai=a[i]*usiro
            elif(a[i]*usiro==saidai):
                koho.append([i,1])
        elif(usiro<mae):
            if(a[i]*mae>saidai):
                koho=[[i,-1]]
                saidai=a[i]*mae
            elif(a[i]*mae==saidai):
                koho.append([i,-1])
        else:
            if(a[i]*mae>saidai):
                saidai=a[i]*mae
                koho=[[i,-1],[i,1]]
            elif(a[i]*mae==saidai):
                koho.append([i,-1])
                koho.append([i,1])
    result_max=-1
    for k in koho:
        sude_co=sude[:]
        sude_co[k[0]]=True
        kekka=-1
        if(k[1]==-1):
            kekka=dfs(sude_co,sho+1,dai,ki+1)+a[k[0]]*abs(sho-k[0])
        else:
            kekka=dfs(sude_co,sho,dai-1,ki+1)+a[k[0]]*abs(dai-k[0])
        if(result_max<kekka):
            result_max=kekka
    #print(koho)
    return result_max


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

ans=0
sude=[False]*n

print(dfs(sude,0,n-1,0))

#sho=0
#dai=n-1
#for i in range(n):
#    saiyo_val=-1
#    saiyo_num=-1
#    tiisaiho=False
#    for j in range(n):
#        if(sude[j]):
#            continue
#        saidai_kyori=max(abs(sho-j),abs(dai-j))
#        if(a[j]*saidai_kyori>saiyo_val):
#            saiyo_val=a[j]*saidai_kyori

Submission status: Wrong Answer

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################

n = int(input())
a = list(map(int, input().split()))
finish = [0 for i in range(n)]

leftPos = 0
rightPos = n-1

ans = 0
for i in range(n):
    maxim = -1
    lr = 0
    idx = -1
    for j in range(n):
        val = a[j]*abs(j-leftPos)
        if(finish[j]==0 and val > maxim):
            maxim = val
            lr = 0
            idx = j
        val = a[j]*abs(j-rightPos)
        if(finish[j]==0 and val > maxim):
            maxim = val
            lr = 1
            idx = j
    if(lr==0):
        leftPos += 1
    else:
        rightPos -=1
    ans += maxim
    finish[idx] = 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import deque

def main():
    args = input().rstrip().split(' ')
    N = int(args[0])
    args = input().rstrip().split(' ')
    A = np.array([int(val) for val in args])
    que = deque([int(val) for val in range(N)])
    top = np.argsort(-A)
    
    Ans = 0
    for i in top:
        l, r = abs(que[0]-i), abs(que[-1]-i)
        if(l > r):
            Ans += A[i] * l
            que.popleft()
        else:
            Ans += A[i] * r
            que.pop()
    print(Ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math

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

for i in range (0, N):
	List[i]=List[i]+0.0000001*i

Listsorted = sorted(List, reverse = True)

left = 0
right = 0
total = 0

for i in range (0, N):
	p = List.index(Listsorted[i])
	if p-left > N-1-p-right:
		total+= math.floor(List[p]*(p-left))
		left+=1
	else:
		total+= math.floor(List[p]*(N-1-p-right))
		right+=1

print(total)

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_l1 = 0
    max_happy_l2 = 0
    max_happy_pos_l1 = -1
    max_happy_pos_l2 = -1
    for j in range(N):
        if j in selected:
            continue
        #移動距離 |i-j|*Ajが最高になるjを選ぶ
        distance = abs(i-j)
        if max_happy_pos_l1>=0:
            if max_happy_l1 + As[max_happy_pos_l1] < As[j]*distance  + As[j]:
                max_happy_l2 = max_happy_l1
                max_happy_pos_l2 = max_happy_pos_l1
                max_happy_l1 = As[j]*distance
                max_happy_pos_l1 = j
        else:
            if max_happy_l1 < distance*As[j]: 
                max_happy_l2 = max_happy_l1
                max_happy_pos_l2 = max_happy_pos_l1
                max_happy_l1 = distance*As[j]
                max_happy_pos_l1=j


    max_happy_r1 = 0
    max_happy_r2 = 0
    max_happy_pos_r1 = -1
    max_happy_pos_r2 = -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_r1>=0:
            if max_happy_r1 + As[max_happy_pos_r1] < As[j]*distance  + As[j]:
                max_happy_r2 = max_happy_r1
                max_happy_pos_r2 = max_happy_pos_r1
                max_happy_r1 = As[j]*distance
                max_happy_pos_r1 = j
        else:
            if max_happy_r1 < distance*As[j]: 
                max_happy_r2 = max_happy_r1
                max_happy_pos_r2 = max_happy_pos_r1
                max_happy_r1 = distance*As[j]
                max_happy_pos_r1=j


    if len(selected) == N-1:
        happy_sum += max_happy_l1
        break

    if max_happy_pos_l1 == max_happy_pos_r1: #左右で同じものが選ばれた場合
        if max_happy_l1>=max_happy_r1:
            happy_sum+= (max_happy_l1 + max_happy_r2)
            selected.append(max_happy_pos_l1)
            selected.append(max_happy_pos_r2)
        else:
            happy_sum+= (max_happy_l2 + max_happy_r1)
            selected.append(max_happy_pos_l2)
            selected.append(max_happy_pos_r1)
    else:
            happy_sum+= (max_happy_l1 + max_happy_r1)
            selected.append(max_happy_pos_l1)
            selected.append(max_happy_pos_r1)

    if len(selected) == N:
        break


print(happy_sum)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
dat = list(map(int, input().split()))
#dat = [[i, datSource[i]] for i in range(n)]
#dat.sort(key=lambda x: (-x[1], -x[0]))
indL = 0
indR = n - 1


loop = math.ceil(n / 2)
used = [False] * n # その数は使ったか？
filled = [False] * n # 埋まっているか？
res = 0
while indR >= indL:
    # まずL
    maxindL = -1
    maxvalL = -9999999999999999999999
    maxindR = -1
    maxvalR = -9999999999999999999999

    for ind in range(n):
        if used[ind]: # もう使っているならパス
            continue
        disL = abs(ind - indL)
        if (dat[ind] * disL) > maxvalL:
            maxvalL = dat[ind] * disL
            maxindL = ind
        disR = abs(ind - indR)
        if (dat[ind] * disR) > maxvalR:
            maxvalR = dat[ind] * disR
            maxindR = ind

    if maxindR == maxindL:
        if maxvalL >= maxindR: # L > R
            if filled[indL]:
                indL += 1
                indR -= 1
                continue
            filled[indL] = True
            used[maxindL] = True
            res += maxvalL
            #print("L:", indL, "maxind", maxindL, "maxval", maxvalL)
            maxindR = -1
            maxvalR = -9999999999999999999999
            for ind in range(n):
                if used[ind]: # もう使っているならパス
                    continue
                disR = abs(ind - indR)
                if (dat[ind] * disR) > maxvalR:
                    maxvalR = dat[ind] * disR
                    maxindR = ind
            if filled[indR]:
                indL += 1
                indR -= 1
                continue
            filled[indR] = True
            used[maxindR] = True
            res += maxvalR
            #print("R:", indR, "maxind",maxindR, "maxval",maxvalR)
        else: # R < L
            if filled[indR]:
                indL += 1
                indR -= 1
                continue
            filled[indR] = True
            used[maxindR] = True
            res += maxvalR
            #print("R:", indR, "maxind",maxindR, "maxval",maxvalR)
            maxindL = -1
            maxvalL = -9999999999999999999999
            for ind in range(n):
                if used[ind]:  # もう使っているならパス
                    continue
                disL = abs(ind - indL)
                if (dat[ind] * disL) > maxvalL:
                    maxvalL = dat[ind] * disL
                    maxindL = ind
            if filled[indL]:
                indL += 1
                indR -= 1
                continue
            filled[indL] = True
            used[maxindL] = True
            res += maxvalL
            #print("L:", indL, "maxind", maxindL, "maxval", maxvalL)
    else:
        if filled[indL]:
            indL += 1
            indR -= 1
            continue
        filled[indL] = True
        used[maxindL] = True
        res += maxvalL
        #print("L:", indL, "maxind",maxindL, "maxval",maxvalL)
        if filled[indR]:
            indL += 1
            indR -= 1
            continue
        filled[indR] = True
        used[maxindR] = True
        res += maxvalR
        #print("R:", indR, "maxind",maxindR, "maxval",maxvalR)
    indL += 1
    indR -= 1

print(res)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(key=lambda x:x[0]*3000+round(abs(x[1]-(N//2))))
c=0
for i in range(N//2):
    a1,i1=A.pop()
    a2,i2=A.pop()
    b=(N-1-i)
    c+=max(a1*round(abs(i-i1))+a2*round(abs(b-i2)),a1*round(abs(b-i1))+a2*round(abs(i-i2)))
if N%2:
    a1,i1=A.pop()
    b=(N-1)//2
    c+=a1*round(abs(b-i1))
print(c)

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, R = 0, 0, False, 0
    for p in range(N):
        v = As[p]
 
        tm = v * (p - l)
        if m < tm or m == tm and R < p - l:
            m = tm
            mp = p
            il = True
            R = p - l
 
        tm = v * (r - p)
        if m < tm or m == tm and R < r - p:
            m = tm
            mp = p
            il = False
            R = r - p
 
    S += m
    As[mp] = 0
    if il:
        l += 1
    else:
        r -= 1
 
print(S)

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 = 0
    for j in range(N):
        if flag[j] and MAX < A[j]:
            MAX = A[j]
            index = j
    if sum(A[:index]) < sum(A[index+1:]):
        ans += A[index] * abs(right - index)
        right -= 1
    elif sum(A[:index]) > sum(A[index+1:]):
        ans += A[index] * abs(left - index)
        left += 1
    elif abs(left - index) < abs(right - index):
        ans += A[index] * abs(right - index)
        right -= 1
    else:
        ans += A[index] * abs(left - index)
        left += 1
    flag[index] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

for i in range (0, N):
	List[i]=List[i]+0.0000001*i

Listsorted = sorted(List, reverse = True)

left = 0
right = 0
total = 0

for i in range (0, N):
	p = List.index(Listsorted[i])
	if p-left > N-1-p-right:
		total+= math.floor(List[p]*(p-left))
		left+=1
		print('left')
		print(total)
	else:
		total+= math.floor(List[p]*(N-1-p-right))
		right+=1
		print('right')
		print(total)

print(total)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0

a = np.arange(N*N).reshape(N,N)

for i in range(N):
    for j in range(N):
        if i == j:
            a[i,j] = 0
        else:
            a[i,j] = A[i] * abs(i-j)

# print(a)

for _ in range(N):
    # 最大値のインデックスを取得 idxには行、列がタプルで入る
    idx = np.unravel_index(np.argmax(a),a.shape)
    ans += a[idx]
    # 最大値がある行、列を削除
    a = np.delete(a,idx[0],axis=0)
    a = np.delete(a,idx[1],axis=1)
    # print(a)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i+1,0])

A.sort(reverse=True)
for i in range(N):
    if i == 0:
        A[N-1-i][2] = A[N-1-i][0]
    else:
        A[N-1-i][2] = A[N-1-i+1][2] + A[N-1-i][0]

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l):
    global r_max
    if r_max - r > A[i][2]*(h-l+1):
        return
    if i == N-1:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l)

test(0,0,N,1)

print(r_max)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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):
    ltmp = defaultdict(list)
    lmaxV = -1
    rtmp = defaultdict(list)
    rmaxV= -1
    for i in range(N):
        if used[i]:
            continue
        ltmp[A[i]*abs(l-i)].append([i, abs(l-i), "l"])
        lmaxV = max(lmaxV, A[i]*abs(l-i))
        rtmp[A[i]*abs(r-i)].append([i, abs(r-i), "r"])
        rmaxV = max(rmaxV, A[i]*abs(r-i))
    if lmaxV > rmaxV:
        t = ltmp[lmaxV]
        t.sort(key=lambda x:x[1])
        ti = t[-1][0]
        used[ti] = True
        l += 1
        ans += lmaxV
    elif lmaxV < rmaxV:
        t = rtmp[rmaxV]
        t.sort(key=lambda x:x[1])
        ti = t[-1][0]
        used[ti] = True
        r -= 1
        ans += rmaxV
    else:
        t = ltmp[lmaxV]+rtmp[rmaxV]
        t.sort(key=lambda x:x[1])
        ti = t[-1][0]
        used[ti] = True
        if t[-1][2] == "l":
            l += 1
        else:
            r -= 1
        ans += lmaxV
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

ans = 0
def main():
    global ans
    n = int(input())
    a = list(map(int, input().split()))
    csum = [0] * (n + 1)
    for i in range(n):
        csum[i+1] = csum[i] + a[i]
    d = 0
    for i in range(1, n):
        if ans < csum[i] * (n - i) + (csum[-1] - csum[i]) * i:
            d = i
            ans = csum[i] * (n - i) + (csum[-1] - csum[i]) * i
    def bsort(A):
        global ans
        l = len(A)
        for i in range(l - 1):
            for j in range(l - 1 - i):
                if A[j] > A[j+1]:
                    ans += A[j] - A[j-1]
                    A[j], A[j-1] = A[j-1], A[j]
    bsort(a[:d])
    bsort(list(reversed(a[d:])))
    print(ans)
main()

Submission status: Wrong Answer

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

bn = [-1]*n
left = 0
right = n-1
an_ = [(an[i], i) for i in range(n)]
an_ = sorted(an_, key=lambda x:x[0], reverse=True)
# print(an_)

for a in an_:
    if abs(a[1]-left) > abs(a[1]-right):
        bn[left] = a[1]
        left += 1
    else:
        bn[right] = a[1]
        right -= 1

res = 0
for i in range(len(bn)):
    b = bn[i]
    res += an[b]*abs(b-i)
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
for i in range(N):
    AAwIdx[i][0] = i
    AAwIdx[i][1] = AA[i]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
#print(AA_sorted)
Idx_i = 0
Idx_f = N-1
AnsIdx = [0]*N
#print(Idx_f)
answer = 0
for i in range(N):
    if Idx_f - AA_sorted[i][0] > AA_sorted[i][0] - Idx_i:
        AnsIdx[AA_sorted[i][0]] = Idx_f
        #answer += abs(AA_sorted[i][0]-Idx_f)*AA_sorted[i][1]
        Idx_f -= 1
    else:
        AnsIdx[AA_sorted[i][0]] = Idx_i
        #answer += abs(AA_sorted[i][0]-Idx_i)*AA_sorted[i][1]
        Idx_i += 1
    #print(AA_sorted[i][0],Idx_i,Idx_f)
for i in range(N):
    answer += abs(AAwIdx[i][0] - AnsIdx[i])*AAwIdx[i][1]
answerb = 0
Idx_i = 0
Idx_f = N-1
AnsIdx = [0]*N
if Idx_f - AA_sorted[0][0] > AA_sorted[0][0] - Idx_i:
    AnsIdx[AA_sorted[i][0]] = Idx_i
    #answer += abs(AA_sorted[i][0]-Idx_i)*AA_sorted[i][1]
    Idx_i += 1
else:
    AnsIdx[AA_sorted[i][0]] = Idx_f
    #answer += abs(AA_sorted[i][0]-Idx_f)*AA_sorted[i][1]
    Idx_f -= 1
for i in range(1,N):
    if Idx_f - AA_sorted[i][0] > AA_sorted[i][0] - Idx_i:
        AnsIdx[AA_sorted[i][0]] = Idx_f
        #answer += abs(AA_sorted[i][0]-Idx_f)*AA_sorted[i][1]
        Idx_f -= 1
    else:
        AnsIdx[AA_sorted[i][0]] = Idx_i
        #answer += abs(AA_sorted[i][0]-Idx_i)*AA_sorted[i][1]
        Idx_i += 1
    #print(AA_sorted[i][0],Idx_i,Idx_f)
for i in range(N):
    answerb += abs(AAwIdx[i][0] - AnsIdx[i])*AAwIdx[i][1]
#print(AnsIdx)
print(max(answer, answerb))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()

tab = [ [0] * len(A) for _ in range(len(A))]
for i in range(len(A)):
    for j in range(len(A)):
        tab[j][i] = (abs(j-i)*(A[i]), i)

for t in tab:
    t.sort()

s = set(range(len(A)))

ans = [-1] * len(A)
idx = [-1] * len(A)
del_j = set()
while s:
    max_i = -1
    max_score = -float('inf')
    for i in s:
        while tab[i][-1][1] in del_j:
            tab[i].pop()
        score, j = tab[i][-1]
        if max_score < score:
            max_score = score
            max_i = i
    score, j = tab[max_i].pop()
    idx[max_i] = j
    ans[max_i] = score
    s.remove(max_i)
    del_j.add(j)

print(sum(ans))

Submission status: Wrong Answer

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

l = 0
r = N-1
res = 0
babies = {}
for i in range(N):
  babies[i] = {'incant': A[i], 'born': i}

while 0 < r-l:
  baby_info = max(babies.items(), key=lambda x:x[1]['incant'])
  index = baby_info[0]
  baby = baby_info[1]
  incant = baby['incant']
  if baby['born'] - l > r - baby['born']:
    next_pos = l
    l+=1
  else:
    next_pos = r
    r-=1

  res += incant * abs(baby['born']-next_pos)
  babies[index] = babies[next_pos]
  del babies[next_pos]

for i in babies:
  baby = babies[i]
  if 0 < baby['incant']:
    res += abs(i-baby['born']) * baby['incant']

print(res)

Submission status: Wrong Answer

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

a_num = A.count(1)

l = []
for a in reversed(sorted(A)):
    idx = A.index(a)
    A[idx] = -1
    l.append((a,idx))

head, tail = 0, N-1

ans = 0
for tup in l:
    v = tup[0]
    idx = tup[1]

    if abs(idx - head) > abs(idx - tail):
        ans += v * abs(idx-head)
        head += 1
    else:
        ans += v * abs(idx-tail)
        tail -= 1

if a_num > 1:
    ans+=1
print(ans)