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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=list(map(int,input().split()))
    B=[(A[i],i) for i in range(N)]
    B.sort(key=lambda t: -t[0])
    dp=[[0]*(N+1) for _ in range(N+1)]
    ans=0
    for i in range(N):
        for x in range(i+1):
            y=i-x
            dp[x+1][y]=max(dp[x+1][y],dp[x][y]+B[i][0]*abs(B[i][1]-x))
            dp[x][y+1]=max(dp[x][y+1],dp[x][y]+B[i][0]*abs(N-1-y-B[i][1]))
            ans=max(ans,dp[x+1][y],dp[x][y+1])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
A = LI()

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

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] + A[i+j][0] * (A[i+j][1] - i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A[i+j][0] * ((N-j-1) - A[i+j][1]))

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

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  N = int(input())
  A = [(i, v) for i, v in enumerate(map(int, input().split()))]
  values = [[0] * (N + 1) for _ in range(N + 1)]

  A.sort(key=lambda x:-x[1])

  for i, (p, v) in enumerate(A):
    for j in range(i + 1):
      left = abs((p - j) * v)
      right = abs((N - 1 - (i - j) - p) * v)

      values[i + 1][j + 1] = max(values[i][j] + left, values[i + 1][j + 1])
      values[i + 1][j] = max(values[i][j] + right, values[i + 1][j])

  print(max(values[-1]))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys
import socket

hostnames = ['N551J', 'F551C', 'X553M']
input_file = 'e1.in'
if socket.gethostname() in hostnames:
    sys.stdin = open(input_file)


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


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


def read_str_list():
    return input().split()


def read_str():
    return input()

inf = 10 ** 9
inf = 10 ** 3

def solve():
    n = read_int()
    a = read_int_list()
    b = [(a[i], i) for i in range(n)]
    b.sort()
    best = [[-inf] * (n + 1) for i in range(n + 1)]
    best[0][0] = 0
    for s in range(1, n + 1):
        for x in range(s + 1):
            y = s - x
            ai, i = b[-s]
            if x > 0:
                c = best[x - 1][y] + (n - x) * ai - i * ai
                if c > best[x][y]:
                    best[x][y] = c
            if y > 0:
                c = best[x][y - 1] - (y - 1) * ai + i * ai
                if c > best[x][y]:
                    best[x][y] = c

    # for i in range(n + 1):
    #     for j in range(n + 1):
    #         print(best[i][j], end='\t')
    #     print()

    res = - inf
    for x in range(n):
        y = n - x
        if res < best[x][y]:
            res = best[x][y]
    return res


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1])

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    pos, val = a.pop()
    pos = pos + 1

    DP[0][i] = DP[0][i-1] + abs(val * (n - i + 1 - pos))
    DP[i][0] = DP[i-1][0] + abs(val * (pos - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(val * (pos - x)),  \
            DP[x][y-1] + abs(val * (n - y + 1 - pos)))

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cost=[]
for i,g in enumerate(a):
    cost.append([g,i])
cost.sort(reverse=True)

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

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
cost=[]
for i,g in enumerate(a):
    cost.append([g,i])
cost.sort(reverse=True)

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

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

print(max(dp[-1]))

Submission status: Accepted

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

a = list(enumerate(a))
a.sort(key=lambda x: x[1])

# dp[left + right][left]
dp = [[] for _ in range(n+1)]
dp[0].append(0)

for i in range(1, n+1): # i = left + right
    ind, act = a.pop(-1)

    # all right
    dp[i].append(dp[i-1][0] + act * (n - i - ind))

    # middle
    for j in range(1, i): # j = left
        ar = dp[i-1][j] + act * (n - i + j - ind) # rightに追加
        al = dp[i-1][j-1] + act * (ind - j + 1) # leftに追加
        dp[i].append(max([ar, al]))

    # all left
    dp[i].append(dp[i-1][i-1] + act * (ind - i + 1))

print(max(dp[n]))

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N):
        for j in range(0, N - i):
            idx, a = A[i + j]
            #idx = indices[i + j]
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N - i]
        if tmp > result:
            result = tmp
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

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

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    solve(N, A)

Submission status: Accepted

Solution code:
def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

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

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


def main():

    # 整数の入力
    a = int(input())
    # # スペース区切りの整数の入力
    nums = list(map(int, input().split()))

    vilist = []
    for i in range(a):
        vilist.append((nums[i], i))
    vilist = sorted(vilist, key=lambda vi: vi[0])

    # dp[x][y]をx人を左から活性度順に並べて、y人を右から活性度順に並べた状態のスコア最大値とする
    dp = []
    for i in range(a):
        dp.append([0]*(a-i))

    # dp = [[0] * a for i in range(a)]

    # cnt = 0
    # dp[i][j]を考える
    for k in range(a-1):
        vi = vilist.pop()
        v = vi[0]
        p = vi[1]
        vi_z = vilist[0]
        vz = vi_z[0]
        pz = vi_z[1]

        for i in range(k + 2):
            # cnt += 1
            j = k - i + 1
            # if i == 0 and j == 0:
            #     continue

            # 最後の値は場所が特定できるのでそのまま計算させる
            if k == a - 2:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1) + vz * abs(pz - i)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p) + vz * abs(a - j - 1 - pz)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1) + vz * abs(pz - i),
                                   dp[i][j-1] + v * abs(a - j - p) + vz * abs(pz - i))
            else:
                if j == 0:
                    dp[i][0] = dp[i-1][0] + v * abs(p - i + 1)
                elif i == 0:
                    dp[0][j] = dp[0][j-1] + v * abs(a - j - p)
                else:
                    dp[i][j] = max(dp[i-1][j] + v * abs(p - i + 1),
                                   dp[i][j-1] + v * abs(a - j - p))

    # print(cnt)
    print(max([max(x) for x in dp]))


main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=[a[i],i]
a.sort()
a.reverse()
dp=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
  for j in range(n):
    if i+j<=n-1:
      dp[i+1][j]=max(dp[i+1][j],dp[i][j]+a[i+j][0]*abs(a[i+j][1]-i))
      dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a[i+j][0]*abs(a[i+j][1]-(n-j-1)))
ans=[]
for i in range(n):
  ans.append(dp[i][n-i])
print(max(ans))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))
    
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    x, pi = heappop(hq)
    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)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

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

f_inf = float('inf')
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    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)

Submission status: Accepted

Solution code:
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
A=list(map(int,input().split()))
que=[]
dp=[[0 for _ in range(N+1)] for _ in range(N+1)]    #dp[i][j]…左にiこ、みぎにjこあること状態になった時の最大をいれる
for i in range(N):
    que.append([A[i],i])
que.sort(key=lambda x:x[0],reverse=True)
#pprint.pprint(dp)
#print(que)
for i in range(0,N+1):
    if i!=0:
        for j in range(i+1):
            if j==0:#dp[i][0],左にiこつまる状態に
                dp[i-j][j]=dp[i-j-1][j]+(que[i-1][0]*abs((i-1)-que[i-1][1]))
            elif j==i:#dp[0][i],みぎにiこ詰まる状態に
                dp[i-j][j]=dp[i-j][j-1]+(que[i-1][0]*abs(N-j-que[i-1][1]))
            else:
                dp[i-j][j]=max(dp[i-j-1][j]+(que[i-1][0]*abs(((i-1)-j)-que[i-1][1])),dp[i-j][j-1]+(que[i-1][0]*abs(N-j-que[i-1][1])))
        #input()
        #pprint.pprint(dp)
ma=0
for i in range(0,N+1):
    #print(dp[N-i][i])
    ma=max(ma,dp[N-i][i])
print(ma)


"""
st=[-1]*N
en=[-1]*N
s=[[0,[0,0]] for _ in range(N*N)]
for i in range(N):
    for j in range(N):
        s[i*N+j][0]=A[i]*abs(i-j)
        s[i*N+j][1][0]=i
        s[i*N+j][1][1] = j
s.sort(key=lambda x:x[0],reverse=True)
print(s)
cnt=0
for i in range(len(s)):
    a=s[i][1][0]
    b=s[i][1][1]
    c=s[i][0]
    if (st[a]==-1)and(en[b]==-1):
        cnt=cnt+c
        st[a]=0
        en[b]=0
print(cnt)
"""

Submission status: Accepted

Solution code:
n = int(input())

ai = [int(i) for i in input().split()]

ai_li = []

for i in range(n):
    ai_li.append([ai[i],i+1])

ai_li.sort(reverse=True)

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

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

#print(dp)
print(max(dp[n]))

Submission status: Accepted

Solution code:
# import time
# p0 = time.time()

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

#dp[x][y] : x人は Ai*(i-pi),y人は Ai*(pi-i)
#           piは 0,1,2...   piはN-1,N-2,N-3,,
# p1 = time.time()-p0

dp[0][0] = 0
# y = 0
for x in range(1,N+1):
    dp[x][0] = dp[x-1][0]+A[x-1][0]*(A[x-1][1]-x+1)
    # print(x,dp)
# x = 0
for y in range(1,N+1):
    dp[0][y] = dp[0][y-1]+A[y-1][0]*(N-y - A[y-1][1])
    # print(x,dp)

# p2 = time.time()-p0
for x in range(1,N):
    for y in range(1,N+1-x):
        A0 = A[x+y-1][0]
        A1 = A[x+y-1][1]
        dp[x][y] = max(dp[x-1][y] + A0*(A1+1 - x), dp[x][y-1] + A0*(N-y - A1))
# print(dp)

# p3 = time.time()-p0

c = 0
for i in range(N):
    if c < dp[i][N-i]:
        c = dp[i][N-i]
print(c)

# print(p1,p2,p3)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

input()

arr = list(sorted([(v, idx) for idx, v in enumerate(map(int, input().split()))], reverse=True))

d = [[-1 for _ in range(len(arr))] for _ in range(len(arr))]


def dp(l, r, idx):
    if idx == len(arr):
        return 0

    if d[l][r] != -1:
        return d[l][r]

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    d[l][r] = max(left, right)
    return max(left, right)


print(dp(0, len(arr) - 1, 0))

Submission status: Accepted

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

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

for i in range(1,N+1):
    b,a = A[i-1]
    b += 1
    for j in range(i+1):
        c = 0
        if i >= 1 and j >= 1:
            dst = j
            c = max(c,DP[i-1][j-1]+a*abs(b-dst))
        if i != j:
            dst = N - (i - j) + 1
            c = max(c,DP[i-1][j]+a*abs(b-dst))
        DP[i][j] = c

print(max(DP[N]))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = [(int(v), i) for i, v in enumerate(input().split())]
    a.sort(reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = a[0][0] * (n - 1 - a[0][1])
    dp[0][1] = a[0][0] * a[0][1]
    for i, v in enumerate(a[1:]):
        dp[i+1][0] = dp[i][0] + v[0] * abs(n - 1 - (i + 1) - v[1])
        dp[i+1][i+2] = dp[i][i+1] + v[0] * abs(v[1] - (i + 1))
        for j in range(1, i + 2):
            dp[i+1][j] = max(
                dp[i][j] + v[0] * abs(n - 1 - (i + 1) + j - v[1]),
                dp[i][j-1] + v[0] * abs(v[1] - (j - 1)))
    ans = -float('inf')
    for i in dp[n-1]:
        ans = max(ans, i)
    print(ans)


main()

Submission status: Accepted

Solution code:
N, = map(int, input().split())
X = [(i+1, x) for i, x in enumerate(map(int, input().split()))]
dp = [[0]*(N+1) for _ in range(N+1)]
X = sorted(X, key=lambda x:x[1])[::-1]
for i in range(1, N+1):
    ai, a = X[i-1]
    dp[i][0] = dp[i-1][0]+a*abs(ai-(N-i+1))
    for j in range(1, i):
        dp[i][j] = max(dp[i-1][j-1]+a*abs(ai-j), dp[i-1][j]+a*abs(ai-(N-(i-j)+1)))
    dp[i][i] = dp[i-1][i-1]+a*abs(ai-i)
print(max(dp[-1]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
def f(n,a_):
      a=[]
      for i,ai in enumerate(a_):
            a.append([1+i,ai])
      a.sort(key=lambda x:x[1],reverse=True)
      dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
      dp[1,1]=a[0][1]*(n-a[0][0])
      dp[1,0]=a[0][1]*(a[0][0]-1)
      for i in range(2,n+1):#i人目の幼児。a[i-1]
            dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
            dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
            #i人目を左に
            l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
            #i人目を右に
            r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
            dp[i,1:i]=np.maximum(l,r)
      return max(dp[n])

if __name__ == '__main__':
      input = sys.stdin.readline
      n=int(input())
      a_=list(map(int,input().split()))
      print(f(n,a_))

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
import numpy as np
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
dp[1,1]=a[0][1]*(n-a[0][0])
dp[1,0]=a[0][1]*(a[0][0]-1)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
      dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
      #i人目を左に
      l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
      #i人目を右に
      r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
      dp[i,1:i]=np.maximum(l,r)
print(max(dp[n]))

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a_=list(map(int,input().split()))
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=defaultdict(lambda:0)
dp[(0,1)]=max(a[0][1]*(n-a[0][0]),0)
dp[(1,0)]=max(a[0][1]*(a[0][0]-1),0)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      for x in range(i+1):
            y=i-x
            if x==0:
                  dp[(x,y)]=dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1))
            elif y==0:
                  dp[(x,y)]=dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1))
            else:
                  dp[(x,y)]=max(dp[(x-1,y)]+a[i-1][1]*(a[i-1][0]-1-(x-1)),dp[(x,y-1)]+a[i-1][1]*(n-a[i-1][0]-(y-1)))
ans=0
for i in range(n+1):
      ans=max(ans,dp[(i,n-i)])
print(ans)

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    As = isRaw()
    Ais = [(a,i) for i,a in enumerate(As)]
    Ais.sort(reverse=True)
    dp = [[0]*(N+1) for n in range(N+1)]
    for sidx,ai in enumerate(Ais):
        a,i = ai
        sxy = sidx+1
        dp[0][sxy] = dp[0][sxy-1]+ a*(i-sidx)
        dp[sxy][0] = dp[sxy-1][0]+ a*(N-1-sidx -i)
        for x in range(1,sxy):
            c1 = dp[x-1][sxy-x]+ a*(N-x-i)
            c2 = dp[x][sxy-x-1]+ a*(i-(sidx-x))
            dp[x][sidx+1-x] = max(c1,c2)
    return max([dp[n][N-n] for n in range(N+1)])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import math
    
def abs(num):
    if num < 0:
        return -num
    else:
        return num

def abc163e(n, a):
    hap_dict = dict()
    hap_list = []
    for elem in range(n):
        if a[elem] in hap_dict:
            hap_dict[a[elem]].append(elem)
        else:
            tmp_list = [elem]
            hap_dict[a[elem]] = tmp_list
            hap_list.append(a[elem])
    
    hap_list.sort(reverse=True)

    left = 0
    right = n-1

    num = 0
    dp = [[0 for re in range(n+1)] for le in range(n+1)]
    for hap in hap_list:
        pos_list = hap_dict[hap]

        while len(pos_list) != 0:
            tgt = pos_list.pop()

            num += 1

            for left in range(num+1):
                right = num-left
                if left == num: # left end
                    dp[left][right] = dp[left-1][right] + hap * abs(tgt-left+1)
                elif left == 0: # right end
                    dp[left][right] = dp[left][right-1] + hap * abs(n-right-tgt)
                else:
                    left_dp = dp[left-1][right] + hap * abs(tgt-left+1)
                    right_dp = dp[left][right-1] + hap * abs(n-right-tgt)
                    dp[left][right] = max(left_dp, right_dp)
                #print("[",str(left),"][",str(right),"]=",str(dp[left][right]))

    ans_list = []
    for i in range(num+1):
        ans_list.append(dp[i][num-i])
    return max(ans_list)

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    a = list(map(int, input().split(" ")))

    ans = abc163e(n, a)

    # output
    print(ans)
    
# else:
    # do nothing

Submission status: Accepted

Solution code:
N = int(input())
A_list = map(int, input().split())
 
# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)
 
# print(A_list)
 
dp = [[0 for i in range(N+1)] for j in range(N+1)]
# print(dp)
for left in range(0, N):
    for right in range(0, N - left):
        # print(f'left, righte: { left, right }')
        # print(A_list[left + right - 1][0])
        activity = A_list[left + right][0]
        distance_from_left = A_list[left + right][1] - left
        # print(f'distance_from_left: { distance_from_left }')
        distance_from_right = (N - 1 - right) - A_list[left + right][1]
        # print(f'distance_from_right: { distance_from_right }')
        dp[left + 1][right]\
            = max(dp[left + 1][right],
                  dp[left][right] + activity * distance_from_left)
        dp[left][right + 1]\
            = max(dp[left][right + 1],
                  dp[left][right] + activity * distance_from_right)
        # print('dp---')
        # print(dp)
        # print('---dp')
# print(dp)
dp_list = [flatten for inner in dp for flatten in inner]
print(max(dp_list))

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()
 
# 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] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x
 
        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))
 
ans = 0
for i in range(N+1):
    ans = max(ans, DP[i][N-i])
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#import numpy as np
N = int(input())
A = list(map(int,input().split()))
table = []
 
for i, a in enumerate(A):
    table.append([a,i])
table.sort()
dp = [[0for i in range(N+1)]for j in range(N+1)]
for i in range(1,N+1):
    baby,pos = table.pop()
    dp[i][0]=dp[i-1][0]+baby*abs(pos-i+1)
    dp[0][i] = dp[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i-x
        dp[x][y]= max(dp[x-1][y] + baby * abs(pos-x+1),dp[x][y-1] + baby * abs(pos-(N-y)))
print(int(max(dp[k][N-k] for k in range(N+1))))

Submission status: Accepted

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

# aの各要素とインデックスを紐付け
for i in range(n):
    a[i]=[a[i],i]
a.sort(reverse=True)

# dp[i][l]:大きいものからi個位置決めてそのうち左がl（右がi-l）の時のMAX
dp=[[0]*(n+1) for i in range(n+1)]

for i in range(n):
    for j in range(i+1):
        # i番目を左に置く時、左に一つズレる
        dp[i+1][j+1]=dp[i][j]+abs(a[i][1]-j)*a[i][0]
    for j in range(i+1):
        # i番目を右に置く時
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]+abs(a[i][1]-(n-1-(i-j)))*a[i][0])

print(max(dp[-1]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
a = list(map(int, input().split()))
a = [(item, i) for i,item in enumerate(a)]
s = sorted(a)[::-1] # (value, index)
dp = [[None] * (n+1) for _ in range(n+1)] # 高い方からx+y人について、a_i * (p_i - i) + a_i * (i - p_i) の和の最大値

dp[0][0] = 0
tmp = 0
# dp[x][y] : 右にx個、左にy個
for i in range(n):
    val, ind = s[i]
    dp[i+1][0] = dp[i][0] + val * ((n-i-1) - ind)
for i in range(n):
    val, ind = s[i]
    dp[0][i+1] = dp[0][i] + val * (ind - i)

for i in range(2,n+1):
    for x in range(1,i):
        y = i - x
        val, ind = s[i-1]
        v1 = dp[x-1][y] + val * ((n-1 - (x-1)) - ind)
        v2 = dp[x][y-1] + val * (ind - (y-1))
        dp[x][y] = max(v1, v2)
print(max((dp[x][n-x] for x in range(n+1))))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())

AA=[]
for i,val in enumerate(A):
    AA.append((val,i+1))

AA.append((float("inf"),None))  #1-indexedにする
AA.sort(reverse=True)

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

l=0
for l in range(N):
    for r in range(N-l):
        val,idx=AA[l+r+1][0],AA[l+r+1][1]
        dp[l+1][r]=max( dp[l+1][r], dp[l][r]+abs(val*(idx-l-1)) )
        dp[l][r+1]=max( dp[l][r+1], dp[l][r]+abs(val*(N-r-idx)) )

ans=float("-inf")
for l in dp:
    ans=max(ans,max(l))

print ans

Submission status: Accepted

Solution code:
n = int(input())
buf = list(map(int,input().split()))
a = []
for i in range(n):
    a.append([buf[i],i])
a = sorted(a,reverse=True)

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

print(max([max(i) for i in dp]))

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()

# 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] の幼児を移動させる
    baby, pos = table.pop()
    
    DP[i][0] = DP[i-1][0] + baby * abs(pos-i+1)
    DP[0][i] = DP[0][i-1] + baby * abs(pos-(N-i))
    for x in range(1,i):
        y = i - x

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

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