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:
'''
着想：大きいaほど左右の端に移動したい、小さいaを先に端にやるより必ず大きくなるから
問題：単純に貪欲に大きいaから左端(x-1)と右端(N-x)の大きい方に移動すると、
      残りのaの組み合わせ的に最適でない場合がある
      アイテムの左右端の単純な割り振りはO(2^N)
解決策の着想：大きい順のk個を(k=L+R)となる
    　　左L個右R個にどのように割り振っても(k+1)個目の最適な割り振り方は変わらない
解決策：アイテムk個左右に割り振る状態をdp[L][R]で保存O(N^2)
'''

N = int(input())
A = [[a, i] for a,i in zip(map(int, input().split()), range(N))]
A.sort(key=lambda a: a[0], reverse=True)

dp = [[0]*(N+1) for _ in range(N+1)] # 左からxマス右からyマス埋める
for i in range(0,N):
  a, l = A[i]
  for x in range(0,i+1):
    y = i - x # 合計x+y=iマス既に埋まっている、次にi+1マス目を考える
    dp[x+1][y] = max(dp[x+1][y], dp[x][y] + a * abs(l - x))
    dp[x][y+1] = max(dp[x][y+1], dp[x][y] + a * abs(l - (N-y-1)))

print(max(dp[N-i][i] for i in range(N+1)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(enumerate(map(int,input().split())))
a.sort(key=lambda x: -x[1])
dp=[[0]*(n+1) for i in range(n+1)]
for idx,ix in enumerate(a):
    i,x=ix
    for j in range(idx+1):
        dp[j+1][idx-j]=max(dp[j+1][idx-j],dp[j][idx-j]+(i-j)*x)
        dp[j][idx-j+1]=max(dp[j][idx-j+1],dp[j][idx-j]+((n-1-(idx-j))-i)*x)
print(max([dp[i][n-i] for i in range(n+1)]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
A = []
for i in range(n):
    A.append([a[i], i])
A.sort(reverse=True)
for i in range(1, n+1):
    for j in range(i+1):
        if j == 0:
            dp[j][i-j] = dp[j][i-j-1] + A[i-1][0] * abs(n-i-A[i-1][1])
        elif j == i:
            dp[j][i-j] = dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-i+1)
        else:
            dp[j][i-j] = max(dp[j][i-j-1] + A[i-1][0] * abs(n-i+j-A[i-1][1]), dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-j+1))
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()))

babies=[(a,i) for i,a in enumerate(a)]
babies.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
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[r+1][r],dp[l][r]+abs(ind-l)*activeness)
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = tuple(sorted(ab,key=itemgetter(0),reverse=True))
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

B = sorted([(A[i], i + 1) for i in range(N)], reverse=True)
dp = defaultdict(int)

for S in range(1, N + 1):
    for x in range(S + 1):
        y = S - x
        candid = []
        if x >= 1:
            candid.append(dp[(x - 1, y)] + B[S - 1][0]
                          * (B[S - 1][1] - x))
        if y >= 1:
            candid.append(dp[(x, y - 1)] + B[S - 1][0]
                          * ((N - y + 1) - B[S - 1][1]))
        dp[(x, y)] = max(candid)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import itertools
# 整数の入力
n = int(input())
before = list(map(int, input().split()))
li = []
for i in range(n):
    li.append(i)
# 計算
after = list(itertools.permutations(li)) # 順列を生成
ans = 0
for t in after:
    temp = 0
    for i in range(n):
        temp += abs(t[i]-i)*before[i]
    # print(t, temp)
    if ans < temp:
        ans = temp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = sorted(ab,key=itemgetter(0),reverse=True)
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    if j >= 1:
      dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
    if j == 0:
      dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
print(max(dp[n]))

Submission status: Time Limit Exceeded

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

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

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

DP = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
  n, x = D[i]
  t = i + 1
  for j in range(t + 1):
    l = j
    r = t - j
    rr = N - 1 - r
    if l != 0:
      DP[l][r] = DP[l - 1][r] + abs(n - l + 1) * x
    if r != 0:
      DP[l][r] = max(DP[l][r], DP[l][r - 1] + abs(rr + 1 - n) * x)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**7)

n = 0
a = []

sorted_a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**3)
		a = [rng(1, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

	global sorted_a
	sorted_a = list(reversed(sorted(a)))

@lru_cache(maxsize=None)
def sum_happiness(left, right):
	if left + right >= n:
		return 0
	activeness = sorted_a[left + right]
	indexes = [i for i in range(n) if a[i] == activeness]
	offset = left + right - sorted_a.index(activeness)

	left_happiness = activeness * (indexes[offset] - left) + sum_happiness(left + 1, right)
	right_happiness = activeness * (n - 1 - right - indexes[offset]) + sum_happiness(left, right + 1)
	return max(left_happiness, right_happiness)

def get_answer():
	return sum_happiness(0, 0)

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3

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


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

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        for i in range(n):
            j = n - 1 - i

            left = dp[i][j] + p[0] * abs(p[1] - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            
            right = dp[i][j] + p[0] * abs(p[1] - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys
sys.setrecursionlimit(10**5)

def f(x, po, h, t, ple):
    if po=='h':
        ple+=B[x][1]*abs(B[x][0]-h)
        h+=1
    else:
        ple+=B[x][1]*abs(B[x][0]-t)
        t-=1
    if h>t:
        return ple
    
    ans1=f(x+1, 'h', h, t, ple)
    ans2=f(x+1, 't', h, t, ple)
    return max(ans1, ans2)

N=int(input())
A=list(map(int, input().split()))
B=[[i, A[i]] for i in range(N)]
B=sorted(B, key=itemgetter(1), reverse=True)
h=0
t=N-1
ans1=f(0, 'h', h, t, 0)
ans2=f(0, 't', h, t, 0)
print(max(ans1, ans2))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
N=int(input())
A=list(map(int, input().split()))
B=[[i, A[i]] for i in range(N)] 
B=sorted(B, key=itemgetter(1), reverse=True)

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

for x in range(N):
    dp[x+1][0]=dp[x][0]+B[x][1]*abs(B[x][0]-x)
    
for y in range(N):
    dp[0][y+1]=dp[0][y]+B[y][1]*abs(N-1-y-B[y][0])
    
for z in range(2, N+1):
    for x in range(1, z):
        y=z-x
        dp[x][y]=max(dp[x][y-1]+B[z-1][1]*abs(N-y-B[z-1][0]), dp[x-1][y]+B[z-1][1]*abs(x-1-B[z-1][0]))
        
print(max([dp[x][N-x] for x in range(N+1)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n = int( input() )
  a = list( map( int, input().split() ) )
  aa = np.zeros((n,2))
  for i in range(n):
    aa[i][0] = a[i]
    aa[i][1] = i
  a2 = np.ndarray.argsort(aa, axis=0)
  for i in range(n):
    tmp = a2[i][0]
    a2[i][0] = aa[ tmp ][0]
    a2[i][1] = aa[ tmp ][1]
  for i in range(n):
    print("",end="")
    aa[i][0] = a2[ i ][0]
    aa[i][1] = a2[ i ][1]
  aa = aa[::-1]
  dp =   np.zeros(n+10)
  dppre = np.zeros(n+10)
  for i in range(n):
    for j in range(i+5):
      dppre[j] = dp[j]
      dp[j] = 0
    for j in range(i+1):
      dp[j+1] = max(dp[j+1], dppre[j] + aa[i][0] *  abs(aa[i][1]-j)   )
      dp[j]   = max(dp[j],   dppre[j] + aa[i][0] *  abs(aa[i][1]-(n-1-i+j))  )
  ans = int(max(dp))
  print(ans)
  

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int, input().split()))
r = []
for i, x in enumerate(l):
    r.append((x, i))
r.sort(reverse=True)
s = {(0, n-1): 0}
result = 0

for i, x in r:
    # print("HERE: ", i, x)
    new = {}
    for (left, right), value in s.items():
        # print(left, right, value)
        if left==right:
            result = max(result, value + abs(left-x)*i)
            continue
        if (left+1, right) in new:
            new[(left+1, right)] = max(new[(left+1, right)], value + abs(left-x)*i)
        else:
            new[(left+1, right)] = value + abs(left-x)*i
            
        if (left, right-1) in new:
            new[(left, right-1)] = max(new[(left, right-1)], value + abs(right-x)*i)
        else:
            new[(left, right-1)] = value + abs(right-x)*i
            
    s = new
    
print(result)

Submission status: Time Limit Exceeded

Solution code:


N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - 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:
# スコアが高い順に右端 or 左端に置く事を考える
# dp[i][l] : l番目まで左に子がいる状態でi番目の子を動かす時の最大値
n = int(input())
tmp = [int(x) for x in input().split()]

aList=[]
for i in range(n):
    aList.append([tmp[i],i])

aList.sort(reverse=True)

dp=[[int(-1) for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0

# スコアが高い順にi人動かす
for i in range(n):
    # 左側に置いた人数。i番目のループでは0〜i人まで左端に置く可能性がある
    for l in range(i+1):
        activity = aList[i][0]
        pos = aList[i][1]

        # 右端の今のポジション
        # totalで置いた数-左側に置いた数(i-l)を計算し、右端(n-1)から引く
        r = n-1-(i-l)

        # 左に置いた場合
        dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l] + abs(l-pos) * activity)

        # 右に置いた場合
        dp[i+1][l]   = max(dp[i+1][l],dp[i][l] + abs(r-pos) * activity)

print(max(dp[n]))

Submission status: Time Limit Exceeded

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

p = []
for i, v in enumerate(A):
  p.append((v, i))
  
p.sort(reverse=True)

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

for i in range(n):
  k = p[i][0]
  r = p[i][1]
  for x in range(i + 1):
    y = i - x
    dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * k)
    dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (n - 1 - y)) * k)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
  n = int( input() )
  a = list( map( int, input().split() ) )
  aa = []
  for i in range(n):
    aa += [[a[i],i]]
  aa.sort(reverse = True)
  dp = np.zeros(n+10)
  dppre = np.zeros(n+10)
  for i in range(n):
    for j in range(i+5):
      dppre[j] = dp[j]
      dp[j] = 0
    for j in range(i+1):
      dp[j+1] = max(dp[j+1], dppre[j] + aa[i][0] *  abs(aa[i][1]-j)   )
      dp[j]   = max(dp[j],   dppre[j] + aa[i][0] *  abs(aa[i][1]-(n-1-i+j))  )
  ans = int(max(dp))
  print(ans)
  

main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
l=[[] for _ in range(ma+1)]
chk=[0]*n
ans=0
for i,x in enumerate(a):
    l[x].append(i)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(ma,0,-1):
    for j in l[i]:
        for x in range(cnt+1):
            if x==0:
                dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
            elif x==cnt:
                dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
            else:
                dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
        cnt+=1
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 in range(N):
  A.append([i+1,a[i]])


A.sort(key=lambda x: x[1], reverse=True)


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


for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

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

Submission status: Time Limit Exceeded

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

def solve(N: int, A: "List[int]"):
    a=np.argsort(A)[::-1]

    dp = np.zeros((N+1,N+1))
    for i, a_ind in enumerate(a):
        x_p_y = i+1
        a_ = A[a_ind]
        # print("a_ : {}, a_ind : {}".format(a_, a_ind))
        for x in range(0, x_p_y+1):
            y = x_p_y - x
            if x-1<0: x_add = 0
            else : x_add = dp[x-1, y] + a_*abs(a_ind-x+1)
            if y-1<0: y_add = 0
            else : y_add = dp[x, y-1] + a_*abs((N-y) - a_ind)

            # print(x_add, y_add)
            dp[x, x_p_y-x] = max(x_add, y_add)
    print(int(np.max(dp)))

    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:
def main():
    N = int(input())
    A = list(map(int, input().split()))

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

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

    for i, b in enumerate(B):
        a = b[0]
        tmp = b[1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

    ans = 0
    for i, dp in enumerate(DP):
        ans = max(ans, dp[N - i])

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

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

    for i, b in enumerate(B):
        a = b[0]
        tmp = b[1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

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

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

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

    for i in range(N):
        a = B[i][0]
        tmp = B[i][1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

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

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    B = [(A[i], i) for i in range(N)]
    B.sort(key = lambda x: x[0], reverse = True)

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

    for i in range(N):
        a = B[i][0]
        tmp = B[i][1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

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

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

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(key = lambda x: x[0], reverse = True)

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

for i in range(N):
    a = B[i][0]
    tmp = B[i][1]
    for x in range(i + 1):
        DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
        DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

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

print (ans)

# for tmp in DP:
#     print (tmp)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[[int(_),0] for _ in input().split()]
for i in range(n): a[i][1]=i
a.sort(reverse=True)
dp=[[0 for _ in range(n)] for __ in range(n)]
for l in range(n):
    for r in range(n):
        if l+r < n:
            if l<n-1:dp[l+1][r]=max(dp[l+1][r], dp[l][r]+a[l+r][0]*abs(a[l+r][1]-l))
            if r<n-1:dp[l][r+1]=max(dp[l][r+1], dp[l][r]+a[l+r][0]*abs(a[l+r][1]-(n-r-1)))
print(max([dp[i][n-i] for i in range(1,n)]))

Submission status: Time Limit Exceeded

Solution code:
#S = input()
#S1, S2 = input().split()
N = int(input())
#I, K, N  = map(int, input().split())
AA = list(map(int, input().split()))

#D1 = []
#D2 = [[]] * 4
#D1 = [0] * 5
#D2 = [[0] * 5 for i in range(4)]
#D3 = [[[0] * 5 for i in range(4)] for i in range(3)]

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

A = []
for i in range(N):
  A += [[AA[i], i]]
A.sort(reverse=True, key=lambda x:x[0])

mx=0
for i in range(N):
  for pl in range(i+1):
    pr = i - pl
    al = abs(A[i][1]-pl)*A[i][0]
    ar = abs((N-1-pr)-A[i][1])*A[i][0]
    dp[pl][pr+1] = max( dp[pl][pr+1],dp[pl][pr] + ar )
    dp[pl+1][pr] = max( dp[pl+1][pr],dp[pl][pr] + al )
    mx = max(mx,dp[pl][pr+1],dp[pl+1][pr])

print(mx)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted([(v,k) for k,v in enumerate(list(map(int, input().split())))], reverse=True)
dp = [[-(10 ** 18)] * (n+1) for i in range(n+1)]
dp[0][0] = 0
for i,(v,k) in enumerate(a):
  for j in range(i+1):
    left = j
    right = n-1-(i-j)
    dp[i+1][j] = max(dp[i+1][j], dp[i][j] + v * abs(k-right))
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + v * abs(k-left))
print(max(dp[i+1]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(yb-(i+1))
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1)-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        a, i = A_l[j+k-1]
        j_plus = a*(yb-(i+1))
        k_plus = a*((i+1)-ys)
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    x = A_l[j-1][1] + 1
#    if yb-i <0:
#        dp[j][0] = -float('inf')
#    else:
    dp[j][0] = dp[j-1][0] + A_l[j-1][0]*(yb-x)
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    x = A_l[k-1][1] + 1
#    if i-ys <0:
#        dp[0][k] = -float('inf')
#    else:
    dp[0][k] = dp[0][k-1] + A_l[k-1][0]*(x-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        x = A_l[j+k-1][1] + 1
        j_plus = A_l[j+k-1][0]*(yb-x)
        k_plus = A_l[j+k-1][0]*(x-ys)
        if j_plus <0:
            j_plus = -float('inf')
        elif k_plus <0:
            k_plus = -float('inf')
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort()
A_l.reverse()

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    x = A_l[j-1][1] + 1
#    if yb-i <0:
#        dp[j][0] = -float('inf')
#    else:
    dp[j][0] = dp[j-1][0] + A_l[j-1][0]*(yb-x)
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    x = A_l[k-1][1] + 1
#    if i-ys <0:
#        dp[0][k] = -float('inf')
#    else:
    dp[0][k] = dp[0][k-1] + A_l[k-1][0]*(x-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        x = A_l[j+k-1][1] + 1
        j_plus = A_l[j+k-1][0]*(yb-x)
        k_plus = A_l[j+k-1][0]*(x-ys)
#        if j_plus <0:
#            j_plus = -float('inf')
#        elif k_plus <0:
#            k_plus = -float('inf')
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.array(A)
I = np.argsort(A)[::-1] + 1

p = np.zeros(shape=(N + 1, N + 1), dtype=np.int)
for i in range(1, N + 1):
  # i      : Aが大きい順
  # x      : A*(i-p); p=1,2,...
  # y      : A*(p-i); p=N,N-1,...
  # p[x][y]: 左からx人、右からy人並べた時の嬉しさ合計の最大値
  # >> p[1][0]: 最大Aを左から1番目に並べた時の嬉しさ
  # >> p[0][1]: 最大Aを左からN番目に並べた時の嬉しさ
  # >> p[1][1]: max(p[0][1] + 2番目Aを左から1番目に並べた時の嬉しさ,
  #                 p[1][0] + 2番目Aを左からN番目に並べた時の嬉しさ)
  j = i - 1
  J = I[j] - 1
  p[i][0] = p[j][0] + A[J]*abs((I[j] - i))
  p[0][i] = p[0][j] + A[J]*abs(((N - j) - I[j]))

  for x in range(1, i):
    y = i - x

    p[x][y] = max(
      p[x - 1][y] + A[J]*abs((I[j] - x)),
      p[x][y - 1] + A[J]*abs(((N - (y - 1)) - I[j])))

print(p.max())

Submission status: Time Limit Exceeded

Solution code:
import sys
 
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
 
n = ni()
a = nl()
lis = [(e, i) for i, e in enumerate(a)]
lis.sort()

dp = [[-1]*n for _ in range(n)]
 
def solve(l, r):
    if l > r:
        return 0
    idx = r - l
    e, i = lis[idx]
    return max(abs(i-l)*e + solve(l+1, r), abs(r-i)*e + solve(l, r-1))
print(solve(0, n-1))

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<=(s:=dp[i][j]+c*abs(i-k)):dp[i+1][j]=s
		if dp[i][j+1]<=(s:=dp[i][j]+c*abs(n-1-k-j)):dp[i][j+1]=s
print(max(dp[i][~i]for i in range(n+1)))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted(a, reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
def f(s,e):
  return abs(e-s)*a[s]
for i in range(n):
  d = a.index(b[i])
  for l in range(0,i+1):
    r = i-l
    dp[l+1][r] = max(dp[l+1][r], dp[l][r]+f(d,l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r]+f(d,n-r-1))
  a[d] = 0
for i in range(n+1):
  ans = max(ans, dp[i][n-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a)|1 and (SA:=SA+a)|1 and (SB:=SB+b)|1 and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from itertools import *

N = int(input())

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

ABI = sorted(((a, max(N-i, i-1)*a, i) for i, a in enumerate(A, 1)), reverse=True)
SA, SB = map(sum, islice(zip(*ABI), 0, 2))

prev = {(0,0):0}
prev_max = 0
for a, b, i in ABI:
  curr = defaultdict(int)
  curr_max = 0
  for (l,r), p in prev.items():
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l,r+1] = max(curr[l,r+1], p+abs(N-i-r)*a)
    curr[l+1,r] = max(curr[l+1,r], p+abs(i-l-1)*a)
    curr_max = max(curr_max, curr[l,r+1], curr[l+1,r])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]
A.sort(reverse=True)

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

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

ans = max([max(d) for d in dp])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=sorted([(v,i+1) for i,v in enumerate(list(map(int,input().split())))],reverse=1)
dp=[[0]*(n+1) for i in range(n+1)]
for ko in range(1,n+1):
    for x in range(ko+1):
        ret=0
        v,i=l[ko-1]
        y=ko-x
        if y>=1:ret=max(ret,dp[x][y-1]+abs(n-y+1-i)*v)
        if x>=1:ret=max(ret,dp[x-1][y]+abs(x-i)*v)
        dp[x][y]=ret
print(max(dp[a][n-a] for a in range(n+1)))