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 main():
    N, *A = map(int, open(0).read().split())

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

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for l in range(N):
        for r in range(N - l):
            p, a = A[l + r]

            dp[l + 1][r] = max(
                dp[l + 1][r],
                a * (p - l) + dp[l][r]
            )
            dp[l][r + 1] = max(
                dp[l][r + 1],
                a * (N - 1 - r - p) + dp[l][r]
            )

    print(max(dp[l][N - l] for l in range(N)))

main()

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

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

ans = 0

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

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

Solution (Python):
n,*a=map(int,open(0).read().split())
a=sorted([(j,i) for i,j in enumerate(a)])[::-1]
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for m,(a_k,k) in enumerate(a):
  for i in range(m+1):
    j=m-i
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a_k*abs(k-i))
    dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a_k*abs(k-((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 deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter


from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())

ls = []
for i in range(n):
    ls.append([ i,a[i] ])
ls = mysort(ls,1,True)


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


for i in range(n):
    f = ls[i][0]
    A = ls[i][1]
    for l in range(i+1):
        
        
        
        t = n - i + l - 1
        
        s = A*abs(t-f)
        
        dp1 = dp[i][l] + s
        
        if dp1 > dp[i+1][l]:
            dp[i+1][l] = dp1
        
        
        
        t = l
        
        s = A*abs(t-f)
        
        dp2 = dp[i][l] + s
        
        
        if dp2 > dp[i+1][l+1]:
            dp[i+1][l+1] = dp2


print(max(dp[n]))

Solution (Python):
N = int(input())
A = [int(v) for v in input().split()]
P = sorted([(v, i) for i, v in enumerate(A)], key=lambda x: x[0], reverse=True)
dp = [[0 for j in range(2005)] for i in range(2005)]

for i in range(N):
    pi = P[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] + (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):
def main():
    N, *A = map(int, open(0).read().split())

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

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

    print(max(dp[N]))

main()

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

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

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

print(max(dp[N]))

Solution (Python):
n,*a=map(int,open(0).read().split()) 
MX=2005
dp=[0]*(MX*10000+MX+100)
p=sorted([(a[i]*MX+i) for i in range(n)])[::-1]
for i in range(n):
    ai,pi=divmod(p[i],MX)
    for l in range(n):
        r=i-l
        if not 0<=r<=n:
            break
        dp[(i+1)*10000+(l+1)]=max(dp[(i+1)*10000+(l+1)],dp[(i)*10000+(l)]+ai*(pi-l))
        dp[(i+1)*10000+(l+0)]=max(dp[(i+1)*10000+(l+0)],dp[(i)*10000+(l)]+ai*(n-r-1-pi))
        
ans=0
for i in range(n+1):
    ans=max(ans,dp[n*10000+i])
print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split())
def dp_table(MXi,MXj):
    return [[0]*MXi for _ in range(MXj)] 
MX=2005
dp=dp_table(MX,MX)
p=sorted([(a[i]*MX+i) for i in range(n)])[::-1]

for i in range(n):
    ai,pi=divmod(p[i],MX)
    for l in range(n):
        r=i-l
        if not 0<=r<=n:
            break
        dp[i+1][l+1]=max(dp[i+1][l+1],dp[i][l]+ai*(pi-l))
        dp[i+1][l+0]=max(dp[i+1][l+0],dp[i][l]+ai*((n-r-1)-pi)) 

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()))
ai = [[a_, i] for i, a_ in enumerate(a)]
ai.sort(reverse=True)


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

Solution (Python):
N = int(input())
A = list(map(int,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] + a*abs(N-i-(k-l)))
        curr[l+1] = prev[l]+a*abs(i-l-1)
    prev = curr
print (max(prev))

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ch=[]
for i in range(n):
    ch.append((a[i],i))
ch.sort(reverse=True)

dp=[[0]*(n+1) for _ in range(n+1)]
dp[1][1]=ch[0][0]*ch[0][1]
dp[1][0]=ch[0][0]*(n-1-ch[0][1])
for i in range(2,n+1):
    for j in range(i+1):
        if j>=1:
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+ch[i-1][0]*abs(ch[i-1][1]-j+1))
        if i-1>=j:
            dp[i][j]=max(dp[i][j],dp[i-1][j]+ch[i-1][0]*abs(n-i+j-ch[i-1][1]))
print(max(dp[n]))

Solution (Python):

import sys

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

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

B.sort(reverse = True)

def score(org_idx, sorted_idx):
    s,idx = B[org_idx]
    return s*abs(idx-sorted_idx)

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


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

Solution (Python):
from sys import stdin


def chmin(a,b):
    if a > b: return b
    else: return a


def chmax(a,b):
    if a < b: return b
    else: return a


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N = int(_in[0])  
    A_arr = list(map(int,_in[1].split(' ')))  
    
    A_arr_wloc = []
    for i,A in enumerate(A_arr):
        A_arr_wloc.append([A,i])
    A_arr_wloc.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N-i):
            dp[i+1][j] = chmax(dp[i+1][j], dp[i][j]+A_arr_wloc[i+j][0]*(A_arr_wloc[i+j][1]-i)) 
            dp[i][j+1] = chmax(dp[i][j+1], dp[i][j]+A_arr_wloc[i+j][0]*((N-1-j)-A_arr_wloc[i+j][1])) 
    cnt = 0
    for i in range(0,N+1):
        cnt = chmax(cnt, dp[i][N-i])
    
    print(cnt)

Solution (Python):


n=int(input())
*a,=map(int, input().split( ))
dp = [0]

aii = [(ai,i) for i,ai in enumerate(a)]
aii.sort(key= lambda x:-x[0])
for j,(ai,i) in enumerate(aii):
    dp2 = [0]*(j+2)
    dp2[0]=dp[0]+ai*abs(n-j-1-i)
    dp2[-1]=dp[-1]+ai*abs(j-i)
    for k in range(j):
        dp2[k+1] = max(dp[k]+ai*abs(k-i), dp[k+1]+ai*abs((n-(j-k-1)-1)-i))
    dp = dp2

print(max(dp))

Solution (Python):
n = int(input())
a = [(int(x), i+1) for i, x in enumerate(input().split())]

a = sorted(a, reverse=True)

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

for k in range(1, n+1):
    child = a[k-1][0]
    ind = a[k-1][1]
    for i in range(k+1):
        if i != 0:
            dp[i][k-i] = dp[i-1][k-i] + child*(ind-i)
        if k-i != 0:
            dp[i][k-i] = max(dp[i][k-i], dp[i][k-i-1] + child*((n+1-(k-i))-ind))

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()))
INF=10**9
dp=[[-INF for i in range(N+1)] for j in range(N+1)]
dp[0][0]=0
AI=[]

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

for i in range(1,N+1):
    a=AI[i-1][0]
    I=AI[i-1][1]
    for j in range(N+1):
        if j==0:
            dp[i][j]=dp[i-1][j]+abs(I-(N+1-i))*a
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+abs(I-j)*a
        else:
            dp[i][j]=max(dp[i-1][j-1]+abs(I-j)*a,dp[i-1][j]+abs(I-(N+1-(i-j)))*a)
ans=0
for i in range(N+1):
    ans=max(ans,dp[N][i])

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'

    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True








class SegTree:

    def __init__(self,n,init_val=0,function=lambda a,b:a+b,ide=0):
        self.n=n
        self.ide_ele=ide_ele=ide
        self.num=num=2**(n-1).bit_length()
        self.seg=seg=[self.ide_ele]*2*self.num
        self.lazy=lazy=[self.ide_ele]*2*self.num
        self.segfun=segfun=function
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
        
        
    def evaluate(k,l,r): 
        if lazy[k]!=0:
            node[k]+=lazy[k]
            if(r-l>1):
                lazy[2*k+1]+=lazy[k]//2
                lazy[2*k+2]+=lazy[k]//2

        lazy[k]=0
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfun(res,self.seg[p])
            if q&1 == 1:
                res = self.segfun(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfun(res,self.seg[p])
        else:
            res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
        return res

    def __str__(self):
        
        rt=self.seg[self.num-1:self.num-1+self.n]
        return str(rt)


ans=0

n=I()
a=LI()
dp=[[0]*(n+1)for i in range(n+1)]
b=sorted(list(enumerate(a)),key=lambda x:-x[1])

for i in range(n):
    j,x=b[i]
    for l in range(i+1):
        dp[i+1][l+1]=max(dp[i+1][l+1], dp[i][l]+abs(l-j)*x)
        dp[i+1][l]  =max(dp[i+1][l],   dp[i][l]+abs(n-(i-l) -(j+1))*x)
        
print(max(dp[-1]))

Solution (Python):

import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

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


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


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

for wa in range(1, N+1):
    
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)

Solution (Python):

import sys
INF = float("inf")
MOD = 10**9+7

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


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


DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        

print(max([DP[(x, N-x)] for x in range(N+1)]))

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


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):
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+1)]


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

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

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())
A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[None for r in range(n+1)] for l in range(n+1)]

def dp(l, r):
    if l == r:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    a, i = A[n-(r-l)]
    x = dp(l+1, r)+a*abs(i-l)
    y = dp(l, r-1)+a*abs(i-(r-1))
    DP[l][r] = max(x, y)
    return DP[l][r]

print(dp(0, n))

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

A = sorted([(val, pos) for pos, val in enumerate(A)], reverse=True)

dp = [0]
for i, (val, pos) in enumerate(A):
    ldp = [e + val * abs(pos - (i - r)) for r, e in enumerate(dp)]
    rdp = [e + val * abs(N - 1 - r - pos) for r, e in enumerate(dp)]
    dp = [max(L, R) for L, R in zip(ldp + [0], [0] + rdp)]

print(max(dp))

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

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

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

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)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)

Solution (Python):
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(n+1):
        for y in range(n+1-x):
            if x == y == 0:
                continue
            ai, i = aii[n-x-y]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1) if x > 0 else 0,
                           dp[x][y-1] + ai * (n-y-i) if y > 0 else 0)

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted((a[i], i)for i in range(n))
    print(solve(n, aii))

Solution (Python):
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1),
                           dp[x][y-1] + ai * (n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]
    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))

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

B = sorted(A, reverse=True)

C = [0] * N

i = 0
while(1):
    if i >= N:
        break
    for j in range(N):
        if A[j] == B[i]:
            C[i] = j
            if i != N-1 and B[i] == B[i+1]:
                i += 1
    i += 1

dp = [[0] * (N+1) for i in range(N+1)]
for i in range(N+1):
    for j in range(i+1):
        if j > 0 and i-j > 0:
            dp[j][i-j] = max([dp[j-1][i-j] + B[i-1] * abs(C[i-1] - (j-1)), dp[j][i-j-1] + B[i-1] * abs(C[i-1] - (N-1-(i-j-1)))])
        elif j == 0 and i-j > 0:
            dp[j][i-j] = dp[j][i-j-1] + B[i-1] * abs(C[i-1] - (N-1-(i-j-1)))
        elif i-j == 0 and j > 0:
            dp[j][i-j] = dp[j-1][i-j] + B[i-1] * abs(C[i-1] - (j-1))


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

print(ans)

Solution (Python):
import numpy as np

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

babies = sorted([(activity, index) for index, activity in enumerate(A, 1)], reverse=True)

DP = np.zeros(n+1, dtype=np.int64)
position = np.arange(1, n+1, dtype=np.int64)

for filled, (activity, index) in enumerate(babies, 1):
    to_left = DP[:filled] + abs((position[:filled]-index)*activity)
    to_right = DP[:filled] + abs((position[-filled:]-index)*activity)
    DP[1:filled+1] = np.maximum(DP[1:filled+1], to_left)
    DP[:filled] = np.maximum(DP[:filled], to_right)

print(DP.max())

Solution (Python):


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


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

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



answer = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + B[i][1]*(abs(B[i][0]-i))
    for j in range(N):
        dp[0][j+1] = dp[0][j] + B[j][1]*(abs(N-1-B[j][0]-j))
        if i+j+1 < N:
            dp[i+1][j+1] = max(dp[i][j+1]+B[i+j+1][1]*(abs(B[i+j+1][0]-i)), dp[i+1][j] + B[i+j+1][1]*(abs(N-1-B[i+j+1][0]-j)))
    answer = max(answer, dp[i][N-i])

print(answer)

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

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

li = []
for i in range(n):
    li.append((a[i],i))

li.sort(reverse = True)

for i in range(1,n+1):
    tmp = li[i-1]
    for ii in range(i+1):
        jj = i - ii
        if ii == 0:
            dp[ii][jj] = dp[ii][jj-1] + tmp[0] * abs((n - jj) - tmp[1])
        elif jj == 0:
            dp[ii][jj] = dp[ii-1][jj] + tmp[0] * abs((ii - 1) - tmp[1])
        else:
            dp[ii][jj] = max(dp[ii][jj-1] + tmp[0] * abs((n - jj) - tmp[1]), dp[ii-1][jj] + tmp[0] * abs((ii - 1)- tmp[1]))


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

print(ans)

Solution (Python):
n = int(input())
a = [(int(j), i) for i, j in enumerate(input().split())]
a.sort(reverse=1)
dp = [[0] * (n+1) for _ in range(n + 1)]

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

Solution (Python):
def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x,out=dp[time+1][:-1])
    print(np.max(dp[n]))
main()

Solution (Python):
def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        dp[time+1][:-1]=np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x)
    print(np.max(dp[n]))
main()

Solution (Python):

N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0] * (N+1) for i in range(N+1)]

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0][i] = dp[0][i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i][0] = dp[i-1][0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x][y]= max(dp[x-1][y] + abs(k-x)*val,
                      dp[x][y-1] + abs(N-y-k+1) * val)

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

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
b=[(a[i],i)for i in range(n)]
b.sort(reverse=1)
dp=[(n+1)*[0]for _ in range(n+1)]
for i in range(1,n+1):
  p,j=b[i-1]
  if j<i-1:break
  dp[i][0]+=dp[i-1][0]+p*(j-(i-1))
for i in range(1,n+1):
  p,j=b[i-1]
  if j>(n-i):break
  dp[0][i]+=dp[0][i-1]+p*((n-i)-j)
for i in range(1,n):
  for j in range(1,n):
    if i+j>n:break
    p,k=b[i+j-1]
    if (i-1)<=k:
      dp[i][j]=max(dp[i][j],dp[i-1][j]+p*(k-(i-1)))
    if k<=(n-j):
      dp[i][j]=max(dp[i][j],dp[i][j-1]+p*((n-j)-k))
ans=0
for i in range(n+1):ans=max(ans,dp[i][n-i])
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 len in range(1,N+1):
        val,index=AA[len-1]
        for x in range(0,len+1):
            y=len-x
            if x==0:
                dp[x][y]=dp[x][y-1]+val*abs(N-y-index)
            elif y==0:
                dp[x][y]=dp[x-1][y]+val*abs(index-x+1)
            else:
                dp[x][y]=max(dp[x][y-1]+val*abs(N-y-index),dp[x-1][y]+val*abs(index-x+1))
    maxes=[]
    for i in dp:
        maxes.append(max(i))
    return max(maxes)
print(main())

Solution (Python):
from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

Solution (Python):
n=int(input())
a=map(int,input().split())
p=[(x,i) for i,x in enumerate(a)]
p.sort(reverse=True)

ans=0
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(n+1):
    if i+j==n:
      ans=max(ans,dp[i][j])
      break
    act,ind=p[i+j]
    dp[i+1][j]=max(dp[i+1][j],
                   dp[i][j]+act*abs(ind-i))
    dp[i][j+1]=max(dp[i][j+1],
                   dp[i][j]+act*abs(n-1-j-ind))

print(ans)

Solution (Python):
'''
着想：大きいaほど左右の端に移動したい、小さいaを先に端にやるより必ず大きくなるから
問題：単純に貪欲に大きいaから左端(x-1)と右端(N-x)の大きい方に移動すると、
      残りのaの組み合わせ的に最適でない場合がある
      アイテムの左右端の単純な割り振りはO(2^N)
解決策の着想：大きい順のk個を(k=L+R)となる
    　　左L個右R個にどのように割り振っても(k+1)個目の最適な割り振り方は変わらない
解決策：アイテムk個左右に割り振る状態をdp[L][R]で保存O(N^2)
'''

def solve():
  N = int(input())
  A = [[a, i] for a,i in zip(map(int, input().split()), range(N))]
  A.sort(key=lambda a: a[0], reverse=True)

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

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

Solution (Python):
n=int(input())
a=list(enumerate(map(int,input().split())))
a.sort(key=lambda x: -x[1])
dp=[[0]*(n+1) for i in range(n+1)]
for idx,ix in enumerate(a):
    i,x=ix
    for j in range(idx+1):
        dp[j+1][idx-j]=max(dp[j+1][idx-j],dp[j][idx-j]+(i-j)*x)
        dp[j][idx-j+1]=max(dp[j][idx-j+1],dp[j][idx-j]+((n-1-(idx-j))-i)*x)
print(max([dp[i][n-i] for i in range(n+1)]))

Solution (Python):
import sys
import math
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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

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

for i in range(N):
  happy, ID = b[i]
  
  for l in range(i+1):
    lcnt = l
    rcnt = i - lcnt
    r = N-1 - rcnt
    if i > l-1:
      dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + happy*abs(ID - l))
      dp[i+1][l] = max(dp[i+1][l], dp[i][l] + happy*abs(ID - r))
    else:
      break
    
    
  
print(max(dp[-1]))