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):
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

n=int(input())
ar=lis()
data=[]
for i in range(n):
    data.append((ar[i],i))
data.sort(reverse=True)
dp = [[0] * (n+1) for _ in range(n+1)]

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

print(max(dp[-1]))

Solution (Python):
N = int(input())
A = sorted([(i, int(a)) for i, a in enumerate(input().split())], key=lambda x: x[1])[::-1]
dp = [[0] * (N+1) for _ in range(N+1)]  
cnt = 0
for k, a in A:
    for i in range(N):
        j = cnt - i
        if j < 0:
            continue
        
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a*max(0, k-i))
        
        dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * max(0, (N - 1) - j - k))
    cnt += 1
ans = 0
for i in range(N+1):
    ans = max(ans, dp[N-i][i])

print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = list((x,i) for i,x in enumerate(a))
b.sort(reverse=True)
dp = [[0]*(n+1-i) for i in range(n+1)]
for i in range(n):
    x,idx = b[i]
    for j in range(i+1):
        k = i-j
        if dp[j+1][k] < dp[j][k] + x*(idx-j):
            dp[j+1][k] = dp[j][k] + x*(idx-j)
        if dp[j][k+1] < dp[j][k] + x*((n-1-k)-idx):
            dp[j][k+1] = dp[j][k] + x*((n-1-k)-idx)
ans = 0
for i in range(n+1):
    if ans < dp[i][n-i]:
        ans = dp[i][n-i]
print(ans)

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

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

for i in range(1, n + 1):
    (j, a) = xs[i - 1]

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

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

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

dp = [0] * (N + 1)
for i in range(N):
    dp2 = dp[:]
    for l in range(i + 1):
        a, pos = A[i]
        
        dp2[l + 1] = max(dp2[l + 1], dp[l] + abs(pos - l) * a)
        
        r = i - l + 1
        dp2[l] = max(dp2[l], dp[l] + abs(N - r - pos) * a)
    dp = dp2
print(max(dp))

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

dp = [0] * (N + 1)
for i in range(N):
    dp2 = dp[:]
    for l in range(i + 1):
        a, pos = A[i]
        
        dp2[l + 1] = max(dp2[l + 1], dp[l] + (pos - l) * a)
        
        r = i - l + 1
        dp2[l] = max(dp2[l], dp[l] + (N - r - pos) * a)
    dp = dp2
print(max(dp))

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







A=[]
for i in range(n):
    A.append((a[i],i))
A.sort(key = lambda x:x[0], reverse=True)
dp = [[-float("inf")]*(n+1) for i in range(n+1)]
dp[0][0] = 0

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

print(max(dp[n]))

Solution (Python):
def main():
    n = int(input())
    tmp = list(map(int, input().split()))
    a = [[v, i] for i, v in enumerate(tmp)]
    a.sort(reverse=True)
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n):
        v, idx = a[i]
        for j in range(i+1):
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+v*abs(idx-j))
            dp[i+1][j] = max(dp[i+1][j] , dp[i][j]+v*abs(idx - (n-1-i+j)))
    print(max(dp[n]))

if __name__ == "__main__":
    main()

Solution (Python):
INF=float('inf')

N=int(input())
arr=list(map(int,input().split()))
A=[]
for i in range(N):
    A.append((arr[i],i))
A.sort(key=lambda x:x[0],reverse=True)
dp=[[-INF]*(N+1) for i in range(N+1)]
dp[0][0]=0

for i in range(N):
    a,w=A[i]
    for x in range(N+1):
        y=i-x+1
        if x>0:
            dp[i+1][x]=max(dp[i+1][x],dp[i][x-1]+a*abs(w-(x-1)))
        if y>=0:
            dp[i+1][x]=max(dp[i+1][x],dp[i][x]+a*abs(w-(N-y)))
print(max(dp[N]))

Solution (Python):
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(i)):
        dp[j+1] = max(dp[j] + a*(x-j), dp[j+1])
        dp[j] += a*(N-(i-j)-x)
print(max(dp))

Solution (Python):
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        res1 = dp[j-1]+a*(x-(j-1))*(j-1>=0)
        res2 = dp[j]+a*(N-(i-j)-x)*(j<=i-1)
        if res1>=res2: dp[j] = res1
        else: dp[j] = res2
print(max(dp))

Solution (Python):
def max2(x,y):
    return x if x > y else y
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max2((dp[j-1]+a*(x-(j-1)))*(j-1>=0), (dp[j]+a*(N-(i-j)-x))*(j<=i-1))
print(max(dp))

Solution (Python):
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max((dp[j-1]+a*(x-(j-1)))*(j-1>=0), (dp[j]+a*(N-(i-j)-x))*(j<=i-1))
print(max(dp))

Solution (Python):
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max((dp[j-1]+a*abs(x-(j-1)))*(j-1>=0), (dp[j]+a*abs(N-(i-j)-x))*(j<=i-1))
print(max(dp))

Solution (Python):
N = int(input())
A = [int(s) for s in input().split(" ")]
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr

print(max(prev))

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, A):
    
    A_order = np.argsort(-A)
    dp = np.zeros((N+2, N+2), dtype=np.int64)
    for n in range(1, N+1):
        idx_A = A_order[n-1]
        a = A[idx_A]
        for k in range(n+1):
            dp[n, k] = max(
                dp[n-1, k-1] + a * abs(idx_A-(k-1)) if k>0 else 0,  
                dp[n-1, k] + a * abs(idx_A-(N-n+k)) if k<n else 0,  
            )
    return dp[N].max()

numba_compile([
    [solve, "i8(i8,i8[:])"],
])

N = int(input())
A = np.array(input().split(), dtype=np.int64)
ans = solve(N, A)
print(ans)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
A_tup = [(0, 0)] * N
for i in range(N):
    A_tup[i] = (A[i], i)
A_tup.sort(reverse=True)

dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    pi = A_tup[i][1]
    for j in range(i + 1):
        k = i - j
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (pi - j) * A_tup[i][0])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (N - k - 1 - pi) * A_tup[i][0])

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

Solution (Python):

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    A = sorted([(a, i) for i, 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]))


if __name__ == "__main__":
    resolve()

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

p = list(range(N))
p.sort(key=lambda i: A[i], reverse=True)

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

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

p = list(range(N))
p.sort(key=lambda i: A[i], reverse=True)

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

Solution (Python):


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = read_ints()
    dp = [
        [0]*(N+1) for _ in range(N+1)
    ]
    AI = sorted(((a, i) for i, a in enumerate(A)), reverse=True)
    for i, (a, ix) in enumerate(AI):
        
        
        for x in range(i+2):
            y = i+1-x
            if y > 0:
                dp[x][y] = max(dp[x][y], dp[x][y-1]+a*abs(N-y-ix))
            if x > 0:
                dp[x][y] = max(dp[x][y], dp[x-1][y]+a*abs(ix-x+1))
    return max(dp[i][N-i] for i in range(N+1))

if __name__ == '__main__':
    print(solve())

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

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

dp = [0] * (n + 1)

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

print(dp[0])

Solution (Python):






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

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

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

    m = 0
    for i in range(1,len(A)+1):
        index,a = A[i-1]
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (N-j-index)*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (N-j-index)*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)
            if i == len(A):
                m = max(m, dp[i-j][j])

    
    
    print(m)

main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    
    
    B=sorted(zip(A,range(N)),reverse=True)
    
    
    dp=[[0]*(N+1) for _ in range(N+1)]
    
    for k in range(N):
        a=B[k][0]
        x=B[k][1]
        
        for i in range(k+1):
            j=k-i
            
            y=N-j-1
            dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a*abs(x-y))
            
            
            y=i
            dp[i+1][j]=max(dp[i+1][j], dp[i][j]+a*abs(x-y))
                
    ans=0
    for i in range(N+1):
        ans=max(ans,dp[i][N-i])
    print(ans)
        
    
    

        
        
        

main()

Solution (Python):


N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))



A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)



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


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a = [(num,i) for i,num in enumerate(a)]
a.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):
        if i>0:
            dp[i][j] = max(dp[i][j],dp[i-1][j]+a[i+j-1][0]*abs(a[i+j-1][1]-(i-1)))
        if j>0:
            dp[i][j] = max(dp[i][j],dp[i][j-1]+ a[i+j-1][0]*abs(a[i+j-1][1]-(n-j)))
ans = max(dp[i][n-i] for i in range(n+1))
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
a = [(num,i) for i,num in enumerate(a)]
a.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):
        if i>0:
            dp[i][j] = max(dp[i][j],dp[i-1][j]+a[i+j-1][0]*abs(a[i+j-1][1]-(i-1)))
        if j>0:
            dp[i][j] = max(dp[i][j],dp[i][j-1]+ a[i+j-1][0]*abs(a[i+j-1][1]-(n-j)))
ans = max(dp[i][n-i] for i in range(n+1))
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(num,i) for i,num in enumerate(a)]
a.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):
        if i>0:
            dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i+j-1][0]*abs(a[i+j-1][1]-(i-1)))
        if j>0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i+j-1][0]*abs(a[i+j-1][1]-(n-j)))
ans = max(dp[i][n-i] for i in range(n+1))
print(ans)

Solution (Python):
n = int(input())
a = sorted([(v, i) for i, v in enumerate(list(map(int, input().split())))])[::-1]

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

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

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

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



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

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

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

A = [(A[i], i) for i in range(N)]
A_sort = sorted(A,reverse = True)

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N):
    dp_new = [-float('inf')]*(N+1)
    pi = A_sort[i][1]  
    for l in range(i+1): 
        r = i - l   
        dp_new[l+1] = max(dp_new[l+1],dp[l] + A_sort[i][0] * (pi-l)) 
        dp_new[l] = max(dp_new[l],dp[l] + A_sort[i][0] * ((N-r-1)-pi))
    dp = dp_new
print(max(dp))

Solution (Python):
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

A = [(A[i], i) for i in range(N)]
A_sort = sorted(A,reverse = True)

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N):
    dp_new = [-float('inf')]*(N+1)
    pi = A_sort[i][1]  
    for l in range(i+1): 
        r = i - l   
        dp_new[l+1] = max(dp_new[l+1],dp[l] + A_sort[i][0] * (pi-l)) 
        dp_new[l] = max(dp_new[l],dp[l] + A_sort[i][0] * ((N-r-1)-pi))
    dp = dp_new
print(max(dp))

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

a_val_ind_l = []
for i, a in enumerate(al):
    a_val_ind_l.append((a,i))

a_val_ind_l.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]


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


ans = 0
for row in dp:
    row_max = max(row)
    ans = max(row_max, ans)

print(ans)

Solution (Python):

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

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


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [(A[i], i) for i in range(N)]
    B.sort(reverse = True)

    DP = [[-1 for j in range(N + 1)] for _ in range(N)] 
    DP[0][0] = B[0][0] * abs(B[0][1] - (N - 1))
    DP[0][1] = B[0][0] * B[0][1]

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

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=(a[i],i)
b=sorted(a,reverse=True)
dp=[[-10**14 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    see=b[i-1][0]
    prv=b[i-1][1]
    for j in range(i+1):
        dp[j][i-j]=max(dp[j-1][i-j]+abs(prv-(j-1))*see,dp[j][i-j-1]+abs(n-i+j-prv)*see)
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Solution (Python):
def main():
    from operator import itemgetter
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

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

    AP = []
    for i in range(N):
        AP.append((A[i], i))
    AP.sort(key=itemgetter(0), reverse=True)

    
    
    
    
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        ai, pi = AP[i]
        for l in range(i+1):
            r = i - l
            
            if dp[i+1][l+1] < dp[i][l] + (pi-l)*ai:
                dp[i+1][l+1] = dp[i][l] + (pi-l)*ai
            
            if dp[i+1][l] < dp[i][l] + ((N-r-1)-pi)*ai:
                dp[i+1][l] = dp[i][l] + ((N-r-1)-pi)*ai

    print(max(dp[N]))

main()

Solution (Python):

N = int(input())
A = list(map(int,input().split()))
dp = [[] for _ in range(N+1)]
dp[0].append(0)
for i in range(N):
    A[i] = [A[i],i+1]
A.sort(reverse=True)
for M in range(1,N+1):
    Ai,i = A[M-1]
    
    dp[M].append(dp[M-1][0]+Ai*(N-(M-1)-i))
    
    for x in range(1,M):
        dp[M].append(max(dp[M-1][x-1]+Ai*(i-x),dp[M-1][x]+Ai*(N-(M-x-1)-i)))
    
    dp[M].append(dp[M-1][M-1]+Ai*(i-M))
print(max(dp[N]))

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

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

for i in range(0,N):
  a, p = Ab[i]
  for j in range(0,i+1):
    r = i - j
    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-r-p-1))
                      
ans = 0
for i in range(N):
  ans = max(ans, dp[N][i])
  
print(ans)

Solution (Python):
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue

Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

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

Solution (Python):
import itertools


def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [(A[i], i) for i in range(N)]
    X.sort(reverse=True)
    l = 0
    r = N-1
    ans = 0
    dp = [[0] * (i+1) for i in range(N+1)]
    for i in range(N):
        cost, prev = X[i]
        dp[i+1][0] = dp[i][0] + cost * abs(prev - (N - 1 - i))
        dp[i+1][i+1] = dp[i][i] + cost * abs(prev - i)
        for j in range(1, i+1):
            pos1 = N - 1 - i + j
            pos2 = j - 1
            dp[i+1][j] = max(dp[i][j] + cost * abs(prev - pos1),
                             dp[i][j-1] + cost * abs(prev - pos2))
    print(max(dp[N]))


if __name__ == "__main__":
    main()

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

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

    A_index=[i for i in range(N)]

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

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

    print(res)

if __name__=="__main__":
    main()

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


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

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

for i in range(N):
    pi = p[i][1]

    for l in range(i + 1):
        
        dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + (pi - l) * A[pi])

        r = i - l
        
        dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + ((N - r - 1) - pi) * A[pi])

print(max(dp[N]))

Solution (Python):
import sys
import time

t = time.time()

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




cache = [[-1 for x in range(n)] for y in range(n)]



def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print(dfs(0, n-1))

Solution (Python):
import heapq
import time
st = time.time()
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))
dp = [[0 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*(n-1-hi)
dp[1][1] = -ai*hi
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(n-i-hi)
    dp[i][i] = dp[i-1][i-1] - ai*abs(hi-i+1)
    for j in range(1,i):
        dp[i][j] = max(dp[i-1][j-1]-ai*abs(hi-j+1),dp[i-1][j]-ai*abs(n-i+j-hi))

print(max(dp[n]))

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

L=[[10**10,0]]
for i in range(N):
    L.append([A[i],i])
L.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(i+1):
        if j==0:
            DP[i][j]=DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1))
            
        elif j==i:
            DP[i][j]=DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j))
            
        else:
            DP[i][j]=max(DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
            
print(max(DP[-1]))

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


V = [0]

for i in range(N-1):
    a, p = A[i]
    s = i+1
    V2 = [None]*(s+1)

    for t in range(s+1):
        v = 0

        if t > 0:
            v = V[t-1] + a*abs(p-(t-1))

        if t < s:
            v = max(V[t] + a*abs(p-(N-s+t)), v)

        V2[t] = v

    V = V2

a, p = A[-1]
for i in range(N):
    V[i] += a*abs(p-i)

print(max(V))

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]


def search(i, l):
    
    if i == N:
        return 0
    if dp[i][l] != -1:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print(search(0, 0))

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

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

    A = list(enumerate(A))
    A.sort(key=lambda x: x[1])
    ans = 0
    for z in range(1, N+1):
        tmp = A.pop()
        i = tmp[0]+1
        a = tmp[1]
        for x in range(z+1):
            y = z - x
            if x == 0:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y])
            elif y == 0:
                dp[x][y] = max(dp[x-1][y]+a*abs(i-x), dp[x][y])
            else:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y], dp[x-1][y]+a*abs(i-x))
            ans = max(ans, dp[x][y])
    print(ans)

if __name__ == "__main__":
    main()

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

    
    
    

    
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        a = sortedA[i][0]
        idx = sortedA[i][1]
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+a*abs((N-r-1)-idx))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+a*abs(l-idx))
    print(max(dp[N]))

main()

Solution (Python):
n=int(input())
a_=list(map(int,input().split()))
a=[[i+1,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[1][0]=a[0][1]*abs(a[0][0]-1)
dp[0][1]=a[0][1]*abs(a[0][0]-n)
for k in range(2,n+1):
    for i in range(k+1):
        j=k-i
        if j==0:
            dp[i][j]=dp[i-1][j]+a[i+j-1][1]*abs(a[i+j-1][0]-i)
        elif i==0:
            dp[i][j]=dp[i][j-1]+a[i+j-1][1]*abs(n-a[i+j-1][0]-j+1)
        else:
            dp[i][j]=max(dp[i-1][j]+a[i+j-1][1]*abs(a[i+j-1][0]-i),dp[i][j-1]+a[i+j-1][1]*abs(n-a[i+j-1][0]-j+1))
ans=0
for i in range(n+1):
    ans=max(dp[i][n-i],ans)
print(ans)

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
  ans = 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))
      if i+j == n:
        ans = max(ans, dp[i][j])
  print(ans)
if __name__ == "__main__":
  main()