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):
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[1e18]*n
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[min(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
print(-min(d))

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

Solution (Python):
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)
 
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
 
  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)
 
main()

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

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

Solution (Python):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = np.array(read().split(), np.int64)
I = np.argsort(A)[::-1].tolist()
A = A[I].tolist()

dp = np.zeros(1, np.int64)

for n, (i, x) in enumerate(zip(I, A)):
    newdp = np.zeros(len(dp) + 1, np.int64)
    left_ind = np.arange(len(dp))
    right_ind = N - 1 - n + left_ind
    left_cost = x * np.abs(left_ind - i)
    right_cost = x * np.abs(right_ind - i)
    np.maximum(newdp[:-1], dp + right_cost, out=newdp[:-1])
    np.maximum(newdp[1:], dp + left_cost, out=newdp[1:])
    dp = newdp

print(dp.max())

Solution (Python):
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n=inp()
a = inpl()
sorted_a = sorted(a,reverse=True)
place=dict()
for i in range(n):
    if a[i] not in place:
        place[a[i]]=[i+1]
    else:
        place[a[i]].append(i+1)
ans = 0
dp=[[-INF]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    if i!=0 and sorted_a[i] == sorted_a[i - 1]:
        index += 1
    else:
        index = 0
    for j in range(n):
        _place = place[sorted_a[i]][index]
        
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + sorted_a[i] * abs(n - (i - j) - _place))
        
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + sorted_a[i] *  abs(_place - j - 1))

print(max(dp[n]))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())








A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[None for r in range(n+1)] for l in range(n+1)]


def dp(l, r):
    if l == r:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    a, i = A[n-(r-l)]
    x = dp(l+1, r)+a*abs(i-l)
    y = dp(l, r-1)+a*abs(i-r+1)
    DP[l][r] = max(x, y)
    return DP[l][r]


print(dp(0, n))

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

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

lis = sorted(org, key=lambda x: x[1], reverse=True)

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


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

ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, dp[i][j])
        
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)]
for i, (v, p) in enumerate(a):
    
    dp[i+1][0] = dp[i][0] + v*abs((n-1 - i) - p)
    for j in range(1, i+1):
        dp[i+1][j] = max(dp[i][j] + v*abs((n-1 - (i-j)) - p),
                         dp[i][j-1] + v*abs((j-1) - p))
    dp[i+1][i+1] = dp[i][i] + v*abs(i - p)
print(max(dp[n]))

Solution (Python):
def solve():
        
    N = int(input())
    A = [(a, i+1) for i, a in enumerate(map(int, input().split()))]

    A.sort(reverse=True)
    INF = float('inf')
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

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

    ans = 0
    for m in range(N):
        if dp[m][N-m] > ans:
            ans = dp[m][N-m]

    print(ans)
solve()

Solution (Python):
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

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

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

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

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

Solution (Python):



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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]


ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1] 
    a=As[i] 
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    


print(max(ds))

Solution (Python):

from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
babies=[(q,i) for i,q in enumerate(a)]
babies.sort(reverse=True)

dp=defaultdict(int)
ans=0
for l in range(n):
  for r in range(n):
    if l+r==n:
      ans=max(ans,dp[(l,r)])
      break
    act,ind=babies[l+r]
    dp[(l+1,r)]=max(dp[(l+1,r)],dp[(l,r)]+act*abs(ind-l))
    dp[(l,r+1)]=max(dp[(l,r+1)],dp[(l,r)]+act*abs(ind-(n-1-r)))

print(ans)

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

Solution (Python):
n = int(input())
*A, = map(int, input().split())




A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[0 for r in range(n+1)] for l in range(n+1)]
for l in range(n):
    for r in range(n-l):
        a, i = A[l+r]
        DP[l+1][r] = max(DP[l+1][r], DP[l][r]+a*abs(i-l))
        DP[l][r+1] = max(DP[l][r+1], DP[l][r]+a*abs(i-(n-1-r)))
print(max([DP[l][n-l] for l in range(n)]))

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]
 
def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res
 
print(solve(0, N-1))

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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=1)


dp = list2d(N+1, N+1, -INF)
dp[0][0] = 0
for i, (a, x) in enumerate(A):
    
    for j in range(i+1):
        
        k = i - j
        
        y = j
        dp[j+1][k] = max(dp[j+1][k], dp[j][k] + abs(x - y) * a)
        
        y = N - 1 - k
        dp[j][k+1] = max(dp[j][k+1], dp[j][k] + abs(x - y) * a)
ans = 0
for i in range(N+1):
    
    ans = max(ans, dp[i][N-i])
print(ans)

Solution (Python):
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

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

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

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

Solution (Python):



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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]


ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1]
    a=As[i]
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    


print(max(ds))

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

Solution (Python):
N=int(input());A=sorted((int(x),i)for i,x in enumerate(input().split()));t=[0]*N**2
for w in range(N):
 a,j=A[w]
 for l in range(N-w):
  r=l+w;p=a*abs(j-l);t[l*N+r]=max(p+t[(l+1)*N+r],a*abs(j-r)+t[l*N+r-1])if w else p
print(t[N-1])

Solution (Python):
e=enumerate
n,*a=map(int,open(0).read().split())
dp=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):dp=[dp[0]+a*abs(n-j-i-1)]+[max(dp[k]+a*abs(n-j+k-i-1),dp[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[dp[j]+a*abs(i-j)]
print(max(dp))

Solution (Python):
e=enumerate
n,*a=map(int,open(0).read().split())
dp=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):dp=[dp[0]+a*abs(n-j-i-1)]+[max(dp[k]+a*abs(n-j+k-i-1),dp[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[dp[j]+a*abs(i-j)]
print(max(dp))

Solution (Python):
N = int(input())
a = map(int,input().split())
A = sorted([(b,a) for a, b in enumerate(a)])[::-1]
dp = [[-1 for _ in range(N+10)]for _ in range(N+10)]

dp[0][0] = 0
import sys
sys.setrecursionlimit(100000000)

def memo(x, y):
    if x < 0 or y < 0: return -1000000000000 
    if dp[x][y] != -1: return dp[x][y]
    val, pre = A[x+y-1][0], A[x+y-1][1]
    dp[x][y] = max(
            
            memo(x - 1,y) + abs(pre - (x - 1)) * val,
            
            memo(x, y - 1) + abs(pre - (N - y )) *val,
            )
    return dp[x][y]
ans = 0
for i in range(N): ans = max(ans, memo(i,N - i))
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,(input().split())))
B = [(0)*2 for _ in range(N)]
for i in range(N):
    B[i] = (A[i],i)
B.sort(reverse=True)

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

ans = []
for l in range(N+1):
    for r in range(N+1):
        if l+r == N:
            ans.append(dp[l][r])
            break
        if r+1 < N+1:
            dp[l][r+1] = max(dp[l][r+1], dp[l][r] + B[l+r][0] * abs(B[l+r][1] - (N-(r+1)) ))
        if l+1 < N+1:
            dp[l+1][r] = max(dp[l+1][r], dp[l][r] + B[l+r][0] * abs(B[l+r][1] - l))

print(max(ans))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]
dp[1][0]=dp[0][0]+B[0][0]*(B[0][1]-1)
dp[0][1]=dp[0][0]+B[0][0]*(N-B[0][1])
for k in range(1,N):
    
    dp[0][k+1]=dp[0][k]+B[k][0]*(N-k-B[k][1])
    dp[1][k]=max(dp[0][k]+B[k][0]*(B[k][1]-1), dp[1][k-1]+B[k][0]*(N-k+1-B[k][1]))
    
    dp[k+1][0]=dp[k][0]+B[k][0]*(B[k][1]-k-1)
    dp[k][1]=max(dp[k-1][+1]+B[k][0]*(B[k][1]-k), dp[k][0]+B[k][0]*(N-B[k][1]))
    for j in range(1,k):
        dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))

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

for i in range(n):
    a[i] = [a[i],i]
l1 = 0
r1 = n-1
l2 = l1
r2 = r1
a.sort(reverse=1)
dp = [[0]*(n+1) for i in range(n+1)]
ans = 0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + a[i-1][0] * abs(a[i-1][1]-i+1)
    dp[0][i] = dp[0][i-1] + a[i-1][0] * abs(n-(a[i-1][1])-i)
    for j in range(1,i):
        dp[j][i-j] = max(dp[j-1][i-j]+a[i-1][0]*abs(a[i-1][1]-j+1),dp[j][i-j-1]+a[i-1][0]*abs(n-(a[i-1][1])-(i-j)))
for i in dp:
    ans = max(ans,max(i))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]

def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res

print(solve(0, N-1))

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

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

A2=[(num,ind) for ind,num in enumerate(A)]
A2.sort(reverse=True)

L=[0]*N

for i in range(N):
    num,ind=A2[i]
    NL=[0]*N
    for j in range(i+1):
        right=N-1-(i-j)
        NL[j]=max(NL[j],abs(right-ind)*num+L[j])

        if j!=N-1:
            NL[j+1]=max(NL[j+1],abs(j-ind)*num+L[j])
    L=NL
print(max(L))

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
A = inputIL()

dic = [[INF,0]]

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

dic.sort(reverse=True)

table = [[0 for i in range(N+1)] for j in range(N+1)]


for n in range(1,N+1):
  for i in range(n+1):
    if i == 0:
      table[n][0] = table[n-1][0] + dic[n][0] * (dic[n][1] -n)
    elif i == n:
      table[0][n] = table[0][n-1] + dic[n][0] * (N -(n-1) - dic[n][1])
    else:
      table[n-i][i] = max(table[n-i-1][i] + dic[n][0] * (dic[n][1] -(n-i)), table[n-i][i-1] + dic[n][0] * (N -(i-1) - dic[n][1]))
  
m = 0
for i in range(0,N+1):
  m = max(m,table[N-i][i])
  
print(m)

Solution (Python):


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


p = list(range(n))
p.sort(key=lambda i: a[i])


dp = [0] * (n + 1)

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

print(dp[0])

Solution (Python):


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


p = list(range(n))
p.sort(key=lambda i: a[i])


dp = [0] * (n + 1)

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

print(dp[0])

Solution (Python):
import sys

sys.setrecursionlimit(2 * 10 ** 5)

N = int(input())

A = [int(x) for x in input().split()]
A = sorted((a, i) for i, a in enumerate(A))

cache = [[None for i in range(N + 1)] for j in range(N + 1)]


def dp(l, r):
    if l > r:
        return 0
    if cache[l][r] is None:
        a, x = A[r - l]
        cache[l][r] = max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))
    return cache[l][r]


print(dp(0, N - 1))

Solution (Python):
N = int(input())
A = sorted([(int(a), i) for i, a in enumerate(input().split())], key = lambda x: x[0])[::-1]
X = [0] + [-1<<100] * (N + 5)
for k, (a, i) in enumerate(A):
    X = [max(X[j] + abs(N - (k - j) - 1 - i) * a, X[j-1] + abs(j - 1- i) * a if j else 0) for j in range(N + 5)]
print(max(X))

Solution (Python):


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


p = list(range(n))
p.sort(key=lambda i: a[i])


dp = {(j, 0): 0 for j in range(n + 1)}

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

print(dp[(0, n)])

Solution (Python):
def solve(n, aaa):
    dp = [0]
    aaa_with_idx = list(zip(aaa, range(n)))
    aaa_with_idx.sort(reverse=True)
    for k in range(1, n + 1):
        ndp = [0] * (k + 1)
        a, i = aaa_with_idx[k - 1]
        for l in range(k):
            
            ndp[l + 1] = max(ndp[l + 1], dp[l] + a * abs(i - l))
            
            r = n - (k - l)
            ndp[l] = max(ndp[l], dp[l] + a * abs(i - r))
        dp = ndp
    return max(dp)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

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)]
x_plus_y = 0
ans = 0

for i in range(n):
    if x_plus_y == 0:
        dp[0][1] = a[i][0] * abs((n - a[i][1]))
        dp[1][0] = a[i][0] * abs((a[i][1] - 1))

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

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

    x_plus_y += 1

print(ans)

Solution (Python):
def main():
  N = int(input())
  A = list(map(int,input().split()))
  A = [[a,i] for a,i in zip(A,range(1,N+1))]
  A = sorted(A,reverse=True)
  INF = float('inf')
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
  ans = 0
  for x_y in range(1,N+1):
    a = A[x_y-1]
    for x in range(x_y+1):
      y = x_y-x
      if x==0:
        dp[x][y] = dp[x][y-1] + a[0]*(N-y+1-a[1])
      elif y==0:
        dp[x][y] = dp[x-1][y] + a[0]*(a[1]-x)
      else:
        dp[x][y] = max(dp[x-1][y]+a[0]*(a[1]-x),dp[x][y-1] + a[0]*(N-y+1-a[1]))

      ans = max(ans,dp[x][y])
  print(ans)
  
main()

Solution (Python):
import copy
n = int(input())
a = list(map(int, input().split()))
array = [(a[i], i+1) for i in range(n)]
array.sort(reverse=True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for j in range(n):
        if i + j >= n:
            break
        count = i + j
        
        value, index = array[count]
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + value * abs((n - j) - index))
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + value * abs((i + 1) - index))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, dp[i][j])
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
A = [[a,i] for a,i in zip(A,range(1,N+1))]
A = sorted(A,reverse=True)
INF = float('inf')
dp = [[-INF] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for x_y in range(1,N+1):
  a = A[x_y-1]
  for x in range(x_y+1):
    y = x_y-x
    if x==0:
      dp[x][y] = dp[x][y-1] + a[0]*(N-y+1-a[1])
    elif y==0:
      dp[x][y] = dp[x-1][y] + a[0]*(a[1]-x)
    else:
      dp[x][y] = max(dp[x-1][y]+a[0]*(a[1]-x),dp[x][y-1] + a[0]*(N-y+1-a[1]))
    
    ans = max(ans,dp[x][y])
print(ans)

Solution (Python):
def solve():
    N = int(input())
    
    AAwIdx = [(i,A) for i, A in enumerate(map(int, input().split()))]
    
    
    
    AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
    

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

    ans_all = 0
    Idx_i = 0
    Idx_f = N-1
    for i in range(0,N):
        for no in range(i+1):
            idxi = i-no
            idxf = Idx_f-no
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1]
            if ans>answer[i+1-no][no]:
                answer[i+1-no][no] = ans
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1]
            if ans>answer[i-no][no+1]:
                answer[i-no][no+1] = ans
    for i in range(N,N+1):
        for no in range(i+1):
            if ans_all<answer[i-no][no]:
                ans_all = answer[i-no][no]

    print(ans_all)
solve()

Solution (Python):
def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()

Solution (Python):


n=int(input())
lists=list(map(int,input().split()))
data=[]
for i in range(n):
    data.append((lists[i],i+1))
data=sorted(data,key=lambda x:-x[0])







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

dp[1][1]=n*(data[0][0])-data[0][0]*data[0][1]
dp[1][0]=data[0][0]*data[0][1]-data[0][0]

for i in range(2,n+1):
    
    for j in range(i+1):
        x=data[i-1][0]
        y=data[i-1][1]
        
        
        if i>j>=1:
            dp[i][j]=max(dp[i-1][j-1]+x*(n+1-j)-x*y,dp[i-1][j]-(i-j)*x+x*y)
        elif j==0:
            dp[i][j]=dp[i-1][0]-i*x+x*y
        elif j==i:
            dp[i][j]=dp[i-1][i-1]+x*(n+1-j)-x*y        
K=0
for i in range(n+1):
    K=max(K,dp[n][i])
print(K)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    infants = [(ai, i) for i, ai in enumerate(A)]
    infants.sort(reverse=True)
    
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    ans = 0
    for x in range(N):
        for y in range(N):
            if x + y == N:
                ans = max(ans, dp[x][y])
                break
            act_level, idx = infants[x + y]
            dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + act_level * abs(idx - x))
            dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + act_level * abs(idx - (N - y - 1)))
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)           

def main():
    n = int(input())
    a = list(enumerate(map(int,input().split())))
    a.sort(key = lambda x:x[1],reverse = True)

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

    for j in range(n):
        i,num = a[j]
        i += 1
        for k in range(j + 2):
            if k == 0:
                dp[j + 1][k] = dp[j][k] + num * abs(i - n + j - k)
            else:
                dp[j + 1][k] = max(dp[j][k - 1] + num * abs(i - k),dp[j][k] + num * abs(i - n + j - k))
            
    print(max(dp[-1]))
if __name__ =='__main__':
    main()

Solution (Python):
n=int(input())
l=list(map(int,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]
e=[]
for i in range(n):
    e.append([l[i],i])
e.sort(reverse=True)
for i in range(1,n+1):
    p=e[i-1][0]
    q=e[i-1][1]
    for j in range(i+1):
        if j<i:
            a1=dp[i-1][j]+p*abs(n-(i-j)-q)
        else:
            a1=0
        if j>0:
            a2=dp[i-1][j-1]+p*abs(q-j+1)
        else:
            a2=0
        dp[i][j]=max(a1,a2)
print(max(dp[-1]))

Solution (Python):
N=int(input())
*A,=map(int, input().split())
B=[(i+1,a) for i,a in enumerate(A)]
from operator import itemgetter
B.sort(reverse=True, key=itemgetter(1))

dp = [[-1] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    idx, act = B[i-1]
    for j in range(i+1):
        k = i-j
        if 0<j: dp[j][k] = max(dp[j][k], dp[j-1][k] + act * abs(idx-j))
        if 0<k: dp[j][k] = max(dp[j][k], dp[j][k-1] + act * abs(idx-(N-k+1)))

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

Solution (Python):
N = int(input())
_L = list(map(int,input().split()))
L = [(v,i) for i,v in enumerate(_L)]
L = sorted(L,key=lambda x:(-x[0]))

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

ans=0
for x in range(N):
    for y in range(N):
        cur = x+y
        if  cur==N:
            ans = max(ans,dp[x][y])
            break
        val,ind = L[cur]
        dp[x+1][y] = max(dp[x+1][y],dp[x][y]+val*abs(ind-x))
        dp[x][y+1] = max(dp[x][y+1],dp[x][y]+val*abs(N-y-1-ind))
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
参考にしました(写経)
https://atcoder.jp/contests/abc163/submissions/12137623

Axが大きい順に置ける部分の中で一番左か一番右に置きたい
dp[i][j]:左からi個目, 右からj個目まで埋まっているときの最大値
i個目を見ているとき左と右に埋まっている数はi-1個なので
dp[i][j]は(左の個数,右の個数) = (0,i-1),(1,i-2),...とO(N)で探索できる
"""
n = I()
a = LI()
b = [[a[i],i] for i in range(n)]
b.sort(reverse=1)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    a,j = b[i]
    for k in range(i+1):
        dp[k][i+1-k] = max(dp[k][i+1-k], dp[k][i-k] + a*abs(j-((n-1)-(i-k)))) 
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a*abs(j-k)) 
ans = 0
for i in range(n):
    ans = max(ans, dp[i][n-i])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N = int(input())

A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, reverse=True)

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

values = sorted(values, reverse=True)
ans = 0

dp_indices = []
for v in values:
    dp_indices.extend(num_indcies[v])


dp = [[0] * (N+1) for _ in range(N+1)]
for no, (a, pos) in enumerate(A):
    for i in range(no+1):
        j = no - i
        
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * (pos -i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a * abs(pos - (N-1-j)))

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