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):
if __name__ == '__main__':
	N = int(input())
	Als = [int(a) for a in input().split()]
	lst = []
	for i in range(N):
		lst.append([Als[i],i+1])

	lst.sort(reverse = True)

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

	ans = 0

	for i in range(1,N+1):
		a = lst[i-1][0]
		index = lst[i-1][1]
		vx = DP[i-1][0] + a * abs(index-i)
		vy = DP[0][i-1] + a * abs(index-(N-i+1))
		DP[i][0] = vx
		DP[0][i] = vy
		if ans < vx:
			ans = vx
		if ans < vy:
			ans = vy

	for i in range(1,N+1):
		for j in range(1,N+1):
			if i + j <= N:
				a = lst[i+j-1][0]
				index = lst[i+j-1][1]
				v = max(DP[i-1][j] + a * abs(index-i),DP[i][j-1] + a * abs(index-(N-j+1)))
				DP[i][j] = v
				if ans < v:
					ans = v
			else:
				break

	print(int(ans))

Solution (Python):
import sys
import numpy as np
def f(n,a_):
      a=[]
      for i,ai in enumerate(a_):
            a.append([1+i,ai])
      a.sort(key=lambda x:x[1],reverse=True)
      dp=np.zeros((n+1,n+1),np.int64) 
      dp[1,1]=a[0][1]*(n-a[0][0])
      dp[1,0]=a[0][1]*(a[0][0]-1)
      for i in range(2,n+1):
            dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) 
            dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) 
            
            l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] 
            
            r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] 
            dp[i,1:i]=np.maximum(l,r)
      return max(dp[n])

if __name__ == '__main__':
      input = sys.stdin.readline
      n=int(input())
      a_=list(map(int,input().split()))
      print(f(n,a_))

Solution (Python):
from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
import numpy as np
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=np.zeros((n+1,n+1),np.int64) 
dp[1,1]=a[0][1]*(n-a[0][0])
dp[1,0]=a[0][1]*(a[0][0]-1)
for i in range(2,n+1):
      dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) 
      dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) 
      
      l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] 
      
      r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] 
      dp[i,1:i]=np.maximum(l,r)
print(max(dp[n]))

Solution (Python):
from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)
dp = [[0]*(i+1) for i in range(N+1)]
for z in range(N):
    for y in range(z+1):
        dp[z+1][y] = max(A[z][0]*(A[z][1]-(z-y))+dp[z][y],dp[z+1][y])
        dp[z+1][y+1]= A[z][0]*((N-y-1)-A[z][1])+dp[z][y]
print(max(dp[-1]))

Solution (Python):
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    As = isRaw()
    Ais = [(a,i) for i,a in enumerate(As)]
    Ais.sort(reverse=True)
    dp = [[0]*(N+1) for n in range(N+1)]
    for sidx,ai in enumerate(Ais):
        a,i = ai
        sxy = sidx+1
        dp[0][sxy] = dp[0][sxy-1]+ a*(i-sidx)
        dp[sxy][0] = dp[sxy-1][0]+ a*(N-1-sidx -i)
        for x in range(1,sxy):
            c1 = dp[x-1][sxy-x]+ a*(N-x-i)
            c2 = dp[x][sxy-x-1]+ a*(i-(sidx-x))
            dp[x][sidx+1-x] = max(c1,c2)
    return max([dp[n][N-n] for n in range(N+1)])

if __name__ == "__main__":
    print(main())

Solution (Python):


import math
    
def abs(num):
    if num < 0:
        return -num
    else:
        return num

def abc163e(n, a):
    hap_dict = dict()
    hap_list = []
    for elem in range(n):
        if a[elem] in hap_dict:
            hap_dict[a[elem]].append(elem)
        else:
            tmp_list = [elem]
            hap_dict[a[elem]] = tmp_list
            hap_list.append(a[elem])
    
    hap_list.sort(reverse=True)

    left = 0
    right = n-1

    num = 0
    dp = [[0 for re in range(n+1)] for le in range(n+1)]
    for hap in hap_list:
        pos_list = hap_dict[hap]

        while len(pos_list) != 0:
            tgt = pos_list.pop()

            num += 1

            for left in range(num+1):
                right = num-left
                if left == num: 
                    dp[left][right] = dp[left-1][right] + hap * abs(tgt-left+1)
                elif left == 0: 
                    dp[left][right] = dp[left][right-1] + hap * abs(n-right-tgt)
                else:
                    left_dp = dp[left-1][right] + hap * abs(tgt-left+1)
                    right_dp = dp[left][right-1] + hap * abs(n-right-tgt)
                    dp[left][right] = max(left_dp, right_dp)
                

    ans_list = []
    for i in range(num+1):
        ans_list.append(dp[i][num-i])
    return max(ans_list)



if(__name__ == '__main__'):
    
    n = int(input())
    a = list(map(int, input().split(" ")))

    ans = abc163e(n, a)

    
    print(ans)

Solution (Python):
N = int(input())
A_list = map(int, input().split())
 

A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)
 

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

for left in range(0, N):
    for right in range(0, N - left):
        
        
        activity = A_list[left + right][0]
        distance_from_left = A_list[left + right][1] - left
        
        distance_from_right = (N - 1 - right) - A_list[left + right][1]
        
        dp[left + 1][right]\
            = max(dp[left + 1][right],
                  dp[left][right] + activity * distance_from_left)
        dp[left][right + 1]\
            = max(dp[left][right + 1],
                  dp[left][right] + activity * distance_from_right)
        
        
        

dp_list = [flatten for inner in dp for flatten in inner]
print(max(dp_list))

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

DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x
 
        
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))
 
ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)

Solution (Python):



N = int(input())
A = list(map(int,input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]= max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(int(max(dp[k][N-k] for k in range(N+1))))

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

d={}

for i,j in enumerate(A):
    d[i]=j

d=sorted(d.items(),key=lambda x:x[1],reverse=True)

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

c=0
for k,v in d:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

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

print(ans)

Solution (Python):
from sys import stdin


def get_result(data):
    N = data[0][0]
    A = data[1]
    dp = [[0]*(N+1) for _ in range(N+1)]
    B = [[A[i], i] for i in range(N)]
    B = sorted(B, reverse=True)
    for i in range(N):
        for j in range(N-i):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + B[i+j][0] * (B[i+j][1] - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + B[i+j][0] * ((N-1-j) - B[i+j][1]))

    res = 0
    for i in range(N):
        res = max(res, dp[i][N-i])
    return res


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

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


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


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

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

print(max(dp[-1]))

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

n = int(input())
a = list(map(int, input().split()))
a = [(item, i) for i,item in enumerate(a)]
s = sorted(a)[::-1] 
dp = [[None] * (n+1) for _ in range(n+1)] 

dp[0][0] = 0
tmp = 0

for i in range(n):
    val, ind = s[i]
    dp[i+1][0] = dp[i][0] + val * ((n-i-1) - ind)
for i in range(n):
    val, ind = s[i]
    dp[0][i+1] = dp[0][i] + val * (ind - i)

for i in range(2,n+1):
    for x in range(1,i):
        y = i - x
        val, ind = s[i-1]
        v1 = dp[x-1][y] + val * ((n-1 - (x-1)) - ind)
        v2 = dp[x][y-1] + val * (ind - (y-1))
        dp[x][y] = max(v1, v2)
print(max((dp[x][n-x] for x in range(n+1))))

Solution (Python):

import sys
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

AA=[]
for i,val in enumerate(A):
    AA.append((val,i+1))

AA.append((float("inf"),None))  
AA.sort(reverse=True)

dp=[ [ 0 for r in range(N+1) ] for l in range(N+1) ]
dp[0][0]=0

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

ans=float("-inf")
for l in dp:
    ans=max(ans,max(l))

print ans

Solution (Python):
n = int(input())
buf = list(map(int,input().split()))
a = []
for i in range(n):
    a.append([buf[i],i])
a = sorted(a,reverse=True)

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

print(max([max(i) for i in dp]))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
table = []

for i, a in enumerate(A):
    table.append([a,i])
table.sort()


DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x

        
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
table = []

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


DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    
    for x in range(i+1):
        y = i - x

        
        DP[x][y] = max((DP[x-1][y] + table[i-1][0] * abs(table[i-1][1]  - x+1)) * (x>0),\
                     (DP[x][y-1] + table[i-1][0] * abs(table[i-1][1] - (N - y))*(y>0)))


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

Solution (Python):
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [[a,i] for i,a in enumerate(LI())]
data.sort(reverse=True)

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

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

Solution (Python):
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [(a,i) for i,a in enumerate(LI())]
data.sort(reverse=True)

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

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

Solution (Python):
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [[a,i] for i,a in enumerate(LI())]
data.sort(reverse=True)

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

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

Solution (Python):
n = int(input())
al = list(map(int, input().split()))
l = 0
r = n-1

data = [[i, a] for i, a in enumerate(al)]
data.sort(key=lambda x: x[1], reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(0, i+1):
        p, a = data[i]
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + abs(n-1-j-p)*a)
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(i-j-p)*a)
print(max(dp[-1]))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a=list(zip(range(n),a))
a.sort(key=lambda x:x[1])
dp=[[0 for i in range(n+1)]for j in range(n+1)] 
ans=0
for k in range(n):
  i,ai=a.pop()
  dp[k+1][0]=dp[k][0]+ai*(i-k)
  dp[0][k+1]=dp[0][k]+ai*(n-k-1-i)
  for l in range(k):
    dp[k-l][l+1]=max(dp[k-l-1][l+1]+ai*(i-k+l+1),dp[k-l][l]+ai*(n-l-1-i))
for k in range(n+1):
  ans=max(ans,dp[k][n-k])

print(ans)

Solution (Python):

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

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

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
  x = b[i][0]
  y = b[i][1]
  for l in range(i+1):
    r = i-l
    dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l]+x*(y-l))
    dp[i+1][l] = max(dp[i+1][l],dp[i][l]+x*(n-1-r-y))

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

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

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

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

for x in range(N):
    for y in range(N-x):
        pos, infant = infants[x+y]
        dp[x][y+1] = max(dp[x][y+1], dp[x][y]+infant*abs(N-1-y-pos))
        dp[x+1][y] = max(dp[x+1][y], dp[x][y]+infant*abs(pos-x))

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

Solution (Python):
def slove(n, a_list):

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

    return max([max(i) for i in dp])

if __name__ == "__main__":
    n = int(input())
    k = sorted([(int(x),i) for i,x in enumerate(input().split())], reverse=True)
    print(slove(n, k))

Solution (Python):
def f(n, a_list):
    a_list = list(zip(range(n), a_list))
    a_list.sort(key=lambda x: x[1])
    
    
    dp = [0]
    
    for k in range(1, n + 1):
        dp_ = []
        i, a = a_list.pop()  
        dp_.append(dp[0] + a * (n - k - i))
        for x in range(1, k):
            dp_.append(max(dp[x - 1] + a * (i - x + 1),
                           dp[x] + a * (n - k + x - i)))
        dp_.append(dp[k - 1] + a * (i - k + 1))
        dp = dp_
    return max(dp)


if __name__ == '__main__':
    n = int(input())
    a_list = list(map(int, input().split()))
    print(f(n, a_list))

Solution (Python):
from sys import stdin, stdout
import math
import bisect
import datetime

n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().strip().split()))
arr.insert(0,0)
d={}
for i in range(len(arr)):
    d[i] = arr[i]
arr = sorted(d.items(), key=lambda a: a[1])

dp = [[0 for i in range(2005)] for j in range(2005)]

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

for l in range(2, n + 1):
    pos, val = arr[l]
    for left in range(1, n - l + 2):
        right = left + l - 1
        dp[left][right] = max(dp[left + 1][right] + val * abs(pos - left), dp[left][right - 1] + val * abs(pos - right))

stdout.writelines(str(dp[1][n]) + '\n')

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9 + 7

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

    B = []
    for i, a in enumerate(A):
        B.append((a, i + 1))
    B.sort()
    

    """
    活発度が大きい方から左右どちらかの端に移動させるが左右どちらになるかは一般に不明。
    しかし端から埋まるのは明らか（厳密な論証はmaspyさんの解説がわかりやすい）なので、
    ここから先をDPすればよい。具体的には
        dp[n][L] = (n人並べているとして左にL人いるときのうれしさの最大値)
    とすれば、これよりdp[n+1][L], dp[n+1][L+1]が更新できる。
    またn人の部分はdpとdp2間の遷移にしてメモリ削減。
    """

    dp = [0] * (N + 1)
    for n in range(1, N + 1):
        (a, i) = B.pop()
        dp2 = [0] * (N + 1)
        dp2[0] = dp[0] + a * abs((N - n + 1) - i)
        for l in range(1, n): 
            dp2[l] = max(dp[l - 1] + a * abs(i - l), dp[l] + a * abs((N - n + l + 1) - i))
        dp2[n] = dp[n - 1] + a * abs(n - i)
        dp = dp2
        
    print(max(dp))


if __name__ == "__main__":
    main()

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

babies = [(a, i) for i, a in enumerate(a)]
babies.sort(reverse=True)

dp = [[0 for _ in range(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, ind = babies[l+r]
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + activeness * abs(ind - l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + activeness * abs(ind - (n - 1 - r)))
print(ans)

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

A = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
dp = [[0]*(N+1) for _ in range(N+1)]

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

print(max(dp[N]))

Solution (Python):
N=int(input())
A=list(map(int, input().split()))
A=sorted([(a,p) for p, a in enumerate(A)])[::-1]

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

Solution (Python):
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 _ 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
        active, index = babies[l+r]
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] +
                         abs(index - (N - 1 - r))*active)
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(index - l)*active)

print(ans)

Solution (Python):
import sys 
try:
	sys.stdin = open('input.txt', 'r') 
	sys.stdout = open('output.txt', 'w')
except:
	pass

input = sys.stdin.readline

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

arr = list(enumerate(arr))
arr.sort(reverse = True, key = lambda x:(x[1]))
dp = [[0 for c in range(n+1)] for r in range(n+1)]
ans = 0
for r in range(n+1):
	st = r-1
	for c in range(n+1-r):
		if r==c==0:
			pass
		elif r-1<0:
			dp[r][c] = dp[r][c-1] + ( arr[st][1] * abs((arr[st][0]+1) - (n+1-c)) )

		elif c-1<0:
			dp[r][c] = dp[r-1][c] + ( arr[st][1] * abs((arr[st][0]+1) - r) )

		else:
			dp[r][c] = max( dp[r-1][c] + ( arr[st][1] * abs((arr[st][0]+1) - r) ), 
						dp[r][c-1] + ( arr[st][1] * abs((arr[st][0]+1) - (n+1-c)) )                           
						)
		ans = max(ans, dp[r][c])
		st += 1
print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
p = sorted([(x, i) for i, x in enumerate(a)], reverse=True)
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for s in range(1, n+1):
	for x in range(s+1):
		y = s-x
		if x > 0:
			dp[x][y] = max(dp[x][y], dp[x-1][y] + abs(p[s-1][1] - x + 1) * p[s-1][0])
		if y > 0:
			dp[x][y] = max(dp[x][y], dp[x][y-1] + abs(n-y - p[s-1][1]) * p[s-1][0])
print(max(dp[x][n-x] for x in range(n+1)))

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

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

p = []
for i in range(n):
    p.append((a[i], i))
p.sort(key=lambda x: -x[0])

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

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

print(ans)

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

A = [(a, i) for i, a in enumerate(A)]
A.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
        else:
            a, i = A[l+r]
            dp[l+1][r] = max(dp[l+r][r], dp[l][r] + a*abs(l-i))
            dp[l][r+1] = max(dp[l][r+1], dp[l][r] + a*abs((N-1-r)-i))

print(ans)

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

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)



N = int(input())

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

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







        
dp = np.zeros(1, dtype=int)
zero = np.zeros(1, dtype=int)
for act, i in B:
    prev = dp.copy()
    dp = np.append(dp,[0])
    l = len(prev)
        
    right = np.arange((N-1-i)*act,(N-1-i)*act - (act*(l)),-act)
    left = np.arange(i*act-(act*(l-1)),(i+1)*act,act)

    np.maximum(np.concatenate([prev + left, zero]),
               np.concatenate([zero, prev + right]),
               out = dp)


print(np.max(dp))

Solution (Python):
import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]

def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Solution (Python):
(N,) = map(int, input().split())
As = list(enumerate(map(int, input().split())))
As.sort(key=lambda x: -x[1])
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (pos, val) in enumerate(As):
    for j in range(i + 1):
        k = i - j
        dp[j + 1][k] = max(dp[j + 1][k], dp[j][k] + abs(j - pos) * val)
        dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + abs(N - 1 - k - pos) * val)
print(max(dp[i][N - i] for i in range(N + 1)))

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

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

s = 0
for i, A in sorted(enumerate(As), key = lambda t:t[1], reverse=True):
    s += 1
    for x in range(s+1):
        y = s - x
        if x > 0 and y > 0:
            dp[x][y] = max(dp[x-1][y] + A * (i - x + 1), dp[x][y-1] + A * ((N-y) - i))
        elif x == 0:
            dp[x][y] = dp[x][y-1] + A * ((N-y) - i)
        else:
            dp[x][y] = dp[x-1][y] + A * (i - x + 1)
ans = max((dp[x][N-x] for x in range(N+1)))

print(ans)

Solution (Python):
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield p+abs(j-i)*a, s+abs(j+r)*a
    p = s
  yield s+abs(len(prev)-i)*a,

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*map(max, solve(a,i, pd))]

print(max(pd))

Solution (Python):
N = int(input())

def left(a, i, prev):
  yield 0
  for l, s in enumerate(prev, 1-i):
    yield s+abs(l)*a
    
def right(a, i, prev):
  for r, s in enumerate(prev, N - len(prev) - i + 1):
    yield s+abs(r)*a
  yield 0

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*map(max, zip(left(a,i, pd), right(a,i, pd)))]

print(max(pd))

Solution (Python):
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print(max(pd))

Solution (Python):
def main():
    N, *A = map(int, open(0).read().split())

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

    dp = [[0] * r for r in reversed(range(1, N + 2))]
    for l in range(N):
        for r in range(N - l):
            p, a = A[l + r]

            dp[l + 1][r] = max(
                dp[l + 1][r],
                a * (p - l) + dp[l][r]
            )
            dp[l][r + 1] = max(
                dp[l][r + 1],
                a * (N - 1 - r - p) + dp[l][r]
            )

    print(max(dp[l][N - l] for l in range(N)))

main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(enumerate(iim()))

    A.sort(key=lambda x: (x[1], (2*x[0]-N)**2), reverse=True)

    dp = [0] * (N+1)
    dp0 = dp[:]
    for i, (j, ai) in enumerate(A):
        for k in range(i+1):
            dp[k] = max(dp[k], dp0[k] + abs(N-i+k-1-j) * ai)
            dp[k+1] = max(dp[k+1], dp0[k] + abs(k-j) * ai)
        dp, dp0 = dp0, dp

    print(max(dp0))

if __name__ == "__main__":
    resolve()

Solution (Python):

N = int(input())

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

def solve(a, i, prev):
  pl, pr, ps = i, 0, 0
  for l, r, s in prev:
    yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
for a,i in AI:
  prev = [*solve(a,i, prev)]

print(max(s for l, r, s in prev))

Solution (Python):
from operator import itemgetter as get
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)

def solve(a, i, prev, th, tha):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th-max(l,r)*tha:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB, SA)]
  pm = M
  SA -= a
  SB -= b

print(pm)

Solution (Python):
from operator import itemgetter as get
N = int(input())

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

def solve(a, i, prev, th):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB)]
  pm = M
  SB -= b

print(pm)