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



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
参考にしました(写経)
https://atcoder.jp/contests/abc163/submissions/12137623
"""
n = I()
a = LI()
b = [[a[i],i] for i in range(n)]
b.sort(reverse=1)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    a,j = b[i]
    for k in range(i+1):
        dp[k][i+1-k] = max(dp[k][i+1-k], 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)) #左側に追加

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

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(2000)


N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

A_mat = []
for i,A in enumerate(As):
    A_mat.append([A,i])

A_mat.sort(reverse=True)

map1 = []

for i in range(N+1):
    temp = [-1]*(N+1)
    map1.append(temp)



def DP(x, y): #Asのなかからx+y個の数列をすでに端に移動していて、x個左端に, y個右端に移動している状態から始めたときに追加で得られるスコア
    if map1[x][y]>=0:
        return map1[x][y]
    
    if x+y == N:
        return 0

    a_val = A_mat[x+y][0]
    a_pos = A_mat[x+y][1]

    left_case = abs(a_pos-x)
    right_case = abs((N-y-1)-a_pos)

    map1[x][y] = max(DP(x+1,y)+left_case*a_val, DP(x,y+1)+right_case*a_val)

    return map1[x][y]

print(DP(0,0))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [(i, a[i]) for i in range(n)]
b = sorted(b, key=lambda x: x[1])[::-1]

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

print(ans)

Submission status: Accepted

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

dp = [[0] * (N+1) for i in range(N+1)]
s, i = B[0]
dp[1][0] = s*(i - 1)
dp[0][1] = s*(N - i)
for n in range(2, N+1):
  a, i = B[n-1]
  for l in range(n+1):
    r = n - l
    if l == 0:
      dp[l][r] = dp[l][r-1] + abs(N-r+1 - i)*a
    elif r == 0:
      dp[l][r] = dp[l-1][r] + abs(l - i)*a
    else:
      dp[l][r] = max(dp[l-1][r]+abs(l-i)*a, dp[l][r-1]+abs(N-r+1-i)*a)

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

print(ans)

Submission status: Accepted

Solution code:
import itertools
n = int(input())
l = list(map(int,input().split()))
li = [i for i in range(n)]

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
_L = list(map(int,input().split()))

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:(-x[0],x[1]))

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

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))

Submission status: Accepted

Solution code:
N = int(input())
_L = list(map(int,input().split()))

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:(-x[0],-x[1]))

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

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)


def solve(N, A):
    q = [(a, i) for i, a in enumerate(A)]
    q.sort(reverse=True)
    dp = [[-1 for _ in range(N + 1)] for __ in range(N + 1)]

    x = 0
    y = 0
    dp[x][y] = 0
    for a, i in q:
        dp[x+1][y] = dp[x][y] + a * abs(i - x)
        x += 1
    x = 0
    for a, i in q:
        dp[x][y+1] = dp[x][y] + a * abs(N - 1 - y - i)
        y += 1

    ans = 0
    for x in range(1, N+1):
        for y in range(1, N+1):
            if x + y > N:
                continue
            a, i = q[x+y-1]
            left = a * abs(i - (x - 1))
            right = a * abs(N - 1 - (y - 1) - i)
            dp[x][y] = max(dp[x-1][y] + left, dp[x][y-1] + right)
            ans = max(ans, dp[x][y])
    # [print(row) for row in dp]
    return ans

def slow_solve(N, A):
    import itertools
    ans = 0
    K = [i for i in range(N)]
    for p in itertools.permutations(K):
        tans = 0
        for i in range(N):
            tans += A[i] * abs(p[i] - i)
        ans = max(ans, tans)
    return ans

#
# assert (slow_solve(4, [1, 3, 4, 2]) == 20)
# assert (slow_solve(4, [1, 3, 4, 2]) == 20)
# assert (slow_solve(6, [5, 5, 6, 1, 1, 1]) == 58)
# assert (slow_solve(6, [8, 6, 9, 1, 2, 1]) == 85)
# print("OK")
if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split(" ")))

    print(solve(N, A))

Submission status: Accepted

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    N = int(input())
    A = [(a, i) for i, a in enumerate(map(int, input().split()))]
    A.sort(reverse=True)
    
    dp = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for k in range(N):
        for i in range(k + 1):
            j = k - i
            here = dp[i][j]
            a, idx = A[k]
            dp[i + 1][j] = max(dp[i + 1][j], here + a * ((N - 1 - i) - idx))
            dp[i][j + 1] = max(dp[i][j + 1], here + a * (idx - j))
            # print(k, i)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for x in range(N):
        for y in range(N-x):
            i, d = A[x+y]
            dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
            dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

Submission status: Accepted

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

x = 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(x):
    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[-1]))

Submission status: Accepted

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

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):
        cnt = i + j
        if cnt == 0: continue
        if cnt > n: continue
        if i == 0:
            dp[0][j] = dp[0][j-1] + li[cnt-1][1] * ((n - j) - li[cnt-1][0])
            continue
        if j == 0:
            dp[i][0] = dp[i-1][0] + li[cnt-1][1] * (li[cnt-1][0] - (i-1) )
            continue
        
        
        res1 = dp[i][j-1] + li[cnt-1][1] * (n - j - li[cnt-1][0])
        res2 = dp[i-1][j] + li[cnt-1][1] * (li[cnt-1][0] - (i-1))
        dp[i][j] = max(res1,res2)
        if cnt ==n:
            ans = max(ans,dp[i][j])

print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    A=list(zip(list(map(int,input().split())),range(n)))
    A.sort(reverse=True)
    DP=[[0]*(n+1) for _ in range(n+1)]
    for i in range(n+1):
        for j in range(n+1):
            if i+j>n:
                break
            a,idx=A[i+j-1]
            if i>0:
                DP[i][j]=max(DP[i][j],DP[i-1][j]+a*abs(idx-(i-1)))
            if j>0:
                DP[i][j]=max(DP[i][j],DP[i][j-1]+a*abs(idx-(n-j)))
    ans=0
    for i in range(n+1):
        ans=max(ans,DP[i][n-i])
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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


# dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
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]))

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    for i in range(n):
        val = max(a)
        idx = a.index(val)
        a[idx] = 0
        for j in range(i + 1):
            left = j
            right = i - j
            prev = dp[left][right]
            dp[left + 1][right] = max(dp[left + 1][right], prev + val * (idx - left))
            dp[left][right + 1] = max(dp[left][right + 1], prev + val * ((n - 1 - right) - idx))

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    #aの大きい順に、左右どちらかの端から埋めていく
    n=II()
    aa=LI()
    dp=[[0]*(n+1) for _ in range(n+1)]
    #dp[l][r]...左からl人、右からr人埋まっているときの最大値
    for s,(i,a) in enumerate(sorted(enumerate(aa),key=lambda x:-x[1])):
        for l in range(s+1):
            r=s-l
            pre=dp[l][r]
            dp[l+1][r]=max(dp[l+1][r],pre+abs(l-i)*a)
            dp[l][r+1]=max(dp[l][r+1],pre+abs(n-1-r-i)*a)
    ans=0
    for l in range(n+1):
        ans=max(ans,dp[l][n-l])
    print(ans)

main()

Submission status: Accepted

Solution code:
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]+(idx-i)*v)
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]+(N-1-j-idx)*v)
    
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
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 = max(dp.values())

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
dp = [[-1]*N for _ in range(N)]

def rec(l, r):
	if l > r:
		return 0
	if dp[l][r] >= 0:
		return dp[l][r]
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	dp[l][r] = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return dp[l][r]

print(rec(0, N-1))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc163/tasks/abc163_e

dpか？
なにを基準にdpすればよい？
まとめられる状態は？
小さいことを考えると貪欲かなぁ
かいてみるか

挿入dp?
前から決めていけば、累積和で減る量がわかる
&増える寄与も計算できる
O(N**2)

全探索はむり

======答えを見ました======
今より右に行く、左に行くの集合に分けたとすると
大きい奴をより左にする方が最適
よって、途中まで単調減少、途中から単調増加が最適であるとわかる

dp[大きい方からi番目まで見た][左にl個つめた] = 最大値
で解ける

"""


N = int(input())

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

ans = 0

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

for i in range(N):

    na,nind = ai[i]

    for l in range(i+1):

        r = N-1-(i-l)
        dp[i+1][l+1] = max(dp[i+1][l+1] , dp[i][l] + na*abs(nind-l) )
        dp[i+1][l]   = max(dp[i+1][l] , dp[i][l] + na*abs(nind-r) )

print (max(dp[N]))

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
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(1,n+1):
    x,y = b[i-1]
    for j in range(i+1):
        left = dp[i-1][j-1] + x*abs(y-j+1) if j > 0 else -1
        right = dp[i-1][j] + x*abs(n-i+j-y) if j < i else -1
        dp[i][j] = max(left,right)

print(max(dp[-1]))

Submission status: Accepted

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

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

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

for j in range(1, N + 1):
    dp[0][j] = dp[0][j - 1] + D[j - 1][0] * abs(D[j - 1][1] - (N - j))

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

for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i + j > N:
            continue
        dp[i][j] = max(dp[i][j - 1] + D[i + j - 1][0] * abs(D[i + j - 1][1] - (N - j)), dp[i - 1][j] + D[i + j - 1][0] * abs(D[i + j - 1][1] - (i - 1)))

res = 0

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

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = list(zip(list(map(int, input().split())), range(N)))
A.sort(reverse=True)
dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(1, N+1):
    a, k = A[i-1]
    dp[i][0] = dp[i-1][0] + a * abs(N-i-k)
    for j in range(1, i):
        dp[i][j] = max(dp[i-1][j] + a * abs(N-(i-j)-k), dp[i-1][j-1] + a * abs(j-1-k))
    dp[i][i] = dp[i-1][i-1] + a * abs(i-1-k)
print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(5000)

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

memo = {}

def solve(i, l, r):
    if i==N: return 0

    key = l*N+r
    if key in memo: return memo[key]
    
    a, loc = A[i]
    score_l = a*abs(l-loc) + solve(i+1, l+1, r)
    score_r = a*abs(r-loc) + solve(i+1, l, r-1)
    retval = max(score_l, score_r)
    memo[key]=retval
    
    return retval
    
print(solve(0, 0, N-1))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        # for j in range(n):
        #    dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, n + n - 1 - i)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang, pos):
    lb_rang = 0
    ub_rang = len(rang) - 1
    lb_pos = 0
    ub_pos = len(pos) - 1
    ret= 0 
    while lb_rang <= ub_rang:
        if abs(rang[lb_rang]-pos[ub_pos]) < abs(rang[ub_rang]-pos[lb_pos]):
            ret += abs(rang[ub_rang]-pos[lb_pos])
            ub_rang -= 1
            lb_pos += 1
        else:
            ret += abs(rang[lb_rang]-pos[ub_pos]) 
            lb_rang += 1
            ub_pos -= 1
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))

Submission status: Accepted

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

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


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

for i in range(0,N-1):
    a,index=A[-1]
    dp[N-1][i]=a*abs(index-i)

for _ in range(1,N):
    i=N-1-_
    for j in range(0,i+1):
        left=j
        right=i-j
        a,index=A[i]
        ans=0
        if index>left-1:
            ans=max(ans,dp[i+1][j+1]+a*(index-left))

        if N-right>index:
            ans=max(ans,dp[i+1][j]+a*(N-right-1-index))

        dp[i][j]=ans

print(dp[0][0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
  b.append([a[i],i])
b.sort(reverse=True)
now = [0]
for i in range(n):
  aj,j = b[i]
  last = now
  now = []
  for l in range(i+1):
    r = l+n-1-i
    now.append(last[l]+aj*abs(r-j))
    #print(aj,j,l,r,abs(r-j))
  #print(now,'#',aj,j)
  for l in range(i):
    now[l+1] = max(now[l+1],last[l]+aj*abs(l-j))
  now.append(last[-1]+aj*abs(i-j))
  #print(now)
print(max(now))

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))

INF = 10 ** 16

dp = [-INF] * (n + 1)
dp[0] = 0

import heapq
q = []
for i in range(n):
    heapq.heappush(q, (-l[i], i))

for itera in range(n):
    _, ind = heapq.heappop(q)
    val = l[ind]
    dpnew = [-INF] * (n + 1)

    for i in range(n):
        left = dp[i] + abs(i - ind) * val
        right = dp[i] + abs(n - 1 - itera + i - ind) * val
        if dpnew[i] < right:
            dpnew[i] = right
        if dpnew[i+1] < left:
            dpnew[i+1] = left
    dp = dpnew
print(max(dp))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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 i in range(n)]

DP[0][0] = B[0][0] * B[0][1]
DP[0][1] = B[0][0] * (n-1-B[0][1])


for i in range(1, n):
    ind = B[i][1]
    for j in range(i+2):
        if j-1 >= 0:
            DP[i][j] = DP[i-1][j-1] + B[i][0] * abs(n-1-(j-1)-ind)
        # print(i,j,ind, i+1-j, ind-(i+1-j))
        DP[i][j] = max(DP[i][j], DP[i-1][j] + B[i][0] * abs(ind-(i-1+1-j)))
# print(DP)
print(max(DP[-1]))

Submission status: Accepted

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

DP = [-float("inf")]*(n+1)

for i in range(n):
    if i == 0:
        DP[1] = a[b[i]]*b[i]
        DP[0] = a[b[i]]*(n-1-b[i])
    else:
        nxt = [-float("inf")]*(n+1)
        for j in range(i+2):
            if j == 0:
                nxt[j] = DP[j] + a[b[i]]*abs(n-1-i-b[i])
            else:
                nxt[j] = DP[j] + a[b[i]]*abs(n-1-(i-j)-b[i])
                nxt[j] = max(nxt[j], DP[j-1] + a[b[i]]*abs(j-1-b[i]))
        DP = nxt
print(max(DP))

Submission status: Accepted

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

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

dp = [[-1] * n for _ in range(n)]
for i2 in range(n-1, -1, -1):
    a, i = a2[i2]

    for s in range(i2+1):
        if i2 == n-1:
            dp[i2][s] = a * abs(s-i)
        else:
            dp[i2][s] = max(dp[i2+1][s+1] + a * abs(s - i),
                            dp[i2+1][s] + a * abs(n-1-i2+s - i))

print(dp[0][0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a2 = [(a[i], i) for i in range(n)]
a2.sort(reverse=True)
# print(a2)

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

for i, (aj, j) in enumerate(a2):
    for k in range(i + 1):
        # left
        dp[i + 1][k + 1] = max(dp[i][k] + aj * abs(k - j), dp[i + 1][k + 1])

        # right
        dp[i + 1][k] = max(dp[i][k] + aj * abs((n - i + k - 1) - j),
                           dp[i + 1][k])

ans = max(dp[n])
print(ans)
# print(*dp, sep='\n')

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9
inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

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

    AA = []
    for i, a in enumerate(A):
        AA.append((a, i))
    AA.sort(key=lambda x: x[0], reverse=True)

    dp = [[-inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        a, x = AA[i]
        for j in range(N):
            if dp[i][j] != -inf:
                # left
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a * abs(x - j))
                # right
                dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * abs(x - (N-1 - (i - j))))
    #print(dp)
    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()

Anew = []
for i in range(N):
    Anew.append((A[i],i))
Anew.sort(key=lambda x:(-x[0],x[1]))

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            continue
        if i+j > N:
            continue
        elif i == 0:
            dp[i][j] = dp[i][j-1] + abs(Anew[j-1][1]-(N-j))*Anew[j-1][0]
        elif j == 0:
            dp[i][j] = dp[i-1][j] + abs(Anew[i-1][1]-(i-1))*Anew[i-1][0]
        else:
            val1 = dp[i][j-1] + abs(Anew[i+j-1][1]-(N-j))*Anew[i+j-1][0]
            val2 = dp[i-1][j] + abs(Anew[i+j-1][1]-(i-1))*Anew[i+j-1][0]
            dp[i][j] = max(val1,val2)

ans = 0
for i in range(N):
    if dp[i][N-i] >= ans:
        ans = dp[i][N-i]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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[i-th item][put j item left] : max value
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
        # put left
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + abs(index - j) * item)
        # put right
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + abs(index - (n - 1 - i + j)) * item)

print(max(dp[-1]))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]
    # left
    for j in range(n):
        dp[ind + 1][j + 1] = max(dp[ind][j] + abs(i - j) * val, dp[ind + 1][j + 1])
    # right
    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]))

Submission status: Accepted

Solution code:
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]  # index left_index left:0 right:0
for i in range(N):
    new = [0] * (i + 2)
    _a, index = heapq.heappop(heap)
    a = -_a

    # case add left:
    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))

# Vj
# while heap:
#     _a, i = heapq.heappop(heap)
#     a = - _a
#     # multiple same val order is small to large
#     if i - left_ >= (N - 1 - right) - i:
#         print("L", i, a)
#         ans += (i - left_) * a
#         left_ += 1
#     else:
#         print("R", i, a)
#         ans += ((N - 1 - right) - i) * a
#         right += 1

Submission status: Accepted

Solution code:
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)