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: Time Limit Exceeded

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][0]*abs((N-r-1)-sortedA[i][1]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][0]*abs(l-sortedA[i][1]))
    print(max(dp[N]))

main()

Submission status: Time Limit Exceeded

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for i in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][0]*abs((N-r-1)-sortedA[i][1]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][0]*abs(l-sortedA[i][1]))
    print(max(dp[N]))

main()

Submission status: Time Limit Exceeded

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[i,a]for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, key=lambda x:x[1], reverse=True)
    # DP
    dp = [[0]*(N+1) for i in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][1]*abs((N-r-1)-sortedA[i][0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][1]*abs(l-sortedA[i][0]))
    print(max(dp[N]))

main()

Submission status: Time Limit Exceeded

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

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

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

com = permutations(range(0, N), N)

rets = []
for hoge in com:
    ret = 0
    for i, pos in enumerate(hoge):
        ret += A[i] * abs(i - pos)
    rets += [ret]
print(max(rets))

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int, input().split()))
L = [(a, i+1) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*(n+1) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n+1):
  for j in range(n+1-i):
    a, idx = L[i+j-1]
    if i:
      dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
    if j:
      dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
ans = 0
for i in range(n+1):
  ans = max(ans, dp[i][n-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n + 1):
    for j in range(n - i + 1):
        k = i + j - 1
        if k == -1:
            continue
        if i == 0:
            dp[i][j] = dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0]
        elif j == 0:
            dp[i][j] = dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0]
        else:
            dp[i][j] = max(dp[i][j - 1] + abs(b[k][1] - (n - j)) * b[k][0], dp[i - 1][j] + abs(b[k][1] - (i - 1)) * b[k][0])
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[i][n - i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(1,N+1)]
C = zip(A, B)
C = sorted(C, reverse = True)
A, B = zip(*C)
dp = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for j in range(i + 2):
        if j == 0:
            dp[0][i-j+1] = dp[0][i-j] + A[i] * (N - (i - j) - B[i])
        elif j == i+1:
            dp[j][0] = dp[j-1][0] + A[i] * (B[i] - j)
        else:
            dp[j][i-j+1] = max(dp[j][i-j] + A[i] * (N - (i - j) - B[i]), dp[j-1][i-j+1] + A[i] * (B[i] - j))
ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Als = list(enumerate(list(map(int, input().split()))))#これで(index,value)
dp = [[0]*(N+2) for i in range(N+2)]
ans = 0
Bls = sorted(Als,key=lambda tup:-tup[1])
dp[0][0] = 0
dp[1][0] = Bls[0][1]*(N-(Bls[0][0]+1))
dp[0][1] = Bls[0][1]*(Bls[0][0]+1 - 1)
dp[1][1] = max(dp[1][0]+Bls[1][1]*(Bls[1][1]+1 -1),dp[0][1]+Bls[1][1]*(N -(Bls[1][0]+1)))
Bls.append((N,0))
for sum in range(1,N+1):#x+yの総和がもう決まってる和
    v = Bls[sum][1]#このループで試す対象を取り出しとく　和が１まで決まってるから２番目のを取り出す
    ind = Bls[sum][0]+1
    for i in range(sum+1):#iがx側でjがy側
        j = sum-i
        if j==0:
            ne = N-i
            a = ne - ind
            dp[i+1][0] = dp[i][0]+a*v
        elif i==0:
            ns = j+1
            b = ind - ns
            dp[0][j+1] = dp[0][j]+b*v
        if j !=0:
            ne = N - i#かかるdpの状態に応じて次の位置を決める
            a = ne - ind
            ns = j
            b = ind - ns
            dp[i+1][j] = max(dp[i][j]+a*v,dp[i+1][j-1]+b*v)
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#  入力
N = int(input())
A = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    a = max(A)
    id = A.index(a)
    
    for x in range(0,i+1):
        y = i - x

        d = dp[x][y]
        tmp = d + a * (id - x)
        if dp[x+1][y] < tmp:
        	dp[x+1][y] = tmp
        tmp = d + a * (((N-1)-y) - id)            
        if dp[x][y+1] < tmp:
        	dp[x][y+1] = tmp
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time

#  入力
N = int(input())
A = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    a = max(A)
    id = A.index(a)
    
    for x in range(0,i+1):
        y = i - x

        d = dp[x][y]
        tmp = d + a * (id - x)
        if dp[x+1][y] < tmp:
        	dp[x+1][y] = tmp
        tmp = d + a * (((N-1)-y) - id)            
        if dp[x][y+1] < tmp:
        	dp[x][y+1] = tmp
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#  入力
N = int(input())
A = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    id = A.index(max(A))
    a = A[id]
    for x in range(0,i+1):
        y = i - x

        # print("{}回目 x {}, y {}".format(i, x, y))
        # print("{}, {}点　移動係数 x {}, y {}".format(id, A[id], id - x, ((N-1)-y) - id))
        
        dp[x+1][y] = max(dp[x+1][y], dp[x][y] + a * (id - x))
        # print("x", A[id], id, id - x, dp[x+1][y])
        dp[x][y+1] = max(dp[x][y+1], dp[x][y] + a * (((N-1)-y) - id))
        # print("y", A[id], id, ((N-1)-y) - id, dp[x][y+1])
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#  入力
N = int(input())
A = [int(x) for x in input().split()]
 
# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
 
for i in range(0,N):
 
    # 最も嬉しさの高い子供から場所を選択していく
    id = A.index(max(A))
    
    for x in range(0,i+1):
        y = i - x
        
        dp[x+1][y] = max(dp[x+1][y], dp[x][y] + A[id] * (id - x))
        dp[x][y+1] = max(dp[x][y+1], dp[x][y] + A[id] * (((N-1)-y) - id))
        
    A[id] = 0

ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

from sys import stdin


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

    a2 = [[a[i], i] for i in range(n)]
    a2.sort(reverse=True)

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

    ans = 0

    for i in range(n + 1):
        for j in range(n + 1 - i):
            s1 = s2 = 0
            if i > 0:
                s1 = dp[i - 1][j] + a2[i + j - 1][0] * (a2[i + j - 1][1] - (i - 1))
            if j > 0:
                s2 = dp[i][j - 1] + a2[i + j - 1][0] * ((n - j) - a2[i + j - 1][1])
            dp[i][j] = np.max([s1, s2])
        ans = np.max([ans, dp[i][n - i]])

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E
N = int(input())
A = list(map(int,input().split()))
B = []
for i in range(N):
    B.append([A[i],i+1])
    
B.sort(reverse=True)

DP = [[0 for _ in range(N+1)] for _ in range(N+1)] #dp[x][y] x->1,2,3... y->N,N-1,N-2...
for i in range(N):
    I = i+1
    b,ind = B[i]
    
    for j in range(I+1):
        if j == 0:
            DP[j][I-j] = DP[j][I-j-1] + b*abs(N-(I-j)-ind+1)
        elif I-j == 0:
            DP[j][I-j] = DP[j-1][I-j] + b*abs(ind-j)
        else:
            DP[j][I-j] = max(DP[j][I-j-1]+b*abs(N-(I-j)-ind+1),DP[j-1][I-j]+b*abs(ind-j))
        
        
ans = 0
for i in range(N+1):
    ans = max(ans,DP[i][N-i])
    
#print(B)
print(ans)

Submission status: Time Limit Exceeded

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

A = [[A[i],i] for i in range(N)]
A.sort()

dp = [[0]*(N+1) for i in range(N+1)]

ans = 0
for i in range(N+1):
    for j in range(N+1):
        if i+j>N:
            continue
        if i+j==0:
            continue
        a,k = A[-i-j]
        if i==0:
            dp[i][j] = dp[i][j-1]+a*(N-j-k)
        elif j==0:
            dp[i][j] = dp[i-1][j]+a*(k-i+1)
        else:
            dp[i][j] = max(dp[i-1][j]+a*(k-i+1),dp[i][j-1]+a*(N-j-k))
        ans = max(ans,dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

import itertools
list2 = [ perm for perm in itertools.permutations(range(1,N+1))]
res=0
for perm in list2:
    score=0
    #print(perm)
    
    for i in range(len(list1)):
        #print(abs(i+1 - perm[i]))
        score += list1[i] * abs(i+1 - perm[i])
    if score > res:
        res = score
    #print(score)
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
active = list(map(int, input().split(" ")))
active = [ [active[i],i+1] for i in range(N) ]
active.sort(reverse=True)
dp = [ [0]*(N+1) for _ in range(N+1) ]

for l in range(1, N+1) :
    idx = l-1
    a = active[idx]
    for i in range(l) :
        dp[l-i][i] = max(dp[l-i][i], dp[l-i-1][i] + abs(l-i-a[1])*a[0] ) 
        dp[i][l-i] = max(dp[i][l-i], dp[i][l-i-1] + abs(N+1-l+i-a[1])*a[0] ) 

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
active = list(map(int, input().split(" ")))
active = [ (active[i],i+1) for i in range(len(active)) ]
active.sort(reverse=True)
dp = [ [0]*(N+1) for _ in range(N+1) ]

for l in range(1, N+1) :
    idx = l-1
    for i in range(l) :
        dp[l-i][i] = max(dp[l-i][i], dp[l-i-1][i] + abs( (l-i) - active[idx][1])*active[idx][0] ) 
        dp[i][l-i] = max(dp[i][l-i], dp[i][l-i-1] + abs( (N+1 -l+i) - active[idx][1])*active[idx][0] ) 

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[(a[i],i)for i in range(n)]
b.sort(reverse=1)
dp=[(n+1)*[0]for _ in range(n+1)]
for i in range(1,n+1):
  p,j=b[i-1]
  if j<i-1:break
  dp[i][0]+=dp[i-1][0]+p*(j-(i-1))
for i in range(1,n+1):
  p,j=b[i-1]
  if j>(n-i):break
  dp[0][i]+=dp[0][i-1]+p*((n-i)-j)
ans=0
for i in range(1,n):
  for j in range(1,n):
    if i+j>n:break
    p,k=b[i+j-1]
    if (i-1)<=k:
      dp[i][j]=max(dp[i][j],dp[i-1][j]+p*(k-(i-1)))
    if k<=(n-j):
      dp[i][j]=max(dp[i][j],dp[i][j-1]+p*((n-j)-k))
  ans=max(ans,dp[i][n-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[(a[i],i)for i in range(n)]
b.sort(reverse=1)
dp=[(n+1)*[0]for _ in range(n+1)]
for i in range(1,n+1):
  p,j=b[i-1]
  if j<i-1:break
  dp[i][0]+=dp[i-1][0]+p*(j-(i-1))
for i in range(1,n+1):
  p,j=b[i-1]
  if j>(n-i):break
  dp[0][i]+=dp[0][i-1]+p*((n-i)-j)
for i in range(1,n):
  for j in range(1,n):
    if i+j>n:break
    p,k=b[i+j-1]
    if (i-1)<=k:
      dp[i][j]=max(dp[i][j],dp[i-1][j]+p*(k-(i-1)))
    if k<=(n-j):
      dp[i][j]=max(dp[i][j],dp[i][j-1]+p*((n-j)-k))
ans=0
for i in range(n+1):ans=max(ans,dp[i][n-i])
print(ans)

Submission status: Time Limit Exceeded

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

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

a = [list(a[i]) for i in range(n)]
a = [[a[i][0]+1, a[i][1]] for i in range(n)]

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: Time Limit Exceeded

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

a_ = []
for i,v in enumerate(a):
    a_.append([i+1,v])
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: Time Limit Exceeded

Solution code:
# 解説AC
import sys
input = sys.stdin.buffer.readline

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):  # 左の個数
        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)

Submission status: Time Limit Exceeded

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):  # 左の個数
        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)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[int]"):
    A_ = []
    indices = []
    tmp = sorted(enumerate(A), reverse=True, key=lambda x:x[1])
    for row in tmp:
        k, v = row
        indices.append(k)
        A_.append(v)
    A = A_
    
    dp = [[0 for i in range(N+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(0, N-i):
            a = A[i+j]
            idx = indices[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N-i]
        if tmp > result:
            result = tmp
    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: Time Limit Exceeded

Solution code:
# My Answer -> TLE
N = int(input())
A = list(map(int, input().split()))

a = [(i, ai) for i, ai in enumerate(A)]
a = sorted(a, key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

dp = [[0] * (N + 1) for _ in range(N + 1)]

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

a = [(i, ai) for i, ai in enumerate(A)]
a.sort(key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

dp = [[0] * (N + 1) for _ in range(N + 1)]

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted([(a, i) for i, a in enumerate(map(int, input().split()))], reverse=True)
dp = [[0]*(N+1) for _ in [0]*(N+1)]

for j, (a, i) in enumerate(A):
    for l in range(j+1):
        r = N-1-(j-l)
        dp[j+1][l] = max(dp[j+1][l], dp[j][l]+a*(r-i))
        dp[j+1][l+1] = max(dp[j+1][l+1], dp[j][l]+a*(i-l))

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

b = [ (a,i) for i,a in enumerate(a)]

b.sort(reverse=True)

dp=[ [0] * (n+1) for i in range(n+1) ]

ans=0

for l in range(n):
  for r in range(n):
    if l + r == n:
      ans = max( ans, dp[l][r] )
      break
    act , i = b[l+r]
    dp[l+1][r] = max( dp[l+1][r] , dp[l][r] +act*abs(i-l))
    dp[l][r+1] = max( dp[l][r+1] , dp[l][r] +act*abs(n-i-1-r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = []
for i in range(a):
    dp.append([0]*(a-i))

# dp = [[0] * a for i in range(a)]

# cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    v = vi[0]
    p = vi[1]
    vi_z = vilist[0]
    vz = vi_z[0]
    pz = vi_z[1]
    for i in range(k + 2):
        # cnt += 1
        j = k - i + 1
        # if i == 0 and j == 0:
        #     continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                               dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                               dp[i][j-1] + v * abs(a - j - p))

# print(cnt)
print(max([max(x) for x in dp]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = []
for i in range(a):
    dp.append([0]*(a-i))

# dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    v = vi[0]
    p = vi[1]
    vi_z = vilist[0]
    vz = vi_z[0]
    pz = vi_z[1]
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                               dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
            else:
                dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                               dp[i][j-1] + v * abs(a - j - p))

# print(cnt)
print(max([max(x) for x in dp]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = []
for i in range(a):
    dp.append([])
    for j in range(a-i):
        dp[i].append(0)
# dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            vi_z = vilist[0]
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(a - j - 1 - vi_z[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(vi_z[1] - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]))

# print(cnt)
print(max([max(x) for x in dp]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0])

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    vi = vilist.pop()
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            vi_z = vilist[0]
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(a - j - 1 - vi_z[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1) + vi_z[0] * abs(vi_z[1] - i),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]) + vi_z[0] * abs(vi_z[1] - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + vi[0] * abs(vi[1] - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vi[0] * abs(a - j - vi[1])
            else:
                dp[i][j] = max(dp[i-1][j] + vi[0] * abs(vi[1] - i + 1),
                               dp[i][j-1] + vi[0] * abs(a - j - vi[1]))

# print(cnt)
print(max([max(x) for x in dp]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
nums = list(map(int, input().split()))

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0], reverse=True)

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = [[0] * a for i in range(a)]

cnt = 0
# dp[i][j]を考える
for k in range(a-1):
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        # 最後の値は場所が特定できるのでそのまま計算させる
        if k == a - 2:
            if j == 0:
                dp[i][0] = dp[i-1][0] + vilist[-2][0] * abs(vilist[-2][1] - i + 1) + vilist[-1][0] * abs(vilist[-1][1] - i)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vilist[-2][0] * abs(a - j - vilist[-2][1]) + vilist[-1][0] * abs(a - j - 1 - vilist[-1][1])
            else:
                dp[i][j] = max(dp[i-1][j] + vilist[-2][0] * abs(vilist[-2][1] - i + 1) + vilist[-1][0] * abs(vilist[-1][1] - i),
                               dp[i][j-1] + vilist[-2][0] * abs(a - j - vilist[-2][1]) + vilist[-1][0] * abs(vilist[-1][1] - i))
        else:
            if j == 0:
                dp[i][0] = dp[i-1][0] + vilist[k][0] * abs(vilist[k][1] - i + 1)
            elif i == 0:
                dp[0][j] = dp[0][j-1] + vilist[k][0] * abs(a - j - vilist[k][1])
            else:
                dp[i][j] = max(dp[i-1][j] + vilist[k][0] * abs(vilist[k][1] - i + 1),
                               dp[i][j-1] + vilist[k][0] * abs(a - j - vilist[k][1]))

# print(cnt)
print(max([max(x) for x in dp]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 整数の入力
a = int(input())
# # スペース区切りの整数の入力
# strs = input().split()

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

vilist = []
for i in range(a):
    vilist.append((nums[i], i))
vilist = sorted(vilist, key=lambda vi: vi[0], reverse=True)

# dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
dp = [[0] * a for i in range(a)]
# for i in range(a + 1):
#     ls = ([0] * a) * a
#     ls *
#     dp.append(ls)

cnt = 0
# dp[i][j]を考える
for k in range(a-2):
    for i in range(k + 2):
        cnt += 1
        j = k - i + 1
        if i == 0 and j == 0:
            continue

        if j == 0:
            dp[i][0] = dp[i-1][0] + vilist[k][0] * abs(vilist[k][1] - i + 1)
        elif i == 0:
            dp[0][j] = dp[0][j-1] + vilist[k][0] * abs(a - j - vilist[k][1])
        else:
            dp[i][j] = max(dp[i-1][j] + vilist[k][0] * abs(vilist[k][1] - i + 1),
                           dp[i][j-1] + vilist[k][0] * abs(a - j - vilist[k][1]))

# 最後の値は場所が特定できるのでそのまま計算させる
k = a - 2
for i in range(k + 2):
    cnt += 1
    j = k - i + 1
    if j == 0:
        dp[i][0] = dp[i-1][0] + vilist[-2][0] * abs(vilist[-2][1] - i + 1) + vilist[-1][0] * abs(vilist[-1][1] - i)
        # dp[i+1][0] = dp[i][0] + vilist[-1][0] * abs(vilist[-1][1] - i)
    elif i == 0:
        dp[0][j] = dp[0][j-1] + vilist[-2][0] * abs(a - j - vilist[-2][1]) + vilist[-1][0] * abs(a - j - 1 - vilist[-1][1])
        # dp[0][j+1] = dp[0][j]
    else:
        dp[i][j] = max(dp[i-1][j] + vilist[-2][0] * abs(vilist[-2][1] - i + 1) + vilist[-1][0] * abs(vilist[-1][1] - i),
                       dp[i][j-1] + vilist[-2][0] * abs(a - j - vilist[-2][1]) + vilist[-1][0] * abs(vilist[-1][1] - i))


# print(cnt)
print(max([max(x) for x in dp]))