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
input = sys.stdin.buffer.readline

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [(a, i+1) for i, a in enumerate(A)]
  L.sort(reverse=True)
  dp = [[-1]*(n+1) for _ in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1-i):
      a, idx = L[i+j-1]
      if i:
        dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
      if j:
        dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
  ans = 0
  for i in range(n+1):
    ans = max(ans, dp[i][n-i])
  print(ans)
if __name__ == "__main__":
  main()

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

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

Solution (Python):
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    A_=[]
    for i in range(n):
        A_.append([A[i],i])
    A_sorted=sorted(A_)[::-1]
    dp=[[0]*(n+1) for _ in range(n+1)]
    ans=0
    for xy in range(1,n+1):
        for x in range(xy+1):
            m=-float("INF")
            a=A_sorted[xy-1][0]
            a_i=A_sorted[xy-1][1]
            if x!=0 and x<=a_i+1:
                m=max(m,dp[x-1][xy-x]+a*(a_i+1-x))
            if x!=xy and n-xy+x>=a_i:
                m=max(m,dp[x][xy-x-1]+a*(n-xy+x-a_i))
            dp[x][xy-x]=m
            if xy==n:
                ans=max(ans,m)
    print(ans)
if __name__ == '__main__':
    main()

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    

    
    

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

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
B = [i for i in range(1,N+1)]
C = zip(A, B)
C = sorted(C, reverse = True)
A, B = zip(*C)
dp = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for j in range(i + 2):
        if j == 0:
            dp[0][i-j+1] = dp[0][i-j] + A[i] * (N - (i - j) - B[i])
        elif j == i+1:
            dp[j][0] = dp[j-1][0] + A[i] * (B[i] - j)
        else:
            dp[j][i-j+1] = max(dp[j][i-j] + A[i] * (N - (i - j) - B[i]), dp[j-1][i-j+1] + A[i] * (B[i] - j))
ans = 0
for i in range(N+1):
    ans = max(ans, dp[i][N-i])
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math

import bisect


class Solver:

    def __init__(self, n, students):
        self.n = n
        self.students = students
        self.ordered = self.make_ordered() 
        self.dp = self.make_dp_container() 

    def make_ordered(self):
        ordered = [None] * self.n
        for i, active in enumerate(self.students):
            pos = i
            
            ordered[i] = (active, pos)
        ordered = sorted(ordered, key=lambda tpl: tpl[0])
        ordered = list(reversed(ordered))
        return ordered

    def make_dp_container(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [0] * (self.n + 1)
        return dp

    def run(self):
        for s, (active, pos) in enumerate(self.ordered):
            for l in range(s + 1):
                v = active * abs(pos - l)
                self.update(s + 1, l + 1, self.dp[s][l] + v)
                r = s - l
                r_key = self.n - 1 - r
                v = active * abs(pos - r_key)
                self.update(s + 1, l, self.dp[s][l] + v)
        
        
        ans = max(self.dp[-1])
        return ans

    def update(self, s, l, value):
        self.dp[s][l] = max(self.dp[s][l], value)


if __name__ == '__main__':
    n = int(input())
    students = list(map(int, input().split()))
    ans = Solver(n, students).run()
    
    print(ans)

Solution (Python):

N = int(input())
A = [int(x) for x in input().split()]


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

for i in range(0,N):

    
    a = max(A)
    id = A.index(a)
    
    for x in range(0,i+1):
        y = i - x

        d = dp[x][y]
        tmp = d + a * (id - x)
        if dp[x+1][y] < tmp:
        	dp[x+1][y] = tmp
        tmp = d + a * (((N-1)-y) - id)            
        if dp[x][y+1] < tmp:
        	dp[x][y+1] = tmp
        
    A[id] = 0

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

Solution (Python):
from sys import stdin


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

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

    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 - i):
            s1 = s2 = 0
            if i > 0:
                s1 = dp[i - 1][j] + a2[i + j - 1][0] * (a2[i + j - 1][1] - (i - 1))
            if j > 0:
                s2 = dp[i][j - 1] + a2[i + j - 1][0] * ((n - j) - a2[i + j - 1][1])
            dp[i][j] = max(s1, s2)
        ans = max(ans, dp[i][n - i])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin


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

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

    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 - i):
            s1 = s2 = 0
            if i > 0:
                s1 = dp[i - 1][j] + a2[i + j - 1][0] * (a2[i + j - 1][1] - (i - 1))
            if j > 0:
                s2 = dp[i][j - 1] + a2[i + j - 1][0] * ((n - j) - a2[i + j - 1][1])
            dp[i][j] = max(s1, s2)
        ans = max(ans, dp[i][n - i])

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)

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

n = int(input())
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append([v, i])
b.sort(reverse = True)
dp = [[0] * (n+1) for _ in range(n+1)]
ans = 0

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

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

print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=list(map(int,input().split()))
    B=[(A[i],i) for i in range(N)]
    B.sort(key=lambda t: -t[0])
    dp=[[0]*(N+1) for _ in range(N+1)]
    ans=0
    for i in range(N):
        for x in range(i+1):
            y=i-x
            dp[x+1][y]=max(dp[x+1][y],dp[x][y]+B[i][0]*abs(B[i][1]-x))
            dp[x][y+1]=max(dp[x][y+1],dp[x][y]+B[i][0]*abs(N-1-y-B[i][1]))
            ans=max(ans,dp[x+1][y],dp[x][y+1])
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

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

DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
for i in range(N):
    I = i+1
    b,ind = B[i]
    
    for j in range(I+1):
        if j == 0:
            DP[j][I-j] = DP[j][I-j-1] + b*abs(N-(I-j)-ind+1)
        elif I-j == 0:
            DP[j][I-j] = DP[j-1][I-j] + b*abs(ind-j)
        else:
            DP[j][I-j] = max(DP[j][I-j-1]+b*abs(N-(I-j)-ind+1),DP[j-1][I-j]+b*abs(ind-j))
        
        
ans = 0
for i in range(N+1):
    ans = max(ans,DP[i][N-i])
    

print(ans)

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
A = LI()

A = sorted([[a, i] for i, a in enumerate(A)], reverse=True, key=lambda x : x[0])

dp = [[0] * (N+1) for _ 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[i+j][0] * (A[i+j][1] - i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A[i+j][0] * ((N-j-1) - A[i+j][1]))

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

print(res)

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

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

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

ans = 0
for i in range(N+1):
    for j in range(N+1):
        if i+j>N:
            continue
        if i+j==0:
            continue
        a,k = A[-i-j]
        if i==0:
            dp[i][j] = dp[i][j-1]+a*(N-j-k)
        elif j==0:
            dp[i][j] = dp[i-1][j]+a*(k-i+1)
        else:
            dp[i][j] = max(dp[i-1][j]+a*(k-i+1),dp[i][j-1]+a*(N-j-k))
        ans = max(ans,dp[i][j])
print(ans)

Solution (Python):




def main():
  N = int(input())
  A = [(i, v) for i, v in enumerate(map(int, input().split()))]
  values = [[0] * (N + 1) for _ in range(N + 1)]

  A.sort(key=lambda x:-x[1])

  for i, (p, v) in enumerate(A):
    for j in range(i + 1):
      left = abs((p - j) * v)
      right = abs((N - 1 - (i - j) - p) * v)

      values[i + 1][j + 1] = max(values[i][j] + left, values[i + 1][j + 1])
      values[i + 1][j] = max(values[i][j] + right, values[i + 1][j])

  print(max(values[-1]))


if __name__ == '__main__':
  main()

Solution (Python):
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'e1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


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


def read_str():
    return input()

inf = 10 ** 9
inf = 10 ** 3

def solve():
    n = read_int()
    a = read_int_list()
    b = [(a[i], i) for i in range(n)]
    b.sort()
    best = [[-inf] * (n + 1) for i in range(n + 1)]
    best[0][0] = 0
    for s in range(1, n + 1):
        for x in range(s + 1):
            y = s - x
            ai, i = b[-s]
            if x > 0:
                c = best[x - 1][y] + (n - x) * ai - i * ai
                if c > best[x][y]:
                    best[x][y] = c
            if y > 0:
                c = best[x][y - 1] - (y - 1) * ai + i * ai
                if c > best[x][y]:
                    best[x][y] = c

    
    
    
    

    res = - inf
    for x in range(n):
        y = n - x
        if res < best[x][y]:
            res = best[x][y]
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1])

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    pos, val = a.pop()
    pos = pos + 1

    DP[0][i] = DP[0][i-1] + abs(val * (n - i + 1 - pos))
    DP[i][0] = DP[i-1][0] + abs(val * (pos - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(val * (pos - x)),  \
            DP[x][y-1] + abs(val * (n - y + 1 - pos)))

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()))
cost=[]
for i,g in enumerate(a):
    cost.append([g,i])
cost.sort(reverse=True)

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

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

print(max(dp[n]))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
cost=[]
for i,g in enumerate(a):
    cost.append([g,i])
cost.sort(reverse=True)

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

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

print(max(dp[-1]))

Solution (Python):

import sys
input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
B = []
for i, e in enumerate(A):
    B.append((e, i + 1))
B.sort(reverse=True)

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

for i in range(n):
    for j in range(i + 1):  
        k = i - j  
        ni = i + 1
        val, idx = B[i]
        dp[ni][j] = max(dp[ni][j], dp[i][j] + abs(n - k - idx) * val)
        dp[ni][j + 1] = max(dp[ni][j + 1], dp[i][j] + abs(idx - (j + 1)) * val)
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 = list(enumerate(a))
a.sort(key=lambda x: x[1])


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

for i in range(1, n+1): 
    ind, act = a.pop(-1)

    
    dp[i].append(dp[i-1][0] + act * (n - i - ind))

    
    for j in range(1, i): 
        ar = dp[i-1][j] + act * (n - i + j - ind) 
        al = dp[i-1][j-1] + act * (ind - j + 1) 
        dp[i].append(max([ar, al]))

    
    dp[i].append(dp[i-1][i-1] + act * (ind - i + 1))

print(max(dp[n]))

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

a = list(enumerate(a))
a.sort(key=lambda x: x[1])


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

for i in range(1, n+1): 
    ind, act = a.pop(-1)

    
    dp[i].append(dp[i-1][0] + act * (n - i - ind))

    
    for j in range(1, i): 
        ar = dp[i-1][j] + act * (n - i + j - ind) 
        al = dp[i-1][j-1] + act * (ind - j + 1) 
        dp[i].append(max([ar, al]))

    
    dp[i].append(dp[i-1][i-1] + act * (ind - i + 1))

print(max(dp[n]))

Solution (Python):

import sys


def solve(N: int, A: "List[int]"):
    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N):
        for j in range(0, N - i):
            idx, a = A[i + j]
            
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N - i]
        if tmp > result:
            result = tmp
    print(result)
    return



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)]  
    solve(N, A)


if __name__ == '__main__':
    main()

Solution (Python):
def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    
    

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

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

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

Solution (Python):
def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    
    

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

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

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

Solution (Python):
N = int(input())
A = sorted([(a, i) for i, a in enumerate(map(int, input().split()))], reverse=True)
dp = [[0]*(N+1) for _ in [0]*(N+1)]

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

print(max(dp[N]))

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

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

b.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
    act , i = b[l+r]
    dp[l+1][r] = max( dp[l+1][r] , dp[l][r] +act*abs(i-l))
    dp[l][r+1] = max( dp[l][r+1] , dp[l][r] +act*abs(n-i-1-r))
print(ans)

Solution (Python):



def main():

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

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    

    
    
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            
            j = k - i + 1
            
            

            
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

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


main()

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

Solution (Python):
from heapq import heappush, heappop

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

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))
    
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    x, pi = heappop(hq)
    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):
from heapq import heappush, heappop

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

f_inf = float('inf')
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    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):
from heapq import heappush, heappop

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

MX = 2005
f_inf = float('inf')
dp = [[0 for _ in range(MX)] for _ in range(MX)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    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())
S = list(map(int, input().split()))

data = [0]*N
for i, item in enumerate(S):
    data[i] = [item, i]
data.sort(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:
            break
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+data[i+j][0]*(data[i+j][1]-(i)))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j]+data[i+j][0]*((N-1-j)-data[i+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()))
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 math
import fractions
import collections
import itertools
import pprint
N=int(input())
A=list(map(int,input().split()))
que=[]
dp=[[0 for _ in range(N+1)] for _ in range(N+1)]    
for i in range(N):
    que.append([A[i],i])
que.sort(key=lambda x:x[0],reverse=True)


for i in range(0,N+1):
    if i!=0:
        for j in range(i+1):
            if j==0:
                dp[i-j][j]=dp[i-j-1][j]+(que[i-1][0]*abs((i-1)-que[i-1][1]))
            elif j==i:
                dp[i-j][j]=dp[i-j][j-1]+(que[i-1][0]*abs(N-j-que[i-1][1]))
            else:
                dp[i-j][j]=max(dp[i-j-1][j]+(que[i-1][0]*abs(((i-1)-j)-que[i-1][1])),dp[i-j][j-1]+(que[i-1][0]*abs(N-j-que[i-1][1])))
        
        
ma=0
for i in range(0,N+1):
    
    ma=max(ma,dp[N-i][i])
print(ma)


"""
st=[-1]*N
en=[-1]*N
s=[[0,[0,0]] for _ in range(N*N)]
for i in range(N):
    for j in range(N):
        s[i*N+j][0]=A[i]*abs(i-j)
        s[i*N+j][1][0]=i
        s[i*N+j][1][1] = j
s.sort(key=lambda x:x[0],reverse=True)
print(s)
cnt=0
for i in range(len(s)):
    a=s[i][1][0]
    b=s[i][1][1]
    c=s[i][0]
    if (st[a]==-1)and(en[b]==-1):
        cnt=cnt+c
        st[a]=0
        en[b]=0
print(cnt)
"""

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

ai = [int(i) for i in input().split()]

ai_li = []

for i in range(n):
    ai_li.append([ai[i],i+1])

ai_li.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 j in range(0,i+1):
        if i == 1:
            if j == 1:
                dp[i][j] = ai_li[i-1][0]*abs(ai_li[i-1][1]-1)
            else:
                dp[i][j] = ai_li[i-1][0]*abs(n-ai_li[i-1][1])
        else:
            if j == 0:
                
                dp[i][j] = dp[i-1][0] + ai_li[i-1][0]*abs(n-ai_li[i-1][1]-i+1)
            else:
                
                
                dp[i][j] = max(dp[i-1][j-1]+ai_li[i-1][0]*abs(ai_li[i-1][1]-j),dp[i-1][j]+ai_li[i-1][0]*abs(n-ai_li[i-1][1]-(i-1-j)))
                


print(max(dp[n]))

Solution (Python):



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

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

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






dp[0][0] = 0

for x in range(1,N+1):
    dp[x][0] = dp[x-1][0]+A[x-1][0]*(A[x-1][1]-x+1)
    

for y in range(1,N+1):
    dp[0][y] = dp[0][y-1]+A[y-1][0]*(N-y - A[y-1][1])
    


for x in range(1,N):
    for y in range(1,N+1-x):
        A0 = A[x+y-1][0]
        A1 = A[x+y-1][1]
        dp[x][y] = max(dp[x-1][y] + A0*(A1+1 - x), dp[x][y-1] + A0*(N-y - A1))




c = 0
for i in range(N):
    if c < dp[i][N-i]:
        c = dp[i][N-i]
print(c)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 9)

input()

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))

d = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]


def dp(l, r, idx):
    if idx == len(arr):
        return 0

    if d[l][r] != -1:
        return d[l][r]

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    d[l][r] = max(left, right)
    return max(left, right)


print(dp(0, len(arr) - 1, 0))

Solution (Python):
N = int(input())
A = enumerate(map(int,input().split()))
A = sorted(A,reverse=True,key=lambda x:x[1])

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

for i in range(1,N+1):
    b,a = A[i-1]
    b += 1
    for j in range(i+1):
        c = 0
        if i >= 1 and j >= 1:
            dst = j
            c = max(c,DP[i-1][j-1]+a*abs(b-dst))
        if i != j:
            dst = N - (i - j) + 1
            c = max(c,DP[i-1][j]+a*abs(b-dst))
        DP[i][j] = c

print(max(DP[N]))

Solution (Python):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = [(int(v), i) for i, v in enumerate(input().split())]
    a.sort(reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = a[0][0] * (n - 1 - a[0][1])
    dp[0][1] = a[0][0] * a[0][1]
    for i, v in enumerate(a[1:]):
        dp[i+1][0] = dp[i][0] + v[0] * abs(n - 1 - (i + 1) - v[1])
        dp[i+1][i+2] = dp[i][i+1] + v[0] * abs(v[1] - (i + 1))
        for j in range(1, i + 2):
            dp[i+1][j] = max(
                dp[i][j] + v[0] * abs(n - 1 - (i + 1) + j - v[1]),
                dp[i][j-1] + v[0] * abs(v[1] - (j - 1)))
    ans = -float('inf')
    for i in dp[n-1]:
        ans = max(ans, i)
    print(ans)


main()

Solution (Python):
N, = map(int, input().split())
X = [(i+1, x) for i, x in enumerate(map(int, input().split()))]
dp = [[0]*(N+1) for _ in range(N+1)]
X = sorted(X, key=lambda x:x[1])[::-1]
for i in range(1, N+1):
    ai, a = X[i-1]
    dp[i][0] = dp[i-1][0]+a*abs(ai-(N-i+1))
    for j in range(1, i):
        dp[i][j] = max(dp[i-1][j-1]+a*abs(ai-j), dp[i-1][j]+a*abs(ai-(N-(i-j)+1)))
    dp[i][i] = dp[i-1][i-1]+a*abs(ai-i)
print(max(dp[-1]))

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

data = [(ai,i) for i,ai in enumerate(A)]
data.sort(reverse = True)

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

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

Solution (Python):

import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

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

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

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