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

Solution (Python):
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, 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)

    
    

if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
N = int(input())
A = [int(s) for s in input().split(" ")]
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr
 
print(max(prev))

Solution (Python):
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)]))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

aa = [[a[i],i] for i in range(n)]

aa.sort(reverse = True)

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

for i in range(1,n+1):
    on = aa[i-1]
    for j in range(i+1):
        if j-1 >= 0:
            dp[i-j][j] = max(dp[i-j][j-1] + on[0] * abs(on[1] - (n-1 - (j - 1))),dp[i-j][j])
            """
            if i == 1:
                print(dp[i-j][j-1] + on[0] * abs(on[1] - j),dp[i-j][j])
            """
        if i-j-1 >= 0:
            
            dp[i-j][j] = max(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """
            if i == 1:
                print(on,(n-1 - (i-j)),n-1,i-j)
                print(dp[i-j-1][j],on[0] * abs(on[1] - (n-1 - (i-j))))
                print(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """

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

Solution (Python):
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]))

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

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): 
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(n-(j-1) - (i+1))
for k in range(1,n+1): 
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1) - (1+(k-1)))

for j in range(1,n+1):
    for k in range(1,n-j+1):
        a, i = A_l[j+k-1]
        j_plus = a*(n-(j-1) - (i+1))
        k_plus = a*((i+1) - (1+(k-1)))
        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)

Solution (Python):
def e_active_infants():
    
    N = int(input())
    A = [int(i) for i in input().split()]
    
    p = sorted([(a, k) for k, a in enumerate(A)], reverse=True)

    
    
    dp = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0  
    for i in range(N):
        a, r = p[i]
        for x in range(i + 1):
            y = i - x
            
            dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * a)
            dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (N - 1 - y)) * a)
    return max(dp[i][N - i] for i in range(N + 1))

print(e_active_infants())

Solution (Python):

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

children = [(a, i) for i, a in enumerate(A)]

children.sort(reverse=True)




dp = [[0] * (N + 1) for _ 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, idx = children[l + r]
        dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(idx - l) * activeness)
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + abs(idx - (N - 1 - r)) * activeness)

print(ans)

Solution (Python):
def main():
    from random import sample
    from operator import itemgetter
    e=enumerate
    n,a=open(0)
    n=int(n)
    d=[0]+[-2**64]*n
    for j,(a,i)in e(sorted(sample([(a,i)for i,a in e(map(int,a.split()))],n),key=itemgetter(0),reverse=1)):
        d=[max(t+a*(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
    print(max(d))
main()

Solution (Python):
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)

prev = [0]
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a

  prev = curr

print(max(prev))

Solution (Python):
def main():
	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)))

if __name__ == '__main__':
	main()

Solution (Python):
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, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = [0]
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    r = k-l
    if prev[l] + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], prev[l]+abs(N-i-r)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev)

print(prev_max)

Solution (Python):
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]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print(max(dp[i][~i]for i in range(n+1)))

Solution (Python):
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)

Solution (Python):
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, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

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

print(prev_max)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

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

b = []
for i in range(n):
    b.append(a[i]*n + i)
b.sort(reverse = True)

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

ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)

Solution (Python):
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, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

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

print(curr_max)

Solution (Python):
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, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

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

print(curr_max)

Solution (Python):
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])

Solution (Python):
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 = 0
for i in range(N + 1):
    ans = max(ans, dp[i][N - i])
print(ans)

Solution (Python):
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)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n = II()
    a = [(i, j) for (i, j) in zip(LI(), range(n))]
    a.sort(reverse=True)
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n):
        dp[i + 1][0] = dp[i][0] + a[i][0] * abs(a[i][1] - i)
        dp[0][i + 1] = dp[0][i] + a[i][0] * abs(a[i][1] - (n - (i + 1)))
        for l in range(1, i + 1):
            r = i - l + 1
            dp[l][r] = max(dp[l - 1][r] + a[i][0] * abs(a[i][1] - (l - 1)),
                            dp[l][r - 1] + a[i][0] * abs(a[i][1] - (n - r)))
    ans = 0
    for r in range(n + 1):
        l = n - r
        ans = max(ans, dp[l][r])
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
a = [(int(x), i) for i, x in enumerate(input().split())]
a.sort(reverse=True)
aval, ai = zip(*a)
dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(n):
    for r in range(n):
        if l + r >= n: break
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + aval[l+r] * abs(ai[l+r]-l))
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + aval[l+r] * abs(ai[l+r]-(n-r-1)))

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

Solution (Python):
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)))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = [[a,i] for a,i in zip(A,range(N))]
A = sorted(A,reverse=True)

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

for n in range(0,N+1):
    for y in range(0,n+1):
        x = n-y
        a = A[n-1]
        ind = a[1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+a[0]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+a[0]*abs(ind-(x-1)),dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

print(ans)

Solution (Python):
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

Solution (Python):

n = int(input())
a = list(map(int,input().split()))
ans = [[0 for i in range(n+1)] for j in range(n+1)]
p = []


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


for i in range(1,n+1):
    ans[0][i] = ans[0][i-1] + p[i-1][0]*abs(p[i-1][1]-i+1)
for i in range(1,n+1):
    ans[i][0] = ans[i-1][0] + p[i-1][0]*abs(n-i-p[i-1][1])


for i in range(1,n):
    for j in range(1,n-i+1):
        ans[i][j] = max(ans[i][j-1] + p[i+j -1][0]*abs(p[i+j -1][1]-j+1),
        ans[i-1][j] + p[i+j - 1][0]*abs(n-i-p[i+j-1][1]))


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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ans = [[0 for i in range(n+1)] for j in range(n+1)]
p = []
for i in range(n):
    p.append([a[i],i])
p.sort(reverse=True)

for i in range(1,n+1):
    ans[0][i] = ans[0][i-1] + p[i-1][0]*abs(p[i-1][1]-i+1)
for i in range(1,n+1):
    ans[i][0] = ans[i-1][0] + p[i-1][0]*abs(n-i-p[i-1][1])

for i in range(1,n):
    for j in range(1,n-i+1):
        ans[i][j] = max(ans[i][j-1] + p[i+j -1][0]*abs(p[i+j -1][1]-j+1),
        ans[i-1][j] + p[i+j - 1][0]*abs(n-i-p[i+j-1][1]))

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

Solution (Python):
n = int(input())
a_ = [int(i) for i in input().split()]
a = [[a_[i], i+1] for i in range(n)]
a.sort(reverse=True)

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

        if x_plus_y == n-1:
            ans = max(ans, dp[x][y+1], dp[x+1][y])

print(ans)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
b = [(a[i],i) for i in range(n)]
b.sort(reverse=True)
ddprint(b)
d = [[0]*(n+1) for i in range(n+1)]
for i in range(n):
    v,j = b[i]
    ddprint(f"i {i} v {v} j {j}")
    d[i+1][0] = d[i][0] + v*abs(n-1-i-j) 
    d[i+1][i+1] = d[i][i] + v*abs(j-i) 
    for k in range(1,i+1):
        v1 = d[i][k-1]+v*abs(j-k+1)  
        v2 =  d[i][k]+v*abs(n-1-i+k-j) 
        ddprint(f"k {k} v1 {v1} v2 {v2} d1 {d[i][k-1]} d0 {d[i][k]} x1 {k-i} x2 {n-1-i+k-j}")
        d[i+1][k] = max(v1,v2)
    if DBG:
        ddprint(i)
        ddprint(d[i+1])
print(max(d[n]))

Solution (Python):
import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))

L = list(range(N))
L.sort(key = lambda x: A[x], reverse = True)

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

for s in range(N):
    l = L[s]
    a = A[l]
    for i in range(s+1):
        j = s-i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+a*abs(l-i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j]+a*abs(l-(N-s+i-1)))
ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Solution (Python):
n = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
for L in range(n+1):
    for R in range(n+1):
        if n <= L+R-1:
            continue
        a, i = A[L+R-1]
        if 0 <= R-1:
            dp[L][R] = max(dp[L][R], dp[L][R-1]+abs((n-R)-i)*a)
        if 0 <= L-1:
            dp[L][R] = max(dp[L][R], dp[L-1][R]+abs(i-(L-1))*a)
        ans = max(ans, dp[L][R])
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    dp = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(i+1):
            x,y = j,i-j
            dp[x+1][y] = max(dp[x+1][y],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-x)))
            dp[x][y+1] = max(dp[x][y+1],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-(N-y-1))))

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

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(n + 1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = dp.copy()

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    dp_new[1:k+1] = np.maximum(dp_new[1:k+1], dp[:k] + add_left)

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    dp_new[:k] = np.maximum(dp_new[:k], dp[:k] + add_right)

    dp = dp_new

ans = dp.max()
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = np.append(dp, 0)

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    np.maximum(dp_new[1:k+1], dp[:k] + add_left, out=dp_new[1:k+1])

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    np.maximum(dp_new[:k], dp[:k] + add_right, out=dp_new[:k])

    dp = dp_new

ans = dp.max()
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(n + 1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = dp.copy()

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    dp_new[1:k+1] = np.maximum(dp_new[1:k+1], dp[:k] + add_left)

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    dp_new[:k] = np.maximum(dp_new[:k], dp[:k] + add_right)

    dp = dp_new

ans = dp.max()
print(ans)

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(reverse=True)
dp=[[0 for i in range(N+1)] for _ in range(N+1)]
for n in range(N):
    a,p=A[n]
    for x in range(1,n+2):
        y=n+1-x
        dp[x][y]=max(dp[x][y],dp[x-1][y]+round(abs(x-1 - p))*a)
    for y in range(1,n+2):
        x=n+1-y
        dp[x][y]=max(dp[x][y],dp[x][y-1]+round(abs(N-y - p))*a)
    
print(max([dp[x][y] for x in range(N+1) for y in range(N+1) if x+y==N]))

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(n + 1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = dp.copy()

    add_left = e * abs(np.arange(1, k + 1) - i)
    dp_new[1:k+1] = np.maximum(dp_new[1:k+1], dp[:k] + add_left)

    add_right = e * abs(np.arange(n - k + 1, n + 1) - i)
    dp_new[:k] = np.maximum(dp_new[:k], dp[:k] + add_right)

    dp = dp_new.copy()

ans = max(dp)
print(ans)

Solution (Python):
from operator import itemgetter

def main():
    n = int(input())
    a = sorted(enumerate(map(int, input().split())), key=itemgetter(1), reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for x in range(n):
        for y in range(n - x):
            i, ai = a[x + y]
            dp[x + 1][y] = max(ai * (i - x) + dp[x][y], dp[x + 1][y])
            dp[x][y + 1] = max(ai * (n - 1 - y - i) + dp[x][y], dp[x][y + 1])
    print(max(dp[i][n - i] for i in range(n)))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = [[e, i] for i, e in enumerate(a, 1)]

a.sort(reverse=True)

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

for t, (e, idx) in enumerate(a, 1):
    for i in range(1, t + 1):
        j = t - i
        dp[i][j] = max(dp[i][j], dp[i-1][j] + e * abs(idx - i))

    for j in range(1, t + 1):
        i = t - j
        dp[i][j] = max(dp[i][j], dp[i][j-1] + e * abs(idx - (n - j + 1)))

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

print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	n = int(input())
	al = list(IN())
	
	
	tl=[(v,i+1) for i,v in enumerate(al)]
	tl.sort(reverse=True)
	
	th = lambda f,t:100000*f + t
	fh = lambda hv : (hv//100000, hv%100000)
	
	ss = th(1,n)
	dd={ss:0}
	for uresisa, pos in tl:
		ndd={}
		for dk in dd:
			pu=dd[dk]
			f, t =fh(dk)
			temp_dkf = uresisa*abs(f-pos)+pu
			h=th(f+1, t)
			if h not in ndd:
				ndd[h] = temp_dkf
			else:
				ndd[h] = max(ndd[h], temp_dkf)
			
			temp_dkt = uresisa*abs(t-pos)+pu
			h=th(f, t-1)
			if h not in ndd:
				ndd[h]=temp_dkt
			else:
				ndd[h]=max(ndd[h], temp_dkt)
		else:
			dd=ndd
			
			
			
	rr=0
	for d in dd:
		rr=max(rr, dd[d])
	return rr
			
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys
from pprint import pprint
readline = sys.stdin.readline

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

inds = [v[1] for v in sorted([(a, i) for i, a in enumerate(A)], reverse=True)]

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

for y in range(N + 1):
    for x in range(N - y + 1):
        if x == 0 and y == 0:
            continue
        
        t = inds[x + y - 1]
        if y == 0:
            dp[y][x] = dp[y][x - 1] + A[t] * (t - (x - 1))
        elif x == 0:
            dp[y][x] = dp[y - 1][x] + A[t] * ((N - y) - t)
        else:
            dp[y][x] = max(dp[y][x - 1] + A[t] * (t - (x - 1)),
                dp[y - 1][x] + A[t] * ((N - y) - t))

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    AI = [(a, i) for i, a in enumerate(A)]
    AI.sort(reverse = 1)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for l in range(n):
        for r in range(n):
            if l + r >= n:
                break
            a, i = AI[l + r]
            dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(i - l) * a)
            dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + abs((n - r - 1) - i) * a)
    print(max(dp[i][n - i] for i in range(n)))
resolve()

Solution (Python):
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-2**64]*n
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

Solution (Python):
N = int(input())
A = [int(i) for i in input().split(' ')]

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)

Solution (Python):
e=enumerate
n,a=open(0)
d=[0]+[-1e18]*2000
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*(~i-j+k+int(n)),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

Solution (Python):
e=enumerate
n,a=open(0)
d=[0]+[-1e18]*2001
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*abs(~i-j+k+int(n)),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

Solution (Python):
def main():
    n=int(input())
    d=[0]+[-10**18]*n
    for j,(a,i)in enumerate(sorted((-a,i)for i,a in enumerate(map(int,input().split())))):
        d=[max(t-a*abs(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in enumerate(d)]
    print(max(d))
main()

Solution (Python):
n=int(input())
d=[0]+[-10**18]*n
for j,(a,i)in enumerate(sorted((-a,i)for i,a in enumerate(map(int,input().split())))):
    d=[max(t-a*abs(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in enumerate(d)]
print(max(d))