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:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

n=int(input())
ar=lis()
data=[]
for i in range(n):
    data.append((ar[i],i))
data.sort(reverse=True)
dp = [[0] * (n+1) for _ in range(n+1)]

for i in range(n):
    a, p = data[i]
    for j in range(i+1):
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + abs(n-1-j-p)*a)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(i-j-p)*a)
print(dp)
print(max(dp[-1]))

Submission status: Wrong Answer

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

B = []
for i in range(N):
  B.append((A[i],i))

B.sort(reverse = True)
ans = 0
for part in range(0,N+1): #part未満のものは右に、それ以外は左に
  tmp = 0
  i_lt = 0
  i_rt = 0
  for i in range(N):
    if B[i][1] < part:
      tmp += B[i][0] * ((N - 1 - i_lt) - B[i][1])
      i_lt += 1
    else:
      tmp += B[i][0] * (B[i][1] - i_rt)
      i_rt += 1  
  ans = max(ans, tmp)
    
print(ans)

Submission status: Wrong Answer

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

B = []
for i in range(N):
  B.append((A[i],i))

B.sort(reverse = True)
ans = 0
for part in range(0,N+1): #part未満のものは右に、それ以外は左に
  
  tmp = 0
  i_lt = 0
  i_rt = 0
  for i in range(N):
    if B[i][1] < part:
      tmp += B[i][0] * ((N - 1 - i_lt) - B[i][1])
      i_lt += 1
    else:
      tmp += B[i][0] * (B[i][1] - i_rt)
      i_rt += 1
    
  ans = max(ans, tmp)
    
print(ans)

Submission status: Wrong Answer

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

B = []
for i in range(N):
  B.append((A[i],i))

ans = 0
for part in range(0,N+1): #part未満のものは右に、それ以外は左に
  B_lt = B[:part]
  B_rt = B[part:]
  
  B_lt.sort(reverse = True)
  B_rt.sort(reverse = True)
  
  #print(B_lt)
  #print(B_rt)
  
  tmp = 0
  for i in range(len(B_lt)):
    tmp += B_lt[i][0] * ((N - 1 - i) - B_lt[i][1])
    #print(i, B_lt[i][0] * ((N - 1 - i) - B_lt[i][1]))
  for i in range(len(B_rt)):
    tmp += B_rt[i][0] * (B_rt[i][1] - i)
    #print(i, B_rt[i][0] * (B_rt[i][1] - i))
    
  ans = max(ans, tmp)
    
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = 0
r = N-1
A = list(map(int, input().split()))
for i in range(N):
  A[i] = (A[i], i)
ans = 0
#print(A)
for i in range(N):
  A[i:N] = sorted(A[i:N], key=lambda x:x[0]*max(abs(x[1]-r),abs(x[1]-l)), reverse=True)
  #print(A)
  a, x = A[i]
  if abs(x-r)>abs(x-l):
    ans += abs(x-r)*a
    r -= 1
  else:
    ans += abs(x-l)*a
    l += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = 0
r = N-1
A = list(map(int, input().split()))
for i in range(N):
  A[i] = (A[i], i)
ans = 0
for i in range(N):
  A[i:N].sort(key=lambda x:x[0]*max(abs(x[1]-r),abs(x[1]-l)), reverse=True)
  a, x = A[i]
  if abs(x-r)>abs(x-l):
    ans += abs(x-r)*a
    r -= 1
  else:
    ans += abs(x-l)*a
    l += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = 0
r = N-1
A = list(map(int, input().split()))
for i in range(N):
  A[i] = (A[i]*max(abs(i-r),abs(i-l)), i)
A.sort(key=lambda x:x[0], reverse=True)
ans = 0
for i in range(N):
  a, x = A[i]
  if abs(x-r)>abs(x-l):
    ans += abs(x-r)*a
    r -= 1
  else:
    ans += abs(x-l)*a
    l += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = 0
r = N-1
A = list(map(int, input().split()))
for i in range(N):
  A[i] = (A[i], i)
A.sort(key=lambda x:x[0], reverse=True)
ans = 0
for i in range(N):
  a, x = A[i]
  if abs(x-r)>abs(x-l):
    ans += abs(x-r)*a
    r -= 1
  else:
    ans += abs(x-l)*a
    l += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
l = 0
r = N-1
A = list(map(int, input().split()))
for i in range(N):
  A[i] = (A[i], i)
A.sort(key=lambda x:x[0])
ans = 0
for i in range(N):
  a, x = A[i]
  if abs(x-r)>abs(x-l):
    ans += abs(x-r)*a
    r -= 1
  else:
    ans += abs(x-l)*a
    l += 1
print(ans)

Submission status: Wrong Answer

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

empty=[True]*N
seen=[False]*N
arr=[]
for i in range(N):
    for j in range(N):
        arr.append((A[j]*abs(j-i),i,j))
arr.sort(reverse=True)
ans=0
res=[0]*N
for p,x,y in arr:
    if empty[x] and not seen[y]:
        ans+=p
        res[x]=y
        seen[y]=True
        empty[x]=False
print(ans)

Submission status: Wrong Answer

Solution code:
from random import shuffle
N = int(input())
A = list(map(int, input().split()))
P = list(range(N))

res = 0
for _ in range(2*N):
    R = list(range(N))
    shuffle(R)
    for _ in range(N//2):
        i = R.pop()
        j = R.pop()
        x, y = P[j], P[i]
        tmp = A[j]*abs(j-y) + A[i]*abs(i-x) - (A[j]*abs(j-x) + A[i]*abs(i-y))
        if tmp > 0:
            P[j], P[i] = y, x
            res += tmp

print(res)

Submission status: Wrong Answer

Solution code:
from random import shuffle
N = int(input())
A = list(map(int, input().split()))
P = list(range(N))
R = [i%N for i in range(N**2)]
shuffle(R)
res = 0
for _ in range(N**2//2):
    i = R.pop()
    j = R.pop()
    x, y = P[j], P[i]
    tmp = A[j]*abs(j-y) + A[i]*abs(i-x) - (A[j]*abs(j-x) + A[i]*abs(i-y))
    if tmp > 0:
        P[j], P[i] = y, x
        res += tmp

print(res)

Submission status: Wrong Answer

Solution code:
from random import sample
N = int(input())
A = list(map(int, input().split()))
P = list(range(N))
res = 0
for _ in range(N**2):
    i, j = sample(range(N), 2)
    x, y = P[j], P[i]
    tmp = A[j]*abs(j-y) + A[i]*abs(i-x) - (A[j]*abs(j-x) + A[i]*abs(i-y))
    if tmp > 0:
        P[j], P[i] = y, x
        res += tmp

print(res)

Submission status: Wrong Answer

Solution code:
from random import sample
N = int(input())
A = list(map(int, input().split()))
P = list(range(N))
res = 0
for _ in range(N**2):
    i, j = sample(P, 2)
    x, y = P[j], P[i]
    tmp = A[j]*abs(j-y) + A[i]*abs(i-x) - (A[j]*abs(j-x) + A[i]*abs(i-y))
    if tmp > 0:
        P[j], P[i] = y, x
        res += tmp

print(res)

Submission status: Wrong Answer

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, A):
    # dp[n][k] := n 人目まで見て左に k 人送ったときの最大値
    A_order = np.argsort(-A)
    dp = np.zeros((N+2, N+2), dtype=np.int64)
    for n in range(1, N+1):
        idx_A = A_order[n-1]
        a = A[idx_A]
        print(idx_A, a)
        for k in range(n+1):
            dp[n, k] = max(
                dp[n-1, k-1] + a * abs(idx_A-(k-1)) if k>0 else 0,  # 左に送る
                dp[n-1, k] + a * abs(idx_A-(N-n+k)) if k<n else 0,  # 右に送る
            )
    return dp[N].max()

numba_compile([
    [solve, "i8(i8,i8[:])"],
])

N = int(input())
A = np.array(input().split(), dtype=np.int64)
ans = solve(N, A)
print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

def calc_hapiness(x,y,a):
    return abs(x-y)*a

q = []
for i in range(n):
    for j in range(n):
        heapq.heappush(q,(-calc_hapiness(i,j,alist[i]),i,j))

used_a = [0]*(n+1)
used_new = [0]*(n+1)
cost  = 0
while used_new.count(1) != n:
    a = heapq.heappop(q)
    if used_a[a[1]] == 0 and used_new[a[2]] == 0:
        cost += a[0]
        used_a[a[1]] = 1
        used_new[a[2]] = 1

print(-cost)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array([int(x) for x in input().split()])
B = range(N)
left = 0
right = N-1
score = 0
for j in range(N):
  C = [max(B[i]-left,right-B[i])*A[i] for i in range(N-j)]
  score += max(C)
  if (B[np.argmax(C)]-left)>(right-B[np.argmax(C)]):
    left+=1
  else:
    right-=1
  A = np.delete(A,np.argmax(C))
  B= np.delete(B,np.argmax(C))
print(score)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]

total = 0
index_1 = 0
index_2 = n - 1
while lst != [0] * n:
  max_number_1 = -1
  max_index_1 = 0
  max_number_2 = -1
  max_index_2 = 0
  #print(index_1)
  #print(index_2)
  for index in range(n):
    if lst[index] != 0:
      max_1 = lst[index] * (index - index_1)
      max_2 = lst[index] * (index_2 - index)
      if max_1 > max_2:
        if max_1 > max_number_1:
          max_number_1 = max_1
          max_index_1 = index
      else:
        if max_2 > max_number_2:
          max_number_2 = max_2
          max_index_2 = index
  if max_number_1 >= max_number_2:
    total += max_number_1
    index_1 += 1
    lst[max_index_1] = 0
  else:
    total += max_number_2
    index_2 -= 1
    lst[max_index_2] = 0
  #print(total)
  #print(lst)
print(total)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]

total = 0
index_1 = 0
index_2 = n - 1
while lst != [0] * n:
  max_number_1 = -1
  max_index_1 = 0
  max_number_2 = -1
  max_index_2 = 0
  #print(index_1)
  #print(index_2)
  for index in range(n):
    if lst[index] != 0:
      max_1 = lst[index] * abs(index - index_1)
      max_2 = lst[index] * abs(index_2 - index)
      if max_1 > max_2:
        if max_1 > max_number_1:
          max_number_1 = max_1
          max_index_1 = index
      else:
        if max_2 > max_number_2:
          max_number_2 = max_2
          max_index_2 = index
  if max_number_1 > max_number_2:
    total += max_number_1
    index_1 += 1
    lst[max_index_1] = 0
  else:
    total += max_number_2
    index_2 -= 1
    lst[max_index_2] = 0
  #print(total)
  #print(lst)
print(total)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]

total = 0
index_1 = 0
index_2 = n - 1
while lst != [0] * n:
  max_number_1 = -1
  max_index_1 = 0
  max_number_2 = -1
  max_index_2 = 0
  #print(index_1)
  #print(index_2)
  for index in range(n):
    if lst[index] != 0:
      max_1 = lst[index] * (index - index_1)
      max_2 = lst[index] * (index_2 - index)
      if max_1 > max_2:
        if max_1 > max_number_1:
          max_number_1 = max_1
          max_index_1 = index
      else:
        if max_2 > max_number_2:
          max_number_2 = max_2
          max_index_2 = index
  if max_number_1 > max_number_2:
    total += max_number_1
    index_1 += 1
    lst[max_index_1] = 0
  else:
    total += max_number_2
    index_2 -= 1
    lst[max_index_2] = 0
  #print(total)
  #print(lst)
print(total)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]

total = 0
index_1 = 0
index_2 = n - 1
while lst != [0] * n:
  #print(index_1)
  #print(index_2)
  max_num = lst[0]
  max_index = 0
  for index in range(n):
    if lst[index] > max_num:
      max_num = lst[index]
      max_index = index
  max_1 = max_num * (max_index - index_1)
  max_2 = max_num * (index_2 - max_index)
  if max_1 > max_2:
    total += max_1
    index_1 += 1
  else:
    total += max_2
    index_2 -= 1
  lst[max_index] = 0
  #print(total)
  #print(lst)
print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
preans = []
for n in range(N):
    preans.append([n, As[n]])
preans.append(preans.pop(0))
judge = 0
while judge == 0:
    for _ in range(N-1):
        for n in range(N-1):
            if abs(preans[n][0] - n) >= abs(preans[n][0] - (n+1)):
                ans1 = -preans[n][1]
            else:
                ans1 = preans[n][1]
            if abs(preans[n+1][0] - (n+1)) >= abs(preans[n+1][0] - n):
                ans2 = -preans[n+1][1]
            else:
                ans2 = preans[n+1][1]
            #print(ans1, ans2)
            if ans1 + ans2 >= 0:
                preans[n], preans[n+1] = preans[n+1], preans[n]
            else:
                judge = 1
                continue
ans = 0
#print(preans)
for n in range(N):
    num = abs(preans[n][0] - n)
    ans += num * preans[n][1]
print(ans)

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))

    A = sorted(enumerate(A), key = lambda x: x[1])[::-1]

    #dp = np.zeros((N+1,N+1), dtype='int64')
    dp = [[0]*(N+1-i) for i in range(N+1)]

    for i in range(1,len(A)+1):
        index,a = A[i-1]
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (N-j-index)*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (N-j-index)*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)

    #print(dp)
    #print(np.max(dp))

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))

    A = sorted(enumerate(A), key = lambda x: x[1])[::-1]

    dp = np.zeros((N+1,N+1), dtype='int32')
    for (i,(index,a)) in enumerate(A):
        i+=1
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (abs(N-j-index))*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (abs(N-j-index))*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)

    print(np.max(dp))

main()

Submission status: Wrong Answer

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

B = list(zip(A, list(range(N))))

if N%2==0:left, right = N//2, N//2
else:left, right = N//2+1, N//2
  

B_l = B[:left]
B_r = B[right:]

C = sorted(B_r, key=lambda x: x[0], reverse=True) + sorted(B_l,key=lambda x: x[0], )

sum2 = 0
for i in range(N):
  sum2 += abs(C[i][1] - i)*C[i][0]

sum_ = 0
left = 0
right = 0
for i in range(N):
  seq1 = A*(np.arange(N)-left)
  seq2 = A*(np.arange(N)[::-1]-right)
  if max(seq1) >= max(seq2):
    sum_ += max(seq1)
    A[seq1.argmax()]=0
    left += 1
  else:
    sum_ += max(seq2)
    A[seq2.argmax()]=0
    right += 1

print(max(sum_, sum2))

Submission status: Wrong Answer

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

B = list(zip(A, list(range(N))))

if N%2==0:left, right = N//2, N//2
else:left, right = N//2+1, N//2
  

B_l = B[:left]
B_r = B[right:]

C = sorted(B_r, key=lambda x: x[0], reverse=True) + sorted(B_l,key=lambda x: x[0], )

sum_ = 0
for i in range(N):
  sum_ += abs(C[i][1] - i)*C[i][0]
print(sum_)

Submission status: Wrong Answer

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

sum_ = 0
left = 0
right = 0
for i in range(N):
  seq1 = A*(np.arange(N)-left)
  seq2 = A*(np.arange(N)[::-1]-right)
  if max(seq1) >= max(seq2):
    sum_ += max(seq1)
    A[seq1.argmax()]=0
    left += 1
  else:
    sum_ += max(seq2)
    A[seq2.argmax()]=0
    right += 1

print(sum_)

Submission status: Wrong Answer

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

move = [0 for _ in range(N)]

for i in range(1, N):
    pos = i
    for j in range(i - 1, -1, -1):
        distance = pos - j
        a1 = abs(move[pos] * A[pos]) + abs(move[j] * A[j])
        a2 = abs((move[pos] - distance) * A[pos]) + abs((move[j] + distance) * A[j])
        if a2 > a1:
            A[pos], A[j] = A[j], A[pos]
            move[pos] -= distance
            move[j] += distance
            move[pos], move[j] = move[j], move[pos]

            pos = j

print(sum(A[i] * abs(move[i]) for i in range(N)))

Submission status: Wrong Answer

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

def f(A,N):
    H=list(range(N))
    S=0
    for i in range(N):
        if i%2:
            x=N-1-(i//2)
        else:
            x=i//2

        C=0
        L=[]
        M=-1
        for j in H:
            e=A[j]*abs(x-j)
            if M<e:
                M=e
                L=[j]
                C=1
            elif M==e:
                L.append(j)
                C+=1

        if i%2:
            u=L[(len(L)-1)//2]
        else:
            u=L[len(L)//2]
        H.remove(u)
        S+=M
    return S

B=[A[-k] for k in range(1,len(A)+1)]
print(max(f(A,N),f(B,N)))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split(' ')))
b = list(range(0,n))

changed = True
ans = 0
while changed:
    changed=False
    for k in range(0,n-1):
        if b[k]<=k and k+1<=b[k+1]:
            ans+=a[b[k]]+a[b[k+1]]
            b[k],b[k+1]=b[k+1],b[k]
            changed=True
        elif k<=b[k] and k+1<=b[k+1] and a[b[k]]<a[b[k+1]]:
            ans+=a[b[k+1]]-a[b[k]]
            b[k],b[k+1]=b[k+1],b[k]
            changed=True
        elif b[k]<=k and b[k+1]<=k+1 and a[b[k]]>a[b[k+1]]:
            ans+=a[b[k]]-a[b[k+1]]
            b[k],b[k+1]=b[k+1],b[k]
            changed=True
print(ans)

Submission status: Wrong Answer

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

P=[None]*N
H=list(range(N))

S=0
for i in range(N):
    if i%2:
        x=N-1-(i//2)
    else:
        x=i//2

    C=0
    L=[]
    M=-1
    for j in H:
        e=A[j]*abs(x-j)
        if M<e:
            M=e
            L=[j]
            C=1
        elif M==e:
            L.append(j)
            C+=1

    if i%2:
        u=L[(len(L)-1)//2]
    else:
        u=L[len(L)//2]
    P[x]=u+1
    H.remove(u)
    S+=M

print(S)

Submission status: Wrong Answer

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

P=[None]*N
H=list(range(N))

S=0
for i in range(N):
    if i%2:
        x=N-1-(i//2)
    else:
        x=i//2

    C=0
    L=[]
    M=-1
    for j in H:
        e=A[j]*abs(x-j)
        if M<e:
            M=e
            L=[j]
            C=1
        elif M==e:
            L.append(j)
            C+=1

    u=L[len(L)//2]
    P[x]=u+1
    H.remove(u)
    S+=M

print(S)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
a = []
for i in range(len(A)):
    a.append([A[i], i])
a.sort(key = lambda x: x[0], reverse = True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for l in range(i+1):
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + a[i][0]*(n-1-(i-l)-a[i][1]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + a[i][0] * (a[i][1] - l))
ans = 0
print(dp)
for now in dp[n]:
    ans = max(now, ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
As = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
As.sort(key=lambda x: x[1], reverse=True)

dp = np.zeros((N+1, N+1), dtype=np.int32) #dp[x][y] = max when l=x r=y

ans = 0
for n in range(1, N+1): # x+y = n
    i, a = As[n-1]
    for m in range(n+1): # x = m
        x = m
        y = n - m
        if x > 0:
            tl = dp[x-1][y] + a * abs(i - x)
        else:
            tl = 0
        if y > 0:
            tr = dp[x][y-1] + a * abs((N-y+1) - i)
        else:
            tr = 0
        dp[x][y] = max(tl, tr)
        ans = max(ans, dp[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
As = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
As.sort(key=lambda x: x[1], reverse=True)

dp = np.zeros((N+1, N+1), dtype=np.int32) #dp[x][y] = max when l=x r=y

for n in range(1, N+1): # x+y = n
    i, a = As[n-1]
    for m in range(n+1): # x = m
        x = m
        y = n - m
        if x > 0:
            tl = dp[x-1][y] + a * abs(i - x)
        else:
            tl = 0
        if y > 0:
            tr = dp[x][y-1] + a * abs((N-y+1) - i)
        else:
            tr = 0
        dp[x][y] = max(tl, tr)

r = 0
for n in range(N+1):
    x = n
    y = N - n
    r = max(dp[x][y], r)

print(r)

Submission status: Wrong Answer

Solution code:
import itertools
N = int(input())
A = [0] + [int(_) for _ in input().split()]
list = [i+1 for i in range(N)]
comb = itertools.permutations(list, 2)
happy = []
for c in comb:
    happy.append([A[c[0]] * abs(c[0] - c[1]), c])
happy.sort(reverse=True)
fixed = [False for i in range(N+1)]
seated = [False for i in range(N+1)]
ans = 0
for h in happy:
    if not fixed[h[1][0]] and not seated[h[1][1]]:
        ans += h[0]
        fixed[h[1][0]] = True
        seated[h[1][1]] = True

print(ans)

Submission status: Wrong Answer

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

import copy

N = int(input())
A = [int(_) for _ in input().split()]

ret = 0
r = N
l = 1

B = sorted(A)

for i in range(N):
    if B == []:
        break
    _ = B[-1]
    idxs = [i+1 for i, value in enumerate(A) if value == _]

    for idx in idxs[::-1]:
        x = idx
        if abs(x - r)  > abs(x - l):
            ret += _ * abs(x-r)
            r -= 1
        else:
            ret += _ * abs(x-l)
            l += 1
        B.pop(-1)

print(ret)

Submission status: Wrong Answer

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

import copy

N = int(input())
A = [int(_) for _ in input().split()]

ret = 0
r = N
l = 1

B = sorted(A)

for i in range(N):
    if B == []:
        break
    _ = B[-1]
    idxs = [i+1 for i, value in enumerate(A) if value == _]

    for idx in idxs[::-1]:
        x = idx
        if abs(x - r)  > abs(x - l):
            ret += _ * abs(x-r)
            print(_, _ * abs(x-r), ret)
            r -= 1
        else:
            ret += _ * abs(x-l)
            print(_, _ * abs(x-l), ret)
            l += 1
        B.pop(-1)

print(ret)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
li1 = [i+1 for i in range(N)]
li2 = []
counter = 0
 
dp =[[0 for i in range(N)] for k in range(N)]
#dp[i][k] を　インデックス番号i からkに移動したときの得点とする
 
for i in range(N):
    for k in range(N):
        dp[i][k] = A[i]*max(i-k,k-i)
#print(dp)



cunter = 0
for s in range(N):
    k = []
    l = []
    for i in dp:
        k.append(max(i))
        l.append(i.index(max(i)))
    counter += max(k)
    for u in range(N):
        dp[u][l[k.index(max(k))]] = -1
        dp[k.index(max(k))][u] = -1
    #print(dp)
print(counter)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
li1 = [i+1 for i in range(N)]
li2 = []
counter = 0
 
dp =[[0 for i in range(N)] for k in range(N)]
#dp[i][k] を　インデックス番号i からkに移動したときの得点とする
 
for i in range(N):
    for k in range(N):
        dp[i][k] = A[i]*max(i-k,k-i)
print(dp)



cunter = 0
for s in range(N):
    k = []
    l = []
    for i in dp:
        k.append(max(i))
        l.append(i.index(max(i)))
    counter += max(k)
    for u in range(N):
        dp[u][l[k.index(max(k))]] = -1
        dp[k.index(max(k))][u] = -1
    print(dp)
print(counter)

Submission status: Wrong Answer

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

li1 = [i+1 for i in range(N)]
li2 = []
counter = 0

dp =[[0 for i in range(N)] for k in range(N)]
#dp[i][k] を　インデックス番号i からkに移動したときの得点とする

for i in range(N):
    for k in range(N):
        dp[i][k] = A[i]*max(i-k,k-i)




cunter = 0
for s in range(N):
    k = []
    l = []
    for i in dp:
        k.append(max(i))
        l.append(i.index(max(i)))
    counter += max(k)
    for u in range(N):
        dp[u][l[k.index(max(k))]] = -1
        dp[k.index(max(k))][u] = -1
print(counter)

Submission status: Wrong Answer

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

li1 = [i+1 for i in range(N)]
li2 = []
counter = 0

dp =[[0 for i in range(N)] for k in range(N)]
#dp[i][k] を　インデックス番号i からkに移動したときの得点とする

for i in range(N):
    for k in range(N):
        dp[i][k] = A[i]*max(i-k,k-i)
print(dp)



cunter = 0
for s in range(N):
    k = []
    l = []
    for i in dp:
        k.append(max(i))
        l.append(i.index(max(i)))
    counter += max(k)
    for u in range(N):
        dp[u][l[k.index(max(k))]] = -1
        dp[k.index(max(k))][u] = -1
    print(dp)
print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
s = list(map(int, input().split()))
index = list(range(1,N+1))

s = np.array(s).astype('int64')
index = np.array(index).astype('int64')

left = 1
right = N
ans = 0

while left<=right:
    larray = s*abs(index-left)
    rarray = s*abs(index-right)
    lmax = np.argmax(larray)
    rmax = np.argmax(rarray)

    if larray[lmax] > rarray[rmax]:
        ans += larray[lmax]
        s[lmax] = 0
        left += 1
        #print(s, left, right)
    else:
        ans += rarray[rmax]
        s[rmax] = 0
        right -= 1
        #print(s, left, right)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
s = list(map(int, input().split()))
index = list(range(1,N+1))

s = np.array(s)
index = np.array(index)

left = 1
right = N
ans = 0

while left<=right:
    larray = s*abs(index-left)
    rarray = s*abs(index-right)
    lmax = np.argmax(larray)
    rmax = np.argmax(rarray)

    if larray[lmax] > rarray[rmax]:
        ans += larray[lmax]
        s[lmax] = 0
        left += 1
        #print(s, left, right)
    else:
        ans += rarray[rmax]
        s[rmax] = 0
        right -= 1
        #print(s, left, right)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

from heapq import heappush, heappop
class PriorityQueue:

    def __init__(self):
        self.contaier = []

    def push(self, priority, value):
        heappush(self.contaier, (priority, value))

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

    def is_empty(self):
        return len(self.contaier) == 0

class Solver():

    def __init__(self, n, students):
        self.n = n
        self.students = students
        self.pq = PriorityQueue()
        self.ans = 0
        self.used_frm = [False] * (n + 1) # [0] is dummy
        self.used_to = [False] * (n + 1) # [0] is dummy

    def run(self):
        self.register()
        self.select()
        return -1 * self.ans

    def register(self):
        for i, active in enumerate(self.students):
            frm = i + 1
            for i in range(n):
                to = i + 1
                point = active * abs(frm - to)
                self.pq.push(-1 * point, (frm, to))

    def select(self):
        self.ans = 0
        while not self.pq.is_empty():
            point, (frm, to) = self.pq.pop()
            #print('self.used_frm, to') # debug
            #print(self.used_frm) # debug
            #print(self.used_to) # debug
            #print('point, frm, to') # debug
            #print(point, frm, to) # debug
            if self.used_frm[frm] or self.used_to[to]:
                continue
            #print('used') # debug
            self.ans += point
            self.used_frm[frm] = True
            self.used_to[to] = True




if __name__ == '__main__':
    n = int(input())
    students = list(map(int, input().split()))
    ans = Solver(n, students).run()
    print(ans)



    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

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

ls = [[i,A[i]] for i in range(N)]
sorted_ls = sorted(ls, key=lambda x: x[1], reverse=True)
moved = [-1 for i in range(N)]

r = N-1
l = 0
ans = 0
for x,ax in sorted_ls:
  if x-l < r-x:
    moved[r] = x
    ans += ax * (r-x)
    r -= 1
  else:
    moved[l] = x
    ans += ax * (x-l)
    l +=1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
listA=list(map(int,input().split()))
listB=[]
listC=[[]*N]
for i,happy in enumerate(listA):
  listB+=[[i,happy]]
listB.sort(key=lambda x: x[1], reverse=True)
a=0
for i in listB:  
  listC[a]=i
print(listB)

Submission status: Wrong Answer

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1], reverse=True)

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    DP[0][i] = DP[0][i-1] + abs(a[i-1][1] * (n - i + 1 - a[i-1][0]))
    DP[i][0] = DP[i-1][0] + abs(a[i-1][1] * (a[i-1][0] - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(a[i-1][1] * (a[i-1][0] - x)),  \
            DP[x][y-1] + abs(a[i-1][1] * (n - y + 1 - a[i-1][0])))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
cost=[]
for i,g in enumerate(a):
    cost.append([g,i])
cost.sort(reverse=True)


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

for i in range(n-1):
    for j in range(i+1):
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+cost[i][0]*(cost[i][1]-j))
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]+cost[i][0]*(n-1-(i-j)-cost[i][1]))

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
# 解説AC
n = int(input())
A = list(map(int, input().split()))
B = []
for i, e in enumerate(A):
    B.append((e, i + 1))
B.sort(reverse=True)
# dp[i][j]: Aiまで入れた時、左にj個決めた時の最大値
dp = [[-1] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(i + 1):  # 左の個数
        print(i, j)
        k = i - j  # 右の個数
        ni = i + 1
        val, idx = B[i]
        dp[ni][j] = max(dp[ni][j], dp[i][j] + abs(n - k - idx) * val)
        dp[ni][j + 1] = max(dp[ni][j + 1], dp[i][j] + abs(idx - (j + 1)) * val)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[n][i])
print(ans)