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):
from collections import defaultdict



n = int(input())

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

d = {}
for i in range(n):
	d[i] = a[i]

dp = defaultdict(lambda: 0)

i = 0
x = 0
y = 0
maxr = 0
for k,v in sorted(d.items(), key=lambda x: -x[1]):
	i+=1

	for j in range(i+1):
		if j == 0:
			migi = 0
		else:
			migi = abs(n - j - k)*v
		
		if i - j == 0:
			hida = 0
		else:
			hida = abs(k - (i - j)+1)*v
		dp[(j,i-j)] = max(dp[(j-1,i-j)]+migi,dp[(j,i-j-1)]+hida)
		
		if i == n:
			maxr = max(maxr,dp[(j,i-j)])


print(maxr)

Solution (Python):






"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb: int) -> int:
    s_values = sorted(((v, i) for i, v in enumerate(values)), reverse=True)
    dp = [[0 for _ in range(nb + 1)] for _ in range(nb + 1)]
    for i, (v, p) in enumerate(s_values, start=1):
        for x in range(i + 1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x - 1][0] + abs(p - x + 1) * v
                continue
            if x == 0:
                dp[x][y] = dp[x][y - 1] + abs(nb - y - p) * v
                continue
            dp[x][y] = max(
                dp[x - 1][y] + abs(p - x + 1) * v, dp[x][y - 1] + abs(nb - y - p) * v
            )
    return max(dp[i][nb - i] for i in range(nb + 1))


def do_job():
    "Do the work"
    LOG.debug("Start working")
    
    N = int(input())
    values = list(map(int, input().split()))
    
    
    
    result = solve(values, N)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case 
    
    


def configure_log(log_file: Optional[str] = None) -> None:
    "Configure the log output"
    log_formatter = logging.Formatter(
        "%(asctime)s - %(filename)s:%(lineno)d - " "%(levelname)s - %(message)s"
    )
    if log_file:
        handler = logging.FileHandler(filename=log_file)
    else:
        handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None

if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            
            
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

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

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

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

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

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(v, i) for i, v in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i, (a, b) in enumerate(AA, start=1):
        for x in range(i+1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x-1][y] + abs(b - x+1) * a
            elif x == 0:
                dp[x][y] = dp[x][y-1] + abs(N-y-b) * a
            else:
                dp[x][y] = max(dp[x-1][y] + abs(b - x + 1) * a, dp[x][y-1] + abs(N-y-b) * a)
    r = 0
    for i in range(N+1):
        r = max(r, dp[i][N-i])
    return r
print(main())

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ans = 0
place = [0]*n
active = sorted(a,reverse=True)
for i in range(n):
    place[i] = a.index(active[i])
    a[a.index(active[i])] = -1


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

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



def check(mat):
    for i in range(len(mat)):
        print(mat[i])
    print("\n")


for i in range(n):
    for x in range(i+2):
        y = i+1 - x
        if x != 0 and y != 0:
            dp[x][y] = max(dp[x-1][y]+active[i]*abs(place[i]-x+1),dp[x][y-1]+active[i]*abs(n-y-place[i]))
            if i == n-1:
                ans = max(ans,dp[x][y])

print(ans)

Solution (Python):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(a, i) for i, a in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        a, t = AA[i]
        for x in range(i + 2):
            y = i + 1 - x
            dp[x][y] = max((dp[x - 1][y] + abs(t - (x - 1)) * a) if x > 0 else 0,
                           (dp[x][y - 1] + abs(t - (N - y)) * a) if y > 0 else 0)
    return max(dp[i][N - i] for i in range(N + 1))

print(main())

Solution (Python):

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted([(j, i) for i, j in enumerate(a)])[::-1]
    dp = [0]
    for i in range(n):
        dp2 = [0]*(i+2)
        A, p = a[i]
        for j in range(i+1):
            right = n-i-1+j
            dp2[j] = max(dp2[j], dp[j]+abs(p-right)*A)
            dp2[j+1] = max(dp2[j+1], dp[j]+abs(p-j)*A)
        dp = dp2
    print(max(dp2))


main()

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

infants = []
for i,a in enumerate(A):
    infants.append((a, i))
infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

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

Solution (Python):

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

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

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

Solution (Python):
from collections import defaultdict

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

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

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

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

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

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

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

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

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

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

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

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

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

Solution (Python):



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




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

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

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


if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left
N = int(input())
As = [(x, i) for i, x in enumerate(map(int, input().split()))]

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

for i, (u, idx) in enumerate(up[::-1], 1):
    for j in range(i):
        left = j
        right = N-(i-j)
        dp[i][j] = max(dp[i][j], dp[i-1][j]+u*abs(right-idx))
        dp[i][j+1] = max(dp[i][j+1], dp[i-1][j]+u*abs(left-idx))

print(max(dp[-1]))

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

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

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

Solution (Python):
"""
AtCoder Beginner Contest 163  E

・大きいものほど移動距離を増やしたいので、端にもっていく
を真っ先に思いつくので、大きいものから移動距離が大きくなるように配置すると、例２が答えと一致しない。
手を動かしてみると、
・大きいものから端にもっていく
は正しいそうだが、
・移動距離が最も大きくなるように
が当てはまらないことが見えてくる。

大きいものからi人目まで並べるときに、左側にx人配置されているなら、残りのi-x人が右側に配置されている。
・一人目は左右の端のいずれかに配置されうる
・二人目は、左端、その右隣、右端、その左隣、に配置されうる
・n人目は、左端からn番目まで、右端からn番目までの場所に配置されうる
このような感じで、左にx人、右にy人配置されている場合のうれしさの最大値を求めていって、最終的にx+y=Nになるようなdp[x][y]の最大値を求めるとよい


・大きいものから
・左右の端のどっちかに持っていく

のがいいっぽい


556111の例について、

大きい順から6を左右に振った場合
次に大きい5について、↑でできた2パターンかにおいて左右のどっちかに振った場合、
次に大きい5について、↑でできた4パターンかにおいて左右のどっちかに振った場合、
・・・

みたいな形でやるのがいいか？
2*2*2*2*... みたいな形で増えていかないか？
→NO。最初の6は左右の端のどちらか。次の5が左右から二つ分のいずれか。...。最後の1が左端〜右端で全ての場所に当てうるので、計算量的にはN**2ですむ
 N <= 2000 なので、十分間に合う

 ・例えば上の例で6について左右の端のいずれかにせず、全ての場所を試してもいいのでは？
 →恥に持っていくのが一番点が増えるので意味なし。のちの操作も煩雑になる＆分岐がややこしいのよろしくない。
"""



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

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



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

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

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


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

print(ans)

Solution (Python):


n = int(input())
tmp = [int(x) for x in input().split()]

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

aList.sort(reverse=True)

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


for i in range(n):
    
    for l in range(i+1):
        activity = aList[i][0]
        pos = aList[i][1]

        
        
        r = n-1-(i-l)

        
        dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l] + abs(l-pos) * activity)

        
        dp[i+1][l]   = max(dp[i+1][l],dp[i][l] + abs(r-pos) * activity)

print(max(dp[n]))

Solution (Python):


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

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



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

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

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


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

print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
infants = []
for i in range(n):
    infants.append((a[i],i))
infants.sort()
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    score,initial = infants.pop()
    for right in dp[i].keys():
        dp[i+1][right] = max(dp[i][right]+abs(initial-(i-right))*score,dp[i+1][right])
        dp[i+1][right+1] = max(dp[i][right]+abs((n-1-right)-initial)*score,dp[i+1][right+1])
print(max(dp[n].values()))

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

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

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

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

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

Solution (Python):
from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0, 0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1))
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print(dp[-1,].max())

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 9
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
A = LI()
S = sorted([(A[k], k + 1) for k in range(n)], reverse=True)
ans = 0
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(n):
        if i and i <= S[i + j - 1][1]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + S[i + j - 1][0] * abs(i - S[i + j - 1][1]))
        if j and S[i + j - 1][1] <= n - j + 1:
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + S[i + j - 1][0] * abs(n - j + 1 - S[i + j - 1][1]))
        if i + j == n:
            ans = max(ans, dp[i][j])
            break

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 9
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
A = LI()
S = sorted([(A[k], k + 1) for k in range(n)], reverse=True)
ans = 0
dp = [[-INF] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(n):
        if i and i <= S[i + j - 1][1]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + S[i + j - 1][0] * abs(i - S[i + j - 1][1]))
        if j and S[i + j - 1][1] <= n - j + 1:
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + S[i + j - 1][0] * abs(n - j + 1 - S[i + j - 1][1]))
        if i + j == n:
            ans = max(ans, dp[i][j])
            break

print(ans)

Solution (Python):
from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0][0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1)), dp[i + 1, 1:])
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print(dp[-1,].max())

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

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


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

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

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 =[] 

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


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


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


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


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


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

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

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

A =[] 

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


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

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

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


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


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

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

Solution (Python):

def get_all_int():
    return map(int, open(0).read().split())

n,*A = get_all_int()


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

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

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

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

ans = 0

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

print(ans)

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,*A = get_all_int()


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

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

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

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

ans = 0

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





















print(ans)

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

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

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

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

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

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

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

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

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

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

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

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

C = sorted(B, key=lambda b: b[1], reverse=True)

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

dp[1][0] = (C[0][0] - 0) * C[0][1]
dp[0][1] = ((N - 1) - C[0][0]) * C[0][1]

ans = 0
for i in range(2, N + 1):
    for j in range(0, i + 1):
        t1, t2 = 0, 0

        if j - 1 >= 0:
            t1 = dp[j - 1][i - j] + abs((C[i - 1][0] - (j - 1))) * C[i - 1][1]

        if i - j - 1 >= 0:
            t2 = dp[j][i - j - 1] + abs((C[i - 1][0] - (N - (i - j)))) * C[i - 1][1]

        dp[j][i - j] = max(t1, t2)

        if i == N:
            ans = max(ans, dp[j][i - j])

print(ans)

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

def student_sorting(N, A):
    student_list = [0] * N

    for initial_pos, activity in enumerate(A):
        student_list[initial_pos] = (activity, initial_pos)

    return sorted(student_list, reverse = True)

def DP(N, student_list):
    DP_map = list(list(0 for row in range(N + 1 - column)) for column in range(N + 1))
    ans_list = []
    ans = 0

    for left in range(N): 
        activity = student_list[left][0]
        distance_l = abs(left - student_list[left][1])
        DP_map[left + 1][0] = DP_map[left][0] + activity * distance_l

    for right in range(N): 
        activity = student_list[right][0]
        distance_r = abs((N - 1 - right) - student_list[right][1])
        DP_map[0][right + 1] = DP_map[0][right] + activity * distance_r

    for left in range(1, N + 1):
        for right in range(1, N - left + 1):
            activity = student_list[left + right - 1][0]
            distance_l = abs((left - 1) - student_list[left + right - 1][1])
            distance_r = abs((N - right) - student_list[left + right - 1][1])
            score_if_appended_to_left = DP_map[left - 1][right] + activity * distance_l
            score_if_appended_to_right = DP_map[left][right - 1] + activity * distance_r
            DP_map[left][right] = max(score_if_appended_to_left, score_if_appended_to_right)

    for left in range(N + 1):
        row = N - left
        column = left
        ans_list.append(DP_map[column][row])

    ans = max(ans_list)

    return ans

student_list = student_sorting(N, A)
ans = DP(N, student_list)
print(ans)

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

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

Solution (Python):
def main():
    from operator import itemgetter

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

    *ea, = enumerate(a, 1)

    ea.sort(key=itemgetter(1), reverse=True)

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

    for i, (p, x) in enumerate(ea, 1):
        for left in range(i + 1):
            right = i - left
            if left > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left - 1][right] + x * (p - left)
                )
            if right > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][right - 1] + x * (N - right + 1 - p)
                )

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


if __name__ == '__main__':
    main()