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.readline

n = int(input())
a = [int(item) for item in input().split()]
aind = []
for i, item in enumerate(a):
    aind.append((item, i))
aind.sort(reverse=True)


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

for i, (item, index) in enumerate(aind): 
    for j in range(n):
        if dp[i][j] == -1:
            continue
        
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + abs(index - j) * item)
        
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(index - (n - 1 - i + j)) * item)

print(max(dp[-1]))

Solution (Python):
from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = [[-1]*N for _ in range(N)]
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    if DP[i][l] != -1: return DP[i][l]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[i][l] = max(v1, v2)
    return DP[i][l]

print(opt(0, 0))

Solution (Python):
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        return self._sum(r) - self._sum(l)


n = int(input())
a = list(map(int, input().split()))
bit = BIT(n)
for i in range(n):
    bit.add(i, a[i])

a = [[a[i], i] for i in range(n)]
a = sorted(a, reverse=True)
INF = 10 ** 18

l = 0
r = n - 1
dp = [[-INF] * (n + 1) for i in range(n + 1)]
dp[0][0] = 0
for ind in range(n):
    val, i = a[ind]
    
    for j in range(n):
        dp[ind + 1][j + 1] = max(dp[ind][j] + abs(i - j) * val, dp[ind + 1][j + 1])
    
    for j in range(n):
        r_cnt = ind - j
        dp[ind + 1][j] = max(dp[ind][j] + abs(n - i - r_cnt - 1) * val, dp[ind + 1][j])

print(max(dp[-1]))

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

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

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

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

    dp = dp2

ans = 0
for k, v in dp.items():
    ans = max(ans, v)

print(ans)

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

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    a,j = B.pop()
    for k in range(i+1):
        dp[k][i-k+1] = max(dp[k][i-k+1], dp[k][i-k] + a * abs(j-(N-1-(i-k))))
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a * abs(j-k))

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

Solution (Python):
import bisect
import collections
import heapq
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()

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

heap = []

for a, i in AI:
    heapq.heappush(heap, (-a, i))  

right = 0
left_ = 0
last = [0]  
for i in range(N):
    new = [0] * (i + 2)
    _a, index = heapq.heappop(heap)
    a = -_a

    
    for l in range(i + 1):
        r = N - 1 - (i - l)
        new[l + 1] = max(new[l + 1], last[l] + abs(index - l) * a)
        new[l] = max(new[l], last[l] + abs(r - index) * a)
    last = new

print(max(last))

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
ai = [(val, ind) for ind,val in enumerate(a)]
ai.sort(reverse=True)

dp = [[0] * (n+1) for _  in  range(n+1)]
for i,tmp in enumerate(ai,1):
    val , val_i = tmp
    for right in range(i+1):
        left = i-right
        if(left==0):
            dp[left][right] = dp[left][right-1] + val * abs((n-right)  - val_i)
        elif(right==0):
            dp[left][right] = dp[left-1][right] + val * abs((val_i - (left-1)))
        else:
            dp[left][right] = max(dp[left][right-1] + val * abs((n-right)  - val_i),
                                    dp[left-1][right] + val * abs((val_i - (left-1))))


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

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

    def max2(x, y): return x if x >= y else y

    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]

    As.sort(reverse=True)

    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))

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

    print(ans)


solve()

Solution (Python):
def examA():
    R = I()
    ans = R*2*3.141592
    print(ans)
    return

def examB():
    N, M = LI()
    A = LI()
    S = sum(A)
    if N>=S:
        ans = N-S
    else:
        ans = -1
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    ans = [0]*N
    for i in range(N-2,-1,-1):
        ans[A[i]-1] +=1
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    S = [0]*(N+2)
    for i in range(1,N+1):
        S[i+1] = S[i] + i
    
    ans = 0
    for i in range(K,N+2):
        cur = (S[N+1] - S[N-i+1]) - (S[i] - S[0]) +1
        ans += cur
        ans %= mod
        

    print(ans)
    return

def examE():
    N = I()
    A = LI()
    S = [[]for _ in range(N)]
    for i in range(N):
        S[i] = [A[i],i]
    S.sort(reverse=True)
    
    dp = [[0]*(N+1)for _ in range(N+1)]
    for i in range(N):
        s, x = S[i]
        for j in range(i+1):
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + s*(x-j))
            dp[i+1][j] = max(dp[i+1][j],dp[i][j] + s*(N-i-x+j-1))
            
    ans = max(dp[-1])
    print(ans)
    
    return

def examF():
    N = I()
    C = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    ans = 0

    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sa = [(a[i], i) for i in range(N)]
sa.sort(key = lambda x: (-x[0], -abs(x[1] - (N - 1) / 2)))
dp = [[0] * (N + 1) for _ in range(N + 1)]
for k in range(N):
  x, i = sa[k]
  for l in range(k + 1):
    r = k - l
    nr = N - 1 - r
    dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(l - i) * x)
    dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + abs(nr - i) * x)
res = 0
for l in range(N):
  r = N - l
  res = max(res, dp[l][r])
print(res)

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

    def max2(x, y): return x if x >= y else y

    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]

    As.sort(reverse=True)

    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))

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

    print(ans)


solve()

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

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

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

for l, (a, i) in enumerate(B):
    length = N-l
    for left in range(l+1):
        dp[left+1][left+length] = max(dp[left+1][left+length], dp[left][left+length] + a*abs(i-left))
        dp[left][left+length-1] = max(dp[left][left+length-1], dp[left][left+length] + a*abs(left+length-1-i))
ans = 0    
for n in range(N+1):
    ans = max(ans, dp[n][n])
print(ans)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
b = [(a[i],i+1) for i in range(n)]
b.sort(reverse=True)
cntf = 0
cntb = n-1
dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][1] = -10**18
for i in range(1,n+1):
  x,ind = b[i-1]
  dp[i][0] = dp[i-1][0]+abs(n-i-ind+1)*x
  for j in range(1,i+1):
    dp[i][j] = max(dp[i-1][j-1]+abs(j-ind)*x,dp[i-1][j]+abs(n-(i-j)+1-ind)*x)
print(max(dp[n]))

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

mod = 1000000007
INF = 110110110

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

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

for i in range(N+1):
    for j in range(N+1):
        dp[i][j] = -INF * INF

dp[0][0] = 0

for i in range(N):
    for j in range(N):
        if i+j >= N:
            continue
        w = PA[i+j][0]
        at = PA[i+j][1]
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + w * abs(at - i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + w * abs(at - (N-1-j)))
ans = 0
for i in range(N+1):
    for j in range(N+1):
        ans = max(ans, dp[i][j]);
print(ans)

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

al_id = [(a, idx) for idx, a in enumerate(al)]
al_id = sorted(al_id, reverse=True)
dp = [[-float("inf") for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
for count, (a, idx) in enumerate(al_id):
    for i in range(count+1):
        j = count - i
        dp[i+1][j] = max(dp[i][j] + abs(idx-i) * a, dp[i+1][j])
        dp[i][j+1] = max(dp[i][j] + abs(n-j-idx-1) * a, dp[i][j+1])


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

print(ans)

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

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

cnt = [0,n-1]

As = sorted(list(zip(A,range(n))), reverse = True)

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


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

print(max(dp[n]))

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

ap = [(v, k) for k, v in enumerate(A)]
ap.sort(reverse=True)

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

for i, (a, p) in enumerate(ap) :
  for l in range(i + 1) :
    r = i - l
    if l + 1 <= N :
      dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a * (p - l))
    if r + 1 <= N :
      dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a * (N - 1 - r - p))
  
print(max(dp[i][N - i] for i in range(N + 1)))

Solution (Python):
import sys

stdin = sys.stdin
sys.setrecursionlimit(10**6)
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
lis = [(e, i) for i, e in enumerate(a)]
lis.sort()
dp = [[-1]*n for _ in range(n)]

def solve(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    idx = r - l
    e, i = lis[idx]
    dp[l][r] = max(abs(i-l)*e + solve(l+1, r), abs(r-i)*e + solve(l, r-1))
    return dp[l][r]

print(solve(0, n-1))

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

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

babies.sort(reverse=True)

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

ans = 0

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

print(ans)

Solution (Python):
N = int(input())
A = sorted([(int(a), i) for i, a in enumerate(input().split())], key = lambda x: x[0])[::-1]
X = [0] + [-1<<100] * (N + 1)
for k, (a, i) in enumerate(A):
    nX = [0] * (N + 2)
    for j in range(k + 1):
        nX[j] = max(nX[j], X[j] + abs(N - (k - j) - 1 - i) * a)
        nX[j+1] = max(nX[j+1], X[j] + abs(j - i) * a)
    X = nX
print(max(X))

Solution (Python):
import os
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))

order = argsort(A)[::-1]
dp = [defaultdict(int) for _ in range(N + 1)]
l = 0
r = N - 1
dp[0][l, r] = 0
for i, p in enumerate(order):
    for (l, r), v in dp[i].items():
        dp[i + 1][l + 1, r] = max(dp[i + 1][l + 1, r], v + A[p] * abs(p - l))
        dp[i + 1][l, r - 1] = max(dp[i + 1][l, r - 1], v + A[p] * abs(p - r))
print(max(dp[-1].values()))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

N = int(readline())
A = np.array(read().split(), np.int64)
I = np.argsort(A)[::-1].tolist()
A = A[I].tolist()

dp = np.zeros(1, np.int64)

for n, (i, x) in enumerate(zip(I, A)):
    newdp = np.zeros(len(dp) + 1, np.int64)
    left_ind = np.arange(len(dp))
    right_ind = N - 1 - n + left_ind
    left_cost = x * np.abs(left_ind - i)
    right_cost = x * np.abs(right_ind - i)
    np.maximum(newdp[:-1], dp + right_cost, out=newdp[:-1])
    np.maximum(newdp[1:], dp + left_cost, out=newdp[1:])
    dp = newdp

print(dp.max())