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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 9
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
A = LI()
S = sorted([(A[k], k + 1) for k in range(n)], reverse=True)
ans = 0
dp = [[-INF] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(n):
        if i and i <= S[i + j - 1][1]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + S[i + j - 1][0] * abs(i - S[i + j - 1][1]))
        if j and S[i + j - 1][1] <= n - j + 1:
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + S[i + j - 1][0] * abs(n - j + 1 - S[i + j - 1][1]))
        if i + j == n:
            ans = max(ans, dp[i][j])
            break

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0][0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1)), dp[i + 1, 1:])
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print(dp[-1,].max())

Submission status: Accepted

Solution code:
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()), start=1)]#(Ai,i)を作成 iはスタート位置
A.sort(reverse=True)#Aiが大きい順にソート

dp = [[0] * (N + 1) for _ in range(N + 1)]
#dp[l][r]=l人は左、r人は右に配置した時の最大スコア

for s, (a, i) in enumerate(A):#Ai大きい順にs人動かした場合
    for l in range(s + 1):#0~s人うごかした時を考える s=l+r。
        r = s - l
        L = dp[l][r] + a * (i - (l + 1))
        R = dp[l][r] + a * (N - r - i)

        if dp[l + 1][r] < L:#最大値の更新
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

ans = 0
for i in range(N + 1):#Ansは左にi,右にN-i動かしたときの最大値、の中の最大値
    ans = max(ans, dp[i][N - i])
print(ans)

Submission status: Accepted

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

A =[] 

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


A.sort(key=lambda x: x[1], reverse=True)

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

for i in range(N+1):
  for x in range(i+1):
    y = i - x
    if x == 0 and y == 0:
      dp[x][y] = 0
    
    elif x == 0:
      dp[x][y] = dp[x][y-1] + A[y-1][1]*((N-y+1) - (A[y-1][0]))


    elif y == 0:
      dp[x][y] = dp[x-1][y] + A[x-1][1]*((A[x-1][0]) - x )


    else:
      dp[x][y] = max(dp[x][y-1] + A[x+y-1][1]*((N-y+1) - (A[x+y-1][0])) , dp[x-1][y] + A[x+y-1][1]*((A[x+y-1][0]) - x ))

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

Submission status: Accepted

Solution code:
# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

n,*A = get_all_int()

# dp[i][j] = 活発度高い順のi人目まで処理し、左にjに置いた場合のうれしさの最大
dp = [ [0] * (n+1) for _ in range(n+1) ]

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

for i, t in enumerate(AA):
    # k 移動前の位置
    # a 活発度
    k,a = t
    for j in range(i+1):
        # 左に置く (すでに左端にj人居る)
        move = abs(k - j)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a*move)

        # 右に置く (すでに右端にi-j人居る)
        move = abs(k - (n-(i-j)-1))
        dp[i+1][j] =   max(dp[i+1][j],   dp[i][j] + a*move)

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n,*A = get_all_int()

# dp[i][j] = 活発度高い順のi人目まで処理し、左にjに置いた場合のうれしさの最大
dp = [ [0] * (n+1) for _ in range(n+1) ]

AA = list(enumerate(A))
AA.sort(key=(lambda t: t[1]), reverse=True)

for i, t in enumerate(AA):
    # k 移動前の位置
    # a 活発度
    k,a = t
    for j in range(i+1):
        # 左に置く (すでに左端にj人居る)
        move = abs(k - j)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a*move)

        # 右に置く (すでに右端にi-j人居る)
        move = abs(k - (n-(i-j)-1))
        dp[i+1][j] =   max(dp[i+1][j],   dp[i][j] + a*move)

ans = 0

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

# left = 0
# right = n-1

# AA = list(enumerate(A))
# AA.sort(key=(lambda t: t[1]), reverse=True)
# ans = 0
# for i,a in AA:
#     log(i,a)
#     l = abs(left-i)
#     r = abs(right-i)

#     if l > r:
#         log(f"  {i}->{left}, ", a*l)
#         ans += a * l
#         left += 1
#     else:
#         log(f"  {i}->{right}, ", a*r)
#         ans += a * r
#         right -= 1

print(ans)

Submission status: Accepted

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

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

for s, (a, i) in enumerate(A):
    for l in range(s + 1):
        r = s - l
        L = dp[l][r] + a * (i - (l + 1))
        R = dp[l][r] + a * (N - r - i)

        if dp[l + 1][r] < L:
            dp[l + 1][r] = L
        if dp[l][r + 1] < R:
            dp[l][r + 1] = R

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 = map(int, input().split())

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

C = sorted(B, key=lambda b: b[1], reverse=True)

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

dp[1][0] = (C[0][0] - 0) * C[0][1]
dp[0][1] = ((N - 1) - C[0][0]) * C[0][1]

ans = 0
for i in range(2, N + 1):
    for j in range(0, i + 1):
        t1, t2 = 0, 0

        if j - 1 >= 0:
            t1 = dp[j - 1][i - j] + abs((C[i - 1][0] - (j - 1))) * C[i - 1][1]

        if i - j - 1 >= 0:
            t2 = dp[j][i - j - 1] + abs((C[i - 1][0] - (N - (i - j)))) * C[i - 1][1]

        dp[j][i - j] = max(t1, t2)

        if i == N:
            ans = max(ans, dp[j][i - j])

print(ans)

Submission status: Accepted

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

def student_sorting(N, A):
    student_list = [0] * N

    for initial_pos, activity in enumerate(A):
        student_list[initial_pos] = (activity, initial_pos)

    return sorted(student_list, reverse = True)

def DP(N, student_list):
    DP_map = list(list(0 for row in range(N + 1 - column)) for column in range(N + 1))
    ans_list = []
    ans = 0

    for left in range(N): #初期値設定 right = 0
        activity = student_list[left][0]
        distance_l = abs(left - student_list[left][1])
        DP_map[left + 1][0] = DP_map[left][0] + activity * distance_l

    for right in range(N): #初期値設定 left = 0
        activity = student_list[right][0]
        distance_r = abs((N - 1 - right) - student_list[right][1])
        DP_map[0][right + 1] = DP_map[0][right] + activity * distance_r

    for left in range(1, N + 1):
        for right in range(1, N - left + 1):
            activity = student_list[left + right - 1][0]
            distance_l = abs((left - 1) - student_list[left + right - 1][1])
            distance_r = abs((N - right) - student_list[left + right - 1][1])
            score_if_appended_to_left = DP_map[left - 1][right] + activity * distance_l
            score_if_appended_to_right = DP_map[left][right - 1] + activity * distance_r
            DP_map[left][right] = max(score_if_appended_to_left, score_if_appended_to_right)

    for left in range(N + 1):
        row = N - left
        column = left
        ans_list.append(DP_map[column][row])

    ans = max(ans_list)

    return ans

student_list = student_sorting(N, A)
ans = DP(N, student_list)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted((int(x), k) for k, x in enumerate(input().split()))
opt = [[0 for j in range(n + 1)] for i in range(n + 1)]
for i in reversed(range(n)):
    for j in range(i, n):
        val, k = a[j - i]
        opt[i][j] = max(val * abs(k - i) + opt[i + 1][j], val * abs(k - j) + opt[i][j - 1])
print(opt[0][n - 1])

Submission status: Accepted

Solution code:
def main():
    from operator import itemgetter

    N = int(input())
    a = map(int, input().split())

    *ea, = enumerate(a, 1)

    ea.sort(key=itemgetter(1), reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    # dp[left][right]:=活発な幼児から順に左端からleft,右端からright並べた際の最大うれしさ

    for i, (p, x) in enumerate(ea, 1):
        for left in range(i + 1):
            right = i - left
            if left > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left - 1][right] + x * (p - left)
                )
            if right > 0:
                dp[left][right] = max(
                    dp[left][right],
                    dp[left][right - 1] + x * (N - right + 1 - p)
                )

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    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(key = lambda x: x[0], reverse = True)

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

    for i, b in enumerate(B):
        a = b[0]
        tmp = b[1]
        for x in range(i + 1):
            DP[x + 1][i - x] = max(DP[x + 1][i - x], DP[x][i - x] + a * abs(tmp - x))
            DP[x][i - x + 1] = max(DP[x][i - x + 1], DP[x][i - x] + a * abs((N - tmp - 1) - (i - x)))

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

    print (ans)

    # for tmp in DP:
    #     print (tmp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(s) for s in 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]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr
 
print(max(prev))

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

aa = [[a[i],i] for i in range(n)]

aa.sort(reverse = True)

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

for i in range(1,n+1):
    on = aa[i-1]
    for j in range(i+1):
        if j-1 >= 0:
            dp[i-j][j] = max(dp[i-j][j-1] + on[0] * abs(on[1] - (n-1 - (j - 1))),dp[i-j][j])
            """
            if i == 1:
                print(dp[i-j][j-1] + on[0] * abs(on[1] - j),dp[i-j][j])
            """
        if i-j-1 >= 0:
            #dp[i-j][j] = max(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (n-1 - (i-j))))
            dp[i-j][j] = max(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """
            if i == 1:
                print(on,(n-1 - (i-j)),n-1,i-j)
                print(dp[i-j-1][j],on[0] * abs(on[1] - (n-1 - (i-j))))
                print(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """

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

Submission status: Accepted

Solution code:
n = int(input())
A_l = [(A,i) for i, A in enumerate(map(int,input().split()))]
A_l.sort(reverse=True)

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(n-(j-1) - (i+1))
for k in range(1,n+1): # all go smaller
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1) - (1+(k-1)))

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

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

Submission status: Accepted

Solution code:
def e_active_infants():
    # 参考: https://kmjp.hatenablog.jp/entry/2020/04/20/0900
    N = int(input())
    A = [int(i) for i in input().split()]
    # どこから移動するかの情報が必要なので、付与する
    p = sorted([(a, k) for k, a in enumerate(A)], reverse=True)

    # dp[x][y]: 元の場所から (元の場所を含んで) 左に動いた人数が x 人、
    # 右に動いた人数が y 人のときのうれしさの最大値
    dp = [[-float('inf')] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 0  # 誰も動いていなければうれしさは 0
    for i in range(N):
        a, r = p[i]
        for x in range(i + 1):
            y = i - x
            # 左右の埋まっていない端に動かしたときの場合の遷移
            dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * a)
            dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (N - 1 - y)) * a)
    return max(dp[i][N - i] for i in range(N + 1))

print(e_active_infants())

Submission status: Accepted

Solution code:
# 解説AC
N = int(input())
A = map(int, input().split())

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

children.sort(reverse=True)

# dp[i][j]: うれしさの合計の最大値
# i: 左端の個数
# j: 右端の個数
dp = [[0] * (N + 1) for _ in range(N + 1)]

ans = 0
# 配るDP
for l in range(N):
    for r in range(N):
        if l + r == N:
            ans = max(ans, dp[l][r])
            break
        activeness, idx = children[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] + abs(idx - (N - 1 - r)) * activeness)

print(ans)

Submission status: Accepted

Solution code:
def main():
    from random import sample
    from operator import itemgetter
    e=enumerate
    n,a=open(0)
    n=int(n)
    d=[0]+[-2**64]*n
    for j,(a,i)in e(sorted(sample([(a,i)for i,a in e(map(int,a.split()))],n),key=itemgetter(0),reverse=1)):
        d=[max(t+a*(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
    print(max(d))
main()

Submission status: Accepted

Solution code:
N = int(input())

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

prev = [0]
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a

  prev = curr

print(max(prev))

Submission status: Accepted

Solution code:
def main():
	n, *a = map(int, open(0).read().split())
	dp = [[0] * (n + 1) for _ in range(n + 1)]
	for t, (c, k) in enumerate(sorted((c, k) for k, c in enumerate(a))[::-1]):
		for i in range(t + 1):
			j = t - i
			if dp[i + 1][j] <= (s := dp[i][j] + c * abs(i - k)): dp[i + 1][j] = s
			if dp[i][j + 1] <= (s := dp[i][j] + c * abs(n - 1 - k - j)): dp[i][j + 1] = s
	print(max(dp[i][~i] for i in range(n + 1)))

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import *
from itertools import *

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)

prev = [0]
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    r = k-l
    if prev[l] + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], prev[l]+abs(N-i-r)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev)

print(prev_max)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
dp=[[0]*(n+1)for _ in range(n+1)]
for t,(c,k) in enumerate(sorted((c,k) for k,c in enumerate(a))[::-1]):
	for i in range(t+1):
		j=t-i
		if dp[i+1][j]<dp[i][j]+c*abs(i-k):dp[i+1][j]=dp[i][j]+c*abs(i-k)
		if dp[i][j+1]<dp[i][j]+c*abs(n-1-k-j):dp[i][j+1]=dp[i][j]+c*abs(n-1-k-j)
print(max(dp[i][~i]for i in range(n+1)))

Submission status: Accepted

Solution code:
from collections import *
from itertools import *

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)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  for l, p in prev.items():
    r = k-l
    if p + SB - max(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev.values())

print(prev_max)

Submission status: Accepted

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

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

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

b = []
for i in range(n):
    b.append(a[i]*n + i)
b.sort(reverse = True)

for i in range(n+1):
    for j in range(n+1-i):
        val,idx = divmod(b[i+j-1],n)
        if i > 0:
            dp[i][j] = max(dp[i][j],dp[i-1][j] + val*abs(idx-i+1))
        if j > 0:
            dp[i][j] = max(dp[i][j],dp[i][j-1] + val*abs(idx-n+j))

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

Submission status: Accepted

Solution code:
from collections import *
from itertools import *

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)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - max(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *

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)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  curr_max = 0
  for l, p in prev.items():
    r = k-l
    if p + SB - min(l,r)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
    curr_max = max(curr_max, curr[l], curr[l+1])
  SA -= a
  SB -= b
  prev = curr
  prev_max = curr_max

print(curr_max)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = [(i, j) for (i, j) in zip(LI(), range(n))]
    a.sort(reverse=True)
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(n):
        dp[i + 1][0] = dp[i][0] + a[i][0] * abs(a[i][1] - i)
        dp[0][i + 1] = dp[0][i] + a[i][0] * abs(a[i][1] - (n - (i + 1)))
        for l in range(1, i + 1):
            r = i - l + 1
            dp[l][r] = max(dp[l - 1][r] + a[i][0] * abs(a[i][1] - (l - 1)),
                            dp[l][r - 1] + a[i][0] * abs(a[i][1] - (n - r)))
    ans = 0
    for r in range(n + 1):
        l = n - r
        ans = max(ans, dp[l][r])
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = [(int(x), i) for i, x in enumerate(input().split())]
a.sort(reverse=True)
aval, ai = zip(*a)
dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(n):
    for r in range(n):
        if l + r >= n: break
        dp[l+1][r] = max(dp[l+1][r], dp[l][r] + aval[l+r] * abs(ai[l+r]-l))
        dp[l][r+1] = max(dp[l][r+1], dp[l][r] + aval[l+r] * abs(ai[l+r]-(n-r-1)))

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

Submission status: Accepted

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

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

for n in range(0,N+1):
    for y in range(0,n+1):
        x = n-y
        a = A[n-1]
        ind = a[1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+a[0]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+a[0]*abs(ind-(x-1)),dp[x][y-1] + a[0]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

print(ans)

Submission status: Accepted

Solution code:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
import numpy as np


sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    arr = sorted(enumerate(map(int, input().split()), 1),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros(n+1, dtype=np.int)

    for k, (i, a) in enumerate(arr, 1):
        ndp = dp.copy()
        
        add_left = np.abs(np.arange(1, k+1) - i) * a
        ndp[1:k+1] = np.maximum(ndp[1:k+1], dp[:k] + add_left)
        
        add_right = np.abs(np.arange(n-k+1, n+1) - i) * a
        ndp[:k] = np.maximum(ndp[:k], dp[:k] + add_right)

        dp = ndp

    print(dp.max())

Submission status: Accepted

Solution code:
#pythonじゃ通らなかった…(´・ω・`)
n = int(input())
a = list(map(int,input().split()))
ans = [[0 for i in range(n+1)] for j in range(n+1)]
p = []

#それぞれの活発度と元々居た位置の記録
for i in range(n):
    p.append([a[i],i])
p.sort(reverse=True)

#活発度の高い順にそれぞれ左と右から詰めて並べていく時のうれしさの変化
for i in range(1,n+1):
    ans[0][i] = ans[0][i-1] + p[i-1][0]*abs(p[i-1][1]-i+1)
for i in range(1,n+1):
    ans[i][0] = ans[i-1][0] + p[i-1][0]*abs(n-i-p[i-1][1])

#Douteki Planning 活発度の高い順に左にi人、右にj人詰めて並べていった時の最大値
for i in range(1,n):
    for j in range(1,n-i+1):
        ans[i][j] = max(ans[i][j-1] + p[i+j -1][0]*abs(p[i+j -1][1]-j+1),
        ans[i-1][j] + p[i+j - 1][0]*abs(n-i-p[i+j-1][1]))

#全て詰め並べ終わったときのうれしさの最大値(=答え)を探す
ma = 0
for i in range(n):
    ma = max(ma,ans[0+i][n-i])
print(ma)

Submission status: Accepted

Solution code:
n = int(input())
a_ = [int(i) for i in input().split()]
a = [[a_[i], i+1] for i in range(n)]
a.sort(reverse=True)

dp = [[0 for i in range(n+1)] for j in range(n+1)]
ans = 0
for x_plus_y in range(n):
    for x in range(x_plus_y + 1): #x：左に詰めた個数
        y = x_plus_y - x #y：# 右に詰めた個数
        dp[x][y+1] = max(dp[x][y+1], a[x_plus_y][0] * abs((n - y) - a[x_plus_y][1]) + dp[x][y]) #右
        dp[x+1][y] = max(dp[x+1][y], a[x_plus_y][0] * abs((a[x_plus_y][1] - (1+x))) + dp[x][y]) #左

        if x_plus_y == n-1:
            ans = max(ans, dp[x][y+1], dp[x+1][y])

print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
b = [(a[i],i) for i in range(n)]
b.sort(reverse=True)
ddprint(b)
d = [[0]*(n+1) for i in range(n+1)]
for i in range(n):
    v,j = b[i]
    ddprint(f"i {i} v {v} j {j}")
    d[i+1][0] = d[i][0] + v*abs(n-1-i-j) # all to right
    d[i+1][i+1] = d[i][i] + v*abs(j-i) # all to left
    for k in range(1,i+1):
        v1 = d[i][k-1]+v*abs(j-k+1)  # k-1 infants on left
        v2 =  d[i][k]+v*abs(n-1-i+k-j) # i-k infants on right
        ddprint(f"k {k} v1 {v1} v2 {v2} d1 {d[i][k-1]} d0 {d[i][k]} x1 {k-i} x2 {n-1-i+k-j}")
        d[i+1][k] = max(v1,v2)
    if DBG:
        ddprint(i)
        ddprint(d[i+1])
print(max(d[n]))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))

L = list(range(N))
L.sort(key = lambda x: A[x], reverse = True)

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

for s in range(N):
    l = L[s]
    a = A[l]
    for i in range(s+1):
        j = s-i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j]+a*abs(l-i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j]+a*abs(l-(N-s+i-1)))
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 = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
ans = 0
for L in range(n+1):
    for R in range(n+1):
        if n <= L+R-1:
            continue
        a, i = A[L+R-1]
        if 0 <= R-1:
            dp[L][R] = max(dp[L][R], dp[L][R-1]+abs((n-R)-i)*a)
        if 0 <= L-1:
            dp[L][R] = max(dp[L][R], dp[L-1][R]+abs(i-(L-1))*a)
        ans = max(ans, dp[L][R])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    dp = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(i+1):
            x,y = j,i-j
            dp[x+1][y] = max(dp[x+1][y],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-x)))
            dp[x][y+1] = max(dp[x][y+1],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-(N-y-1))))

    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:
import sys
readline = sys.stdin.buffer.readline

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(n + 1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = dp.copy()

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    dp_new[1:k+1] = np.maximum(dp_new[1:k+1], dp[:k] + add_left)

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    dp_new[:k] = np.maximum(dp_new[:k], dp[:k] + add_right)

    dp = dp_new

ans = dp.max()
print(ans)

Submission status: Accepted

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

import numpy as np

n = int(readline())
a = np.array(readline().split(), np.int64)

ai = np.argsort(a)[::-1]
a = a[ai]
ai += 1

dp = np.zeros(1, np.int64)
for k, (i, e) in enumerate(zip(ai, a), 1):
    dp_new = np.append(dp, 0)

    add_left = e * np.abs(np.arange(1, k + 1) - i)
    np.maximum(dp_new[1:k+1], dp[:k] + add_left, out=dp_new[1:k+1])

    add_right = e * np.abs(np.arange(n - k + 1, n + 1) - i)
    np.maximum(dp_new[:k], dp[:k] + add_right, out=dp_new[:k])

    dp = dp_new

ans = dp.max()
print(ans)