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):


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
"""
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):
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(2000)


N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

A_mat = []
for i,A in enumerate(As):
    A_mat.append([A,i])

A_mat.sort(reverse=True)

map1 = []

for i in range(N+1):
    temp = [-1]*(N+1)
    map1.append(temp)



def DP(x, y): 
    if map1[x][y]>=0:
        return map1[x][y]
    
    if x+y == N:
        return 0

    a_val = A_mat[x+y][0]
    a_pos = A_mat[x+y][1]

    left_case = abs(a_pos-x)
    right_case = abs((N-y-1)-a_pos)

    map1[x][y] = max(DP(x+1,y)+left_case*a_val, DP(x,y+1)+right_case*a_val)

    return map1[x][y]

print(DP(0,0))

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

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

babies.sort(reverse=True)

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

ans=0

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

print(ans)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [(i, a[i]) for i in range(n)]
b = sorted(b, key=lambda x: x[1])[::-1]

dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0
for l in range(0, n+1):
    for r in range(0, n+1):
        if l + r == n:
            ans = max(ans, dp[l][r])
            break
        idx, activeness = b[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] + (n-1-r-idx) * activeness)

print(ans)

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

dp = [[0] * (N+1) for i in range(N+1)]
s, i = B[0]
dp[1][0] = s*(i - 1)
dp[0][1] = s*(N - i)
for n in range(2, N+1):
  a, i = B[n-1]
  for l in range(n+1):
    r = n - l
    if l == 0:
      dp[l][r] = dp[l][r-1] + abs(N-r+1 - i)*a
    elif r == 0:
      dp[l][r] = dp[l-1][r] + abs(l - i)*a
    else:
      dp[l][r] = max(dp[l-1][r]+abs(l-i)*a, dp[l][r-1]+abs(N-r+1-i)*a)

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

print(ans)

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

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


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


for i in range(1,N+1):
  aa,ii=a2list[i-1]
  for j1 in range(i+1):
    j2=i-j1
    if j1==0:
      dp[j1][j2]=dp[j1][j2-1]+aa*abs((N-1)-(j2-1)-ii)
    elif j2==0:
      dp[j1][j2]=dp[j1-1][j2]+aa*abs(ii-(j1-1))
    else:
      dp[j1][j2]=max(dp[j1][j2-1]+aa*abs((N-1)-(j2-1)-ii),dp[j1-1][j2]+aa*abs(ii-(j1-1)))


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

Solution (Python):
import itertools
n = int(input())
l = list(map(int,input().split()))
li = [i for i in range(n)]

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

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

ans = 0
for i in range(n+1):
    j = n-i
    ans = max(ans,dp[i][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],x[1]))

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

for i in range(N):
    for k in range(N):
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))
print(max(dp[-1]))

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],-x[1]))

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

for i in range(N):
    for k in range(N):
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))
print(max(dp[-1]))

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)]

for i in range(N):
    for k in range(N):
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))
print(max(dp[-1]))

Solution (Python):
import sys

sys.setrecursionlimit(1000000)


def solve(N, A):
    q = [(a, i) for i, a in enumerate(A)]
    q.sort(reverse=True)
    dp = [[-1 for _ in range(N + 1)] for __ in range(N + 1)]

    x = 0
    y = 0
    dp[x][y] = 0
    for a, i in q:
        dp[x+1][y] = dp[x][y] + a * abs(i - x)
        x += 1
    x = 0
    for a, i in q:
        dp[x][y+1] = dp[x][y] + a * abs(N - 1 - y - i)
        y += 1

    ans = 0
    for x in range(1, N+1):
        for y in range(1, N+1):
            if x + y > N:
                continue
            a, i = q[x+y-1]
            left = a * abs(i - (x - 1))
            right = a * abs(N - 1 - (y - 1) - i)
            dp[x][y] = max(dp[x-1][y] + left, dp[x][y-1] + right)
            ans = max(ans, dp[x][y])
    
    return ans

def slow_solve(N, A):
    import itertools
    ans = 0
    K = [i for i in range(N)]
    for p in itertools.permutations(K):
        tans = 0
        for i in range(N):
            tans += A[i] * abs(p[i] - i)
        ans = max(ans, tans)
    return ans







if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))

    print(solve(N, A))

Solution (Python):
def main():
    
    
    
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)
    
    dp = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for k in range(N):
        for i in range(k + 1):
            j = k - i
            here = dp[i][j]
            a, idx = A[k]
            dp[i + 1][j] = max(dp[i + 1][j], here + a * ((N - 1 - i) - idx))
            dp[i][j + 1] = max(dp[i][j + 1], here + a * (idx - j))
            

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for x in range(N):
        for y in range(N-x):
            i, d = A[x+y]
            dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
            dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

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

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
li = list(enumerate(a))
li.sort(key = lambda x:x[1])
li.reverse()

dp = [[0 for _ in range(n+1)]for __ in range(n+1)]
ans = 0
for i in range(n+1):
    for j in range(n+1):
        cnt = i + j
        if cnt == 0: continue
        if cnt > n: continue
        if i == 0:
            dp[0][j] = dp[0][j-1] + li[cnt-1][1] * ((n - j) - li[cnt-1][0])
            continue
        if j == 0:
            dp[i][0] = dp[i-1][0] + li[cnt-1][1] * (li[cnt-1][0] - (i-1) )
            continue
        
        
        res1 = dp[i][j-1] + li[cnt-1][1] * (n - j - li[cnt-1][0])
        res2 = dp[i-1][j] + li[cnt-1][1] * (li[cnt-1][0] - (i-1))
        dp[i][j] = max(res1,res2)
        if cnt ==n:
            ans = max(ans,dp[i][j])

print(ans)

Solution (Python):
def main():
    n=int(input())
    A=list(zip(list(map(int,input().split())),range(n)))
    A.sort(reverse=True)
    DP=[[0]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        for j in range(n+1):
            if i+j>n:
                break
            a,idx=A[i+j-1]
            if i>0:
                DP[i][j]=max(DP[i][j],DP[i-1][j]+a*abs(idx-(i-1)))
            if j>0:
                DP[i][j]=max(DP[i][j],DP[i][j-1]+a*abs(idx-(n-j)))
    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()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)



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 - (i - j) - 1) - p) * a)

print(max(dp[-1]))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    for i in range(n):
        val = max(a)
        idx = a.index(val)
        a[idx] = 0
        for j in range(i + 1):
            left = j
            right = i - j
            prev = dp[left][right]
            dp[left + 1][right] = max(dp[left + 1][right], prev + val * (idx - left))
            dp[left][right + 1] = max(dp[left][right + 1], prev + val * ((n - 1 - right) - idx))

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    
    n=II()
    aa=LI()
    dp=[[0]*(n+1) for _ in range(n+1)]
    
    for s,(i,a) in enumerate(sorted(enumerate(aa),key=lambda x:-x[1])):
        for l in range(s+1):
            r=s-l
            pre=dp[l][r]
            dp[l+1][r]=max(dp[l+1][r],pre+abs(l-i)*a)
            dp[l][r+1]=max(dp[l][r+1],pre+abs(n-1-r-i)*a)
    ans=0
    for l in range(n+1):
        ans=max(ans,dp[l][n-l])
    print(ans)

main()

Solution (Python):
import sys


input = sys.stdin.buffer.readline

N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)

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

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

print(ans)

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

N = int(input())
A = list(map(int, input().split()))
iA = [(i, A[i]) for i in range(N)]
iA.sort(key=lambda t: t[1], reverse=True)
dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    for j in range(N):
        if i+j<N:
            idx, v = iA[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]+(idx-i)*v)
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]+(N-1-j-idx)*v)
    
ans = 0

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

print(ans)

Solution (Python):
from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in dp.items():
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = max(dp.values())

print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
dp = [[-1]*N for _ in range(N)]

def rec(l, r):
	if l > r:
		return 0
	if dp[l][r] >= 0:
		return dp[l][r]
	idx = r-l  
	val, i = L[idx]
	dp[l][r] = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return dp[l][r]

print(rec(0, N-1))

Solution (Python):
n = int(input())
a = [(int(x), int(y)) for x, y in zip(input().split(), range(n))]
a.sort(reverse=True)

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

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

print(ans)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc163/tasks/abc163_e

dpか？
なにを基準にdpすればよい？
まとめられる状態は？
小さいことを考えると貪欲かなぁ
かいてみるか

挿入dp?
前から決めていけば、累積和で減る量がわかる
&増える寄与も計算できる
O(N**2)

全探索はむり

======答えを見ました======
今より右に行く、左に行くの集合に分けたとすると
大きい奴をより左にする方が最適
よって、途中まで単調減少、途中から単調増加が最適であるとわかる

dp[大きい方からi番目まで見た][左にl個つめた] = 最大値
で解ける

"""


N = int(input())

A = list(map(int,input().split()))
ai = []
for i in range(N):
    ai.append([A[i],i])
ai.sort()
ai.reverse()

ans = 0

dp = [ [float("-inf")] * (N+1) for i in range(N+1) ]
dp[0][0] = 0

for i in range(N):

    na,nind = ai[i]

    for l in range(i+1):

        r = N-1-(i-l)
        dp[i+1][l+1] = max(dp[i+1][l+1] , dp[i][l] + na*abs(nind-l) )
        dp[i+1][l]   = max(dp[i+1][l] , dp[i][l] + na*abs(nind-r) )

print (max(dp[N]))

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

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

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

for i in range(1,n+1):
    x,y = b[i-1]
    for j in range(i+1):
        left = dp[i-1][j-1] + x*abs(y-j+1) if j > 0 else -1
        right = dp[i-1][j] + x*abs(n-i+j-y) if j < i else -1
        dp[i][j] = max(left,right)

print(max(dp[-1]))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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

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

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

for j in range(1, N + 1):
    dp[0][j] = dp[0][j - 1] + D[j - 1][0] * abs(D[j - 1][1] - (N - j))

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

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i + j > N:
            continue
        dp[i][j] = max(dp[i][j - 1] + D[i + j - 1][0] * abs(D[i + j - 1][1] - (N - j)), dp[i - 1][j] + D[i + j - 1][0] * abs(D[i + j - 1][1] - (i - 1)))

res = 0

for i in range(N + 1):
    for j in range(N + 1):
        if i + j == N:
            res = max(res, dp[i][j])

print(res)

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i) for i in range(n)]
a.sort(key=lambda x: -x[0])
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for x in range(n+1):
    for y in range(n+1):
        if x + y > n:
            break
        active, idx = a[x+y-1]
        if x > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x-1][y] + active * abs(idx - (x-1)))

        if y > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x][y-1] + active * abs(idx - (n-y)))

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

print(ans)

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

N = int(input())
A = list(zip(list(map(int, input().split())), range(N)))
A.sort(reverse=True)
dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
    a, k = A[i-1]
    dp[i][0] = dp[i-1][0] + a * abs(N-i-k)
    for j in range(1, i):
        dp[i][j] = max(dp[i-1][j] + a * abs(N-(i-j)-k), dp[i-1][j-1] + a * abs(j-1-k))
    dp[i][i] = dp[i-1][i-1] + a * abs(i-1-k)
print(max(dp[N]))

Solution (Python):
n=int(input())
arr=list(map(int,input().split()))
arr=[[arr[i],i] for i in range(n)]
arr=sorted(arr,reverse=True,key=lambda x:x[0])
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(n):
    if dp[i][j]==-1:
      continue
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+arr[i][0]*abs(arr[i][1]-j))
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+arr[i][0]*abs(n-1-(i-j)-arr[i][1]))
print(max(dp[-1]))

Solution (Python):
import sys
sys.setrecursionlimit(5000)

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

memo = {}

def solve(i, l, r):
    if i==N: return 0

    key = l*N+r
    if key in memo: return memo[key]
    
    a, loc = A[i]
    score_l = a*abs(l-loc) + solve(i+1, l+1, r)
    score_r = a*abs(r-loc) + solve(i+1, l, r-1)
    retval = max(score_l, score_r)
    memo[key]=retval
    
    return retval
    
print(solve(0, 0, N-1))

Solution (Python):
n = int(input())
a = sorted([x, i] for i, x in enumerate(list(map(int, input().split()))))
f = [[0 for j in range(n)] for i in range(n)]
for i in range(n-1, -1, -1):
    f[i][i] = a[0][0]*abs(a[0][1]-i)
    for j in range(i+1, n):
        f[i][j] = max(f[i+1][j]+a[j-i][0]*abs(a[j-i][1]-i), f[i][j-1]+a[j-i][0]*abs(a[j-i][1]-j))
print(f[0][n-1])

Solution (Python):
from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        
        
        
        dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, n + n - 1 - i)), dp[i + 1, :-1])

    
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    


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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang, pos):
    lb_rang = 0
    ub_rang = len(rang) - 1
    lb_pos = 0
    ub_pos = len(pos) - 1
    ret= 0 
    while lb_rang <= ub_rang:
        if abs(rang[lb_rang]-pos[ub_pos]) < abs(rang[ub_rang]-pos[lb_pos]):
            ret += abs(rang[ub_rang]-pos[lb_pos])
            ub_rang -= 1
            lb_pos += 1
        else:
            ret += abs(rang[lb_rang]-pos[ub_pos]) 
            lb_rang += 1
            ub_pos -= 1
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    
                    
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))

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

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


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

for i in range(0,N-1):
    a,index=A[-1]
    dp[N-1][i]=a*abs(index-i)

for _ in range(1,N):
    i=N-1-_
    for j in range(0,i+1):
        left=j
        right=i-j
        a,index=A[i]
        ans=0
        if index>left-1:
            ans=max(ans,dp[i+1][j+1]+a*(index-left))

        if N-right>index:
            ans=max(ans,dp[i+1][j]+a*(N-right-1-index))

        dp[i][j]=ans

print(dp[0][0])

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)
now = [0]
for i in range(n):
  aj,j = b[i]
  last = now
  now = []
  for l in range(i+1):
    r = l+n-1-i
    now.append(last[l]+aj*abs(r-j))
    
  
  for l in range(i):
    now[l+1] = max(now[l+1],last[l]+aj*abs(l-j))
  now.append(last[-1]+aj*abs(i-j))
  
print(max(now))

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    dp = defaultdict(int)
    B = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
    for step, (i, a) in enumerate(B, 1):
        
        for left in range(step):
            right = N - step + left
            
            
            
            dp[(left+1, right)] = max(dp[(left+1, right)], dp[(left, right)] + abs(left-i)*a)
            dp[(left, right-1)] = max(dp[(left, right-1)], dp[(left, right)] + abs(right-i)*a)    
    return max(v for v in dp.values())



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    print(solve(N, A))

if __name__ == '__main__':
    main()

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

INF = 10 ** 16

dp = [-INF] * (n + 1)
dp[0] = 0

import heapq
q = []
for i in range(n):
    heapq.heappush(q, (-l[i], i))

for itera in range(n):
    _, ind = heapq.heappop(q)
    val = l[ind]
    dpnew = [-INF] * (n + 1)

    for i in range(n):
        left = dp[i] + abs(i - ind) * val
        right = dp[i] + abs(n - 1 - itera + i - ind) * val
        if dpnew[i] < right:
            dpnew[i] = right
        if dpnew[i+1] < left:
            dpnew[i+1] = left
    dp = dpnew
print(max(dp))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
b = b[::-1]

dp = [[0]* (n+1) for i in range(n+1)]
cnt = 0
for i,j in b:
    for k in range(cnt+1):
        dp[cnt-k][k+1] = max(dp[cnt-k][k] + abs(n-1-j-k)*i,dp[cnt-k][k+1])
        dp[cnt-k+1][k] = max(dp[cnt-k][k] + abs(j-(cnt-k))*i,dp[cnt-k+1][k])
    cnt+=1
ans = 0
for k in range(n):
    ans = max(ans,dp[n+1-k-1][k])
print(ans)

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

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

DP[0][0] = B[0][0] * B[0][1]
DP[0][1] = B[0][0] * (n-1-B[0][1])


for i in range(1, n):
    ind = B[i][1]
    for j in range(i+2):
        if j-1 >= 0:
            DP[i][j] = DP[i-1][j-1] + B[i][0] * abs(n-1-(j-1)-ind)
        
        DP[i][j] = max(DP[i][j], DP[i-1][j] + B[i][0] * abs(ind-(i-1+1-j)))

print(max(DP[-1]))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = list(range(n))
b.sort(key=lambda x: -a[x])

DP = [-float("inf")]*(n+1)

for i in range(n):
    if i == 0:
        DP[1] = a[b[i]]*b[i]
        DP[0] = a[b[i]]*(n-1-b[i])
    else:
        nxt = [-float("inf")]*(n+1)
        for j in range(i+2):
            if j == 0:
                nxt[j] = DP[j] + a[b[i]]*abs(n-1-i-b[i])
            else:
                nxt[j] = DP[j] + a[b[i]]*abs(n-1-(i-j)-b[i])
                nxt[j] = max(nxt[j], DP[j-1] + a[b[i]]*abs(j-1-b[i]))
        DP = nxt
print(max(DP))

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

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

dp = [[-1] * n for _ in range(n)]
for i2 in range(n-1, -1, -1):
    a, i = a2[i2]

    for s in range(i2+1):
        if i2 == n-1:
            dp[i2][s] = a * abs(s-i)
        else:
            dp[i2][s] = max(dp[i2+1][s+1] + a * abs(s - i),
                            dp[i2+1][s] + a * abs(n-1-i2+s - i))

print(dp[0][0])

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


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

for i, (aj, j) in enumerate(a2):
    for k in range(i + 1):
        
        dp[i + 1][k + 1] = max(dp[i][k] + aj * abs(k - j), dp[i + 1][k + 1])

        
        dp[i + 1][k] = max(dp[i][k] + aj * abs((n - i + k - 1) - j),
                           dp[i + 1][k])

ans = max(dp[n])
print(ans)

Solution (Python):
mod = 1000000007
eps = 10**-9
inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

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

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

    dp = [[-inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        a, x = AA[i]
        for j in range(N):
            if dp[i][j] != -inf:
                
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a * abs(x - j))
                
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * abs(x - (N-1 - (i - j))))
    
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



N = I()
A = LI()

Anew = []
for i in range(N):
    Anew.append((A[i],i))
Anew.sort(key=lambda x:(-x[0],x[1]))

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            continue
        if i+j > N:
            continue
        elif i == 0:
            dp[i][j] = dp[i][j-1] + abs(Anew[j-1][1]-(N-j))*Anew[j-1][0]
        elif j == 0:
            dp[i][j] = dp[i-1][j] + abs(Anew[i-1][1]-(i-1))*Anew[i-1][0]
        else:
            val1 = dp[i][j-1] + abs(Anew[i+j-1][1]-(N-j))*Anew[i+j-1][0]
            val2 = dp[i-1][j] + abs(Anew[i+j-1][1]-(i-1))*Anew[i+j-1][0]
            dp[i][j] = max(val1,val2)

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

print(ans)