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:
N = int(input())
A = list(map(int, input().split()))
table = []

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

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + table[i-1][0] * abs(table[i-1][1]  - x+1)) * (x>0),\
                     (DP[x][y-1] + table[i-1][0] * abs(table[i-1][1] - (N - y))*(y>0)))


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

Submission status: Accepted

Solution code:
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [[a,i] for i,a in enumerate(LI())]
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]))

Submission status: Accepted

Solution code:
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
data = [(a,i) for i,a in enumerate(LI())]
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]))

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

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

dp = [[0 for _ in range(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]))

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int, input().split()))
l = 0
r = n-1

data = [[i, a] for i, a in enumerate(al)]
data.sort(key=lambda x: x[1], reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    for j in range(0, i+1):
        p, a = data[i]
        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]))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=list(zip(range(n),a))#[index,a]の配列
a.sort(key=lambda x:x[1])#aの昇順で並べる
dp=[[0 for i in range(n+1)]for j in range(n+1)] #dp[x][y]:=左にx、右にy人並べたときの最大値
ans=0
for k in range(n):# k人目まで終了、k+1人目に対して
  i,ai=a.pop()#aの大きいものから取り出す
  dp[k+1][0]=dp[k][0]+ai*(i-k)
  dp[0][k+1]=dp[0][k]+ai*(n-k-1-i)
  for l in range(k):#右にl+1人並べたとき
    dp[k-l][l+1]=max(dp[k-l-1][l+1]+ai*(i-k+l+1),dp[k-l][l]+ai*(n-l-1-i))
for k in range(n+1):
  ans=max(ans,dp[k][n-k])

print(ans)

Submission status: Accepted

Solution code:

def main():

  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = [[0] * (n + 1) for _ in range(n + 1)]
  for i, (p, a) in enumerate(arr):
    for l in range(i + 1):
      dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
      dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

  print(max(dp[n]))

main()

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)

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)
#print(dp)

Submission status: Accepted

Solution code:
def f(n, a_list):
    a_list = list(zip(range(n), a_list))
    a_list.sort(key=lambda x: x[1])
    # a_list[j][0]: (j + 1)番目に小さい活発度をもつ幼児の座標
    # a_list[j][1]: ↑の活発度
    dp = [0]
    # dp[x]: x 人を左, (k - x) 人を右に置く場合
    for k in range(1, n + 1):
        dp_ = []
        i, a = a_list.pop()  # i: 座標, a: 活発度
        dp_.append(dp[0] + a * (n - k - i))
        for x in range(1, k):
            dp_.append(max(dp[x - 1] + a * (i - x + 1),
                           dp[x] + a * (n - k + x - i)))
        dp_.append(dp[k - 1] + a * (i - k + 1))
        dp = dp_
    return max(dp)


if __name__ == '__main__':
    n = int(input())
    a_list = list(map(int, input().split()))
    print(f(n, a_list))

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import math
import bisect
import datetime

n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().strip().split()))
arr.insert(0,0)
d={}
for i in range(len(arr)):
    d[i] = arr[i]
arr = sorted(d.items(), key=lambda a: a[1])

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

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

for l in range(2, n + 1):
    pos, val = arr[l]
    for left in range(1, n - l + 2):
        right = left + l - 1
        dp[left][right] = max(dp[left + 1][right] + val * abs(pos - left), dp[left][right - 1] + val * abs(pos - right))

stdout.writelines(str(dp[1][n]) + '\n')

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()
mod = 10**9 + 7

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

    B = []
    for i, a in enumerate(A):
        B.append((a, i + 1))
    B.sort()
    #print(B)

    """
    活発度が大きい方から左右どちらかの端に移動させるが左右どちらになるかは一般に不明。
    しかし端から埋まるのは明らか（厳密な論証はmaspyさんの解説がわかりやすい）なので、
    ここから先をDPすればよい。具体的には
        dp[n][L] = (n人並べているとして左にL人いるときのうれしさの最大値)
    とすれば、これよりdp[n+1][L], dp[n+1][L+1]が更新できる。
    またn人の部分はdpとdp2間の遷移にしてメモリ削減。
    """

    dp = [0] * (N + 1)
    for n in range(1, N + 1):
        (a, i) = B.pop()
        dp2 = [0] * (N + 1)
        dp2[0] = dp[0] + a * abs((N - n + 1) - i)
        for l in range(1, n): # 1-indexedなことに注意
            dp2[l] = max(dp[l - 1] + a * abs(i - l), dp[l] + a * abs((N - n + l + 1) - i))
        dp2[n] = dp[n - 1] + a * abs(n - i)
        dp = dp2
        #print("{}人配置→dp={}".format(n, dp))
    print(max(dp))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

A = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
dp = [[0]*(N+1) for _ in range(N+1)]

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

print(max(dp[N]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
babies = [(a, i) for i, a in enumerate(A)]
babies.sort(reverse=True)
# print(babies)
dp = [[0]*(N+1) for _ 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
        active, index = babies[l+r]
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] +
                         abs(index - (N - 1 - r))*active)
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(index - l)*active)

print(ans)

Submission status: Accepted

Solution code:
import sys 
try:
	sys.stdin = open('input.txt', 'r') 
	sys.stdout = open('output.txt', 'w')
except:
	pass

input = sys.stdin.readline

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

arr = list(enumerate(arr))
arr.sort(reverse = True, key = lambda x:(x[1]))
dp = [[0 for c in range(n+1)] for r in range(n+1)]
ans = 0
for r in range(n+1):
	st = r-1
	for c in range(n+1-r):
		if r==c==0:
			pass
		elif r-1<0:
			dp[r][c] = dp[r][c-1] + ( arr[st][1] * abs((arr[st][0]+1) - (n+1-c)) )

		elif c-1<0:
			dp[r][c] = dp[r-1][c] + ( arr[st][1] * abs((arr[st][0]+1) - r) )

		else:
			dp[r][c] = max( dp[r-1][c] + ( arr[st][1] * abs((arr[st][0]+1) - r) ), 
						dp[r][c-1] + ( arr[st][1] * abs((arr[st][0]+1) - (n+1-c)) )                           
						)
		ans = max(ans, dp[r][c])
		st += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
p = sorted([(x, i) for i, x in enumerate(a)], reverse=True)
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for s in range(1, n+1):
	for x in range(s+1):
		y = s-x
		if x > 0:
			dp[x][y] = max(dp[x][y], dp[x-1][y] + abs(p[s-1][1] - x + 1) * p[s-1][0])
		if y > 0:
			dp[x][y] = max(dp[x][y], dp[x][y-1] + abs(n-y - p[s-1][1]) * p[s-1][0])
print(max(dp[x][n-x] for x in range(n+1)))

Submission status: Accepted

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

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

dp = [[0]*(N+1) for _ 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
        else:
            a, i = A[l+r]
            dp[l+1][r] = max(dp[l+r][r], dp[l][r] + a*abs(l-i))
            dp[l][r+1] = max(dp[l][r+1], dp[l][r] + a*abs((N-1-r)-i))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = sorted(zip(a, range(0, n)), reverse=True)
p = [0] * n
for i in range(n):
    p[i] = l[i][1]
a.sort(reverse=True)
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[j][k] = dp[j][k - 1] + abs(n - k - p[i - 1]) * a[i - 1]
        elif k == 0:
            dp[j][k] = dp[j - 1][k] + abs(j - 1 - p[i - 1]) * a[i - 1]
        else:
            dp[j][k] = max(dp[j][k - 1] + abs(n - k - p[i - 1]) * a[i - 1],
                           dp[j - 1][k] + abs(j - 1 - p[i - 1]) * a[i - 1])
ans = 0
for i in range(n):
    ans = max(ans, dp[n - i][i])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

N = int(input())
#X, Y = map(int,input().split())
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+2)] for _ in range(N+2)]
#for x in range(1,N+2):
#    for y in range(1,N+2):
##        print(act,i)
#        dp[x][y] = max(dp[x-1][y] + B[y][0] * (B[y][1] - 0 - (x-2))
#                    , dp[x][y-1] + B[y][0] * (N - 1 - B[y][1] - (y-2)))
        
dp = np.zeros(1, dtype=int)
zero = np.zeros(1, dtype=int)
for act, i in B:
    prev = dp.copy()
    dp = np.append(dp,[0])
    l = len(prev)
        
    right = np.arange((N-1-i)*act,(N-1-i)*act - (act*(l)),-act)
    left = np.arange(i*act-(act*(l-1)),(i+1)*act,act)
#    print(left,right,prev,dp)
    np.maximum(np.concatenate([prev + left, zero]),
               np.concatenate([zero, prev + right]),
               out = dp)
#    print(dp)

print(np.max(dp))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000 * 2)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Submission status: Accepted

Solution code:
(N,) = map(int, input().split())
As = list(enumerate(map(int, input().split())))
As.sort(key=lambda x: -x[1])
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (pos, val) in enumerate(As):
    for j in range(i + 1):
        k = i - j
        dp[j + 1][k] = max(dp[j + 1][k], dp[j][k] + abs(j - pos) * val)
        dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + abs(N - 1 - k - pos) * val)
print(max(dp[i][N - i] for i in range(N + 1)))

Submission status: Accepted

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

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

s = 0
for i, A in sorted(enumerate(As), key = lambda t:t[1], reverse=True):
    s += 1
    for x in range(s+1):
        y = s - x
        if x > 0 and y > 0:
            dp[x][y] = max(dp[x-1][y] + A * (i - x + 1), dp[x][y-1] + A * ((N-y) - i))
        elif x == 0:
            dp[x][y] = dp[x][y-1] + A * ((N-y) - i)
        else:
            dp[x][y] = dp[x-1][y] + A * (i - x + 1)
ans = max((dp[x][N-x] for x in range(N+1)))

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield p+abs(j-i)*a, s+abs(j+r)*a
    p = s
  yield s+abs(len(prev)-i)*a,

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*map(max, solve(a,i, pd))]

print(max(pd))

Submission status: Accepted

Solution code:
N = int(input())

def left(a, i, prev):
  yield 0
  for l, s in enumerate(prev, 1-i):
    yield s+abs(l)*a
    
def right(a, i, prev):
  for r, s in enumerate(prev, N - len(prev) - i + 1):
    yield s+abs(r)*a
  yield 0

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*map(max, zip(left(a,i, pd), right(a,i, pd)))]

print(max(pd))

Submission status: Accepted

Solution code:
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print(max(pd))

Submission status: Accepted

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

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

    dp = [[0] * r for r in reversed(range(1, N + 2))]
    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()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(enumerate(iim()))

    A.sort(key=lambda x: (x[1], (2*x[0]-N)**2), reverse=True)

    dp = [0] * (N+1)
    dp0 = dp[:]
    for i, (j, ai) in enumerate(A):
        for k in range(i+1):
            dp[k] = max(dp[k], dp0[k] + abs(N-i+k-1-j) * ai)
            dp[k+1] = max(dp[k+1], dp0[k] + abs(k-j) * ai)
        dp, dp0 = dp0, dp

    print(max(dp0))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

N = int(input())

A = map(int, input().split())
AI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev):
  pl, pr, ps = i, 0, 0
  for l, r, s in prev:
    yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
for a,i in AI:
  prev = [*solve(a,i, prev)]

print(max(s for l, r, s in prev))

Submission status: Accepted

Solution code:
from operator import itemgetter as get
N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th, tha):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th-max(l,r)*tha:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB, SA)]
  pm = M
  SA -= a
  SB -= b

print(pm)

Submission status: Accepted

Solution code:
from operator import itemgetter as get
N = int(input())

A = map(int, input().split())
SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s),) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB)]
  pm = M
  SB -= b

print(pm)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 math import gcd,ceil,floor,factorial
# from fractions import gcd
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)
# print(ls)

dp = [ [0]*(n+1) for _ in range(n+1) ]
# dp[i][l]: Aが大きい方からi番目まで決め，左へ移動した個数がl個である時の，スコアの最大値

for i in range(n):
    f = ls[i][0]
    A = ls[i][1]
    for l in range(i+1):
        #
        # 【このi番目を右へ寄せる場合（左へ寄せない場合）】
        # 移動先t
        t = n - i + l - 1
        # スコア
        s = A*abs(t-f)
        # dpテーブルの要素としての更新候補
        dp1 = dp[i][l] + s
        # 既に入っている値より大きければ更新
        if dp1 > dp[i+1][l]:
            dp[i+1][l] = dp1
        #
        # 【このi番目を左へ寄せる場合】
        # 移動先t
        t = l
        # スコア
        s = A*abs(t-f)
        # dpテーブルの要素としての更新候補
        dp2 = dp[i][l] + s
        #
        # 既に入っている値より大きければ更新
        if dp2 > dp[i+1][l+1]:
            dp[i+1][l+1] = dp2
# pprint(dp)

print(max(dp[n]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
# print(p)
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)]
# dp[i][j] : 左からi個，右からj個詰めてある状態の時の最高スコア

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))
        # print('i,j={},{}'.format(i,j))
        # print(dp)
        
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


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])  # type:int
    A_arr = list(map(int,_in[1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    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)) # left
            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])) # right
    cnt = 0
    for i in range(0,N+1):
        cnt = chmax(cnt, dp[i][N-i])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
# ai の大きい方から左端か右端
# はるかに問題なのはそこから先だがDP
n=int(input())
*a,=map(int, input().split( ))
dp = [0]
#周回が総数、dpのindexが左に置いた数
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))##abs((n-(j-k-1)-1)-i)
    dp = dp2

print(max(dp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    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
#sys.setrecursionlimit(10**7)
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


## Segment Tree ##

## Initializer Template ##
# Range Sum:        sg=SegTree(n)
# Range Minimum:    sg=SegTree(n,inf,min,inf)

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
        #set_val
        for i in range(n):
            self.seg[i+self.num-1]=init_val
        #built
        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]))