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:
INF=float('inf')

N=int(input())
arr=list(map(int,input().split()))
A=[]
for i in range(N):
    A.append((arr[i],i))
A.sort(key=lambda x:x[0],reverse=True)
dp=[[-INF]*(N+1) for i in range(N+1)]
dp[0][0]=0

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

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(i)):
        dp[j+1] = max(dp[j] + a*(x-j), dp[j+1])
        dp[j] += a*(N-(i-j)-x)
print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        res1 = dp[j-1]+a*(x-(j-1))*(j-1>=0)
        res2 = dp[j]+a*(N-(i-j)-x)*(j<=i-1)
        if res1>=res2: dp[j] = res1
        else: dp[j] = res2
print(max(dp))

Submission status: Accepted

Solution code:
def max2(x,y):
    return x if x > y else y
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max2((dp[j-1]+a*(x-(j-1)))*(j-1>=0), (dp[j]+a*(N-(i-j)-x))*(j<=i-1))
print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max((dp[j-1]+a*(x-(j-1)))*(j-1>=0), (dp[j]+a*(N-(i-j)-x))*(j<=i-1))
print(max(dp))

Submission status: Accepted

Solution code:
N = int(input())
D = []
for i, a in enumerate(map(int, input().split())):
    D.append((a<<11) + i)
D.sort(reverse=True)
dp = [0]*(N+1)
for i, d in enumerate(D,start=1):
    x, a = d%(1<<11),d>>11
    for j in reversed(range(0, i+1)):
        dp[j] = max((dp[j-1]+a*abs(x-(j-1)))*(j-1>=0), (dp[j]+a*abs(N-(i-j)-x))*(j<=i-1))
print(max(dp))

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:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, A):
    # dp[n][k] := n 人目まで見て左に k 人送ったときの最大値
    A_order = np.argsort(-A)
    dp = np.zeros((N+2, N+2), dtype=np.int64)
    for n in range(1, N+1):
        idx_A = A_order[n-1]
        a = A[idx_A]
        for k in range(n+1):
            dp[n, k] = max(
                dp[n-1, k-1] + a * abs(idx_A-(k-1)) if k>0 else 0,  # 左に送る
                dp[n-1, k] + a * abs(idx_A-(N-n+k)) if k<n else 0,  # 右に送る
            )
    return dp[N].max()

numba_compile([
    [solve, "i8(i8,i8[:])"],
])

N = int(input())
A = np.array(input().split(), dtype=np.int64)
ans = solve(N, A)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
A_tup = [(0, 0)] * N
for i in range(N):
    A_tup[i] = (A[i], i)
A_tup.sort(reverse=True)

dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    pi = A_tup[i][1]
    for j in range(i + 1):
        k = i - j
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (pi - j) * A_tup[i][0])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (N - k - 1 - pi) * A_tup[i][0])

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

Submission status: Accepted

Solution code:

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

    # dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i, (a, p) in enumerate(A):
        for j in range(i + 1):
            # 左に詰める場合
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)
            # 右に詰める場合
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)

    print(max(dp[-1]))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    A = read_ints()
    dp = [
        [0]*(N+1) for _ in range(N+1)
    ]
    AI = sorted(((a, i) for i, a in enumerate(A)), reverse=True)
    for i, (a, ix) in enumerate(AI):
        # dp[x][y] = max(dp[x-1][y]+A[x+y]*x, dp[x][y-1]+A[x+y]*y)
        # add a to the left
        for x in range(i+2):
            y = i+1-x
            if y > 0:
                dp[x][y] = max(dp[x][y], dp[x][y-1]+a*abs(N-y-ix))
            if x > 0:
                dp[x][y] = max(dp[x][y], dp[x-1][y]+a*abs(ix-x+1))
    return max(dp[i][N-i] for i in range(N+1))

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

p = list(range(n))
p.sort(key=lambda i: a[i])

dp = [0] * (n + 1)

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

print(dp[0])

Submission status: Accepted

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit

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

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

    #dp = np.zeros((N+1,N+1), dtype='int64')
    dp = [[0]*(N+1-i) for i in range(N+1)]

    m = 0
    for i in range(1,len(A)+1):
        index,a = A[i-1]
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (N-j-index)*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (N-j-index)*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)
            if i == len(A):
                m = max(m, dp[i-j][j])

    #print(dp)
    #print(np.max(dp))
    print(m)

main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    
    #でかいやつから左右両端のどちらかに動かす
    B=sorted(zip(A,range(N)),reverse=True)
    
    #dp[i][j]は左からi個右からj個埋まっている時の最大値
    dp=[[0]*(N+1) for _ in range(N+1)]
    
    for k in range(N):
        a=B[k][0]
        x=B[k][1]
        
        for i in range(k+1):
            j=k-i
            #右詰
            y=N-j-1
            dp[i][j+1]=max(dp[i][j+1],dp[i][j]+a*abs(x-y))
            
            #左詰
            y=i
            dp[i+1][j]=max(dp[i+1][j], dp[i][j]+a*abs(x-y))
                
    ans=0
    for i in range(N+1):
        ans=max(ans,dp[i][N-i])
    print(ans)
        
    
    

        
        
        

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(num,i) for i,num in enumerate(a)]
a.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(n-i+1):
        if i>0:
            dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i+j-1][0]*abs(a[i+j-1][1]-(i-1)))
        if j>0:
            dp[i][j] = max(dp[i][j], dp[i][j-1] + a[i+j-1][0]*abs(a[i+j-1][1]-(n-j)))
ans = max(dp[i][n-i] for i in range(n+1))
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = sorted([(v, i) for i, v in enumerate(list(map(int, input().split())))])[::-1]

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

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

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[i][j]:(大きい順で)i番目まで見て、左に寄せたのがj個である場合の最大値

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:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

A = [(A[i], i) for i in range(N)]
A_sort = sorted(A,reverse = True)

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N):
    dp_new = [-float('inf')]*(N+1)
    pi = A_sort[i][1]  #もともといた場所
    for l in range(i+1): 
        r = i - l   #右を選んだ回数
        dp_new[l+1] = max(dp_new[l+1],dp[l] + A_sort[i][0] * (pi-l)) 
        dp_new[l] = max(dp_new[l],dp[l] + A_sort[i][0] * ((N-r-1)-pi))
    dp = dp_new
print(max(dp))

Submission status: Accepted

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

a_val_ind_l = []
for i, a in enumerate(al):
    a_val_ind_l.append((a,i))

a_val_ind_l.sort(reverse=True)
dp = [[0]*(n+1) for _ in range(n+1)]


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


ans = 0
for row in dp:
    row_max = max(row)
    ans = max(row_max, ans)

print(ans)

Submission status: Accepted

Solution code:

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

    # dp[i][j] := A が大きい順に i + j 個について、i 個を左詰めして、j 個を右詰めしたときのスコア
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        j = 0
        while i+j < N:
            a, idx = A[i+j]
            # 左に詰める場合
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (idx - i) * a)
            # 右に詰める場合
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + ((N-1-j) - idx) * a)
            j += 1
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i][N-i])
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i]=(a[i],i)
b=sorted(a,reverse=True)
dp=[[-10**14 for i in range(n+1)] for j in range(n+1)]
dp[0][0]=0
for i in range(1,n+1):
    see=b[i-1][0]
    prv=b[i-1][1]
    for j in range(i+1):
        dp[j][i-j]=max(dp[j-1][i-j]+abs(prv-(j-1))*see,dp[j][i-j-1]+abs(n-i+j-prv)*see)
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Submission status: Accepted

Solution code:
def main():
    from operator import itemgetter
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

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

    AP = []
    for i in range(N):
        AP.append((A[i], i))
    AP.sort(key=itemgetter(0), reverse=True)

    # dp[i][l][r]
    # 大きい方からi個まで左右を決めて
    # 左をl回、右をr回使ったときの最大値
    # r = i - l
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        ai, pi = AP[i]
        for l in range(i+1):
            r = i - l
            # 左
            if dp[i+1][l+1] < dp[i][l] + (pi-l)*ai:
                dp[i+1][l+1] = dp[i][l] + (pi-l)*ai
            # 右
            if dp[i+1][l] < dp[i][l] + ((N-r-1)-pi)*ai:
                dp[i+1][l] = dp[i][l] + ((N-r-1)-pi)*ai

    print(max(dp[N]))

main()

Submission status: Accepted

Solution code:
# E - Active Infants
N = int(input())
A = list(map(int,input().split()))
dp = [[] for _ in range(N+1)]
dp[0].append(0)
for i in range(N):
    A[i] = [A[i],i+1]
A.sort(reverse=True)
for M in range(1,N+1):
    Ai,i = A[M-1]
    # x=0
    dp[M].append(dp[M-1][0]+Ai*(N-(M-1)-i))
    # 1<=x<=M-1
    for x in range(1,M):
        dp[M].append(max(dp[M-1][x-1]+Ai*(i-x),dp[M-1][x]+Ai*(N-(M-x-1)-i)))
    # x=M
    dp[M].append(dp[M-1][M-1]+Ai*(i-M))
print(max(dp[N]))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    anumlist = []
    for i in range(n):
        anumlist.append([a[i], i])
    anumlist.sort(reverse = True)
    dp = [[0] * (n + 1) for i 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] + anumlist[i + j][0] * (anumlist[i + j][1] - i))
            dp[i][j + 1] = max(dp[i][j+1],dp[i][j] + anumlist[i + j][0] * ((n - 1 - j) - anumlist[i + j][1]))
            
    ans = 0
    for i in range(n+1):
        ans = max(ans, dp[i][n - i])
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
import itertools


def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = [(A[i], i) for i in range(N)]
    X.sort(reverse=True)
    l = 0
    r = N-1
    ans = 0
    dp = [[0] * (i+1) for i in range(N+1)]
    for i in range(N):
        cost, prev = X[i]
        dp[i+1][0] = dp[i][0] + cost * abs(prev - (N - 1 - i))
        dp[i+1][i+1] = dp[i][i] + cost * abs(prev - i)
        for j in range(1, i+1):
            pos1 = N - 1 - i + j
            pos2 = j - 1
            dp[i+1][j] = max(dp[i][j] + cost * abs(prev - pos1),
                             dp[i][j-1] + cost * abs(prev - pos2))
    print(max(dp[N]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

# dp[n][k]: nは現在使っている個数、kは左から詰めた個数
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

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

for i in range(N):
    pi = p[i][1]

    for l in range(i + 1):
        # add to left
        dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + (pi - l) * A[pi])

        r = i - l
        # add to right
        dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + ((N - r - 1) - pi) * A[pi])

print(max(dp[N]))

Submission status: Accepted

Solution code:
import sys
import time

t = time.time()

n = int(input())
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))
# print(time.time()-t)

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print(dfs(0, n-1))

Submission status: Accepted

Solution code:
import heapq
import time
st = time.time()
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))
dp = [[0 for i in range(j+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*(n-1-hi)
dp[1][1] = -ai*hi
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(n-i-hi)
    dp[i][i] = dp[i-1][i-1] - ai*abs(hi-i+1)
    for j in range(1,i):
        dp[i][j] = max(dp[i-1][j-1]-ai*abs(hi-j+1),dp[i-1][j]-ai*abs(n-i+j-hi))

print(max(dp[n]))

Submission status: Accepted

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

L=[[10**10,0]]
for i in range(N):
    L.append([A[i],i])
L.sort(reverse=True)
#print(L)
DP=[[0 for i in range(N+1)]for j in range(N+1)]
#j=右に押し込んだ数
for i in range(1,N+1):
    for j in range(i+1):
        if j==0:
            DP[i][j]=DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1)))
        elif j==i:
            DP[i][j]=DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j))
            #print(DP,DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
        else:
            DP[i][j]=max(DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
            #print(DP,DP[i-1][j]+L[i][0]*abs(L[i][1]-(i-1-j)),DP[i-1][j-1]+L[i][0]*abs(L[i][1]-(N-j)))
print(max(DP[-1]))

Submission status: Accepted

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


V = [0]

for i in range(N-1):
    a, p = A[i]
    s = i+1
    V2 = [None]*(s+1)

    for t in range(s+1):
        v = 0

        if t > 0:
            v = V[t-1] + a*abs(p-(t-1))

        if t < s:
            v = max(V[t] + a*abs(p-(N-s+t)), v)

        V2[t] = v

    V = V2

a, p = A[-1]
for i in range(N):
    V[i] += a*abs(p-i)

print(max(V))

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
a = []
for i in range(len(A)):
    a.append([A[i], i])
a.sort(key = lambda x: x[0], reverse = True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for l in range(i+1):
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + a[i][0]*(n-1-(i-l)-a[i][1]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + a[i][0] * (a[i][1] - l))
ans = 0
for now in dp[n]:
    ans = max(now, ans)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [[-1 for _ in range(N + 1)] for _ in range(N + 1)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if dp[i][l] != -1:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print(search(0, 0))

Submission status: Accepted

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

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

    A = list(enumerate(A))
    A.sort(key=lambda x: x[1])
    ans = 0
    for z in range(1, N+1):
        tmp = A.pop()
        i = tmp[0]+1
        a = tmp[1]
        for x in range(z+1):
            y = z - x
            if x == 0:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y])
            elif y == 0:
                dp[x][y] = max(dp[x-1][y]+a*abs(i-x), dp[x][y])
            else:
                dp[x][y] = max(dp[x][y-1]+a*abs(i-(N-y+1)), dp[x][y], dp[x-1][y]+a*abs(i-x))
            ans = max(ans, dp[x][y])
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        a = sortedA[i][0]
        idx = sortedA[i][1]
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+a*abs((N-r-1)-idx))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+a*abs(l-idx))
    print(max(dp[N]))

main()

Submission status: Accepted

Solution code:
n=int(input())
a_=list(map(int,input().split()))
a=[[i+1,ai] for i,ai in enumerate(a_)]
a.sort(key=lambda x:x[1],reverse=True)
dp=[[0]*(n+1) for _ in range(n+1)]
# dp[i][j]:大きい順にi+j人のうち、i人を左に、j人を右に移した時の最大値。
dp[1][0]=a[0][1]*abs(a[0][0]-1)
dp[0][1]=a[0][1]*abs(a[0][0]-n)
for k in range(2,n+1):
    for i in range(k+1):
        j=k-i
        if j==0:
            dp[i][j]=dp[i-1][j]+a[i+j-1][1]*abs(a[i+j-1][0]-i)
        elif i==0:
            dp[i][j]=dp[i][j-1]+a[i+j-1][1]*abs(n-a[i+j-1][0]-j+1)
        else:
            dp[i][j]=max(dp[i-1][j]+a[i+j-1][1]*abs(a[i+j-1][0]-i),dp[i][j-1]+a[i+j-1][1]*abs(n-a[i+j-1][0]-j+1))
ans=0
for i in range(n+1):
    ans=max(dp[i][n-i],ans)
print(ans)

Submission status: Accepted

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

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [(a, i+1) for i, a in enumerate(A)]
  L.sort(reverse=True)
  dp = [[-1]*(n+1) for _ in range(n+1)]
  dp[0][0] = 0
  ans = 0
  for i in range(n+1):
    for j in range(n+1-i):
      a, idx = L[i+j-1]
      if i:
        dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
      if j:
        dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
      if i+j == n:
        ans = max(ans, dp[i][j])
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Accepted

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

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [(a, i+1) for i, a in enumerate(A)]
  L.sort(reverse=True)
  dp = [[-1]*(n+1) for _ in range(n+1)]
  dp[0][0] = 0
  for i in range(n+1):
    for j in range(n+1-i):
      a, idx = L[i+j-1]
      if i:
        dp[i][j] = max(dp[i][j], dp[i-1][j]+a*(idx-i))
      if j:
        dp[i][j] = max(dp[i][j], dp[i][j-1]+a*(n+1-j-idx))
  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:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    A_=[]
    for i in range(n):
        A_.append([A[i],i])
    A_sorted=sorted(A_)[::-1]
    dp=[[0]*(n+1) for _ in range(n+1)]
    ans=0
    for xy in range(1,n+1):
        for x in range(xy+1):
            m=-float("INF")
            a=A_sorted[xy-1][0]
            a_i=A_sorted[xy-1][1]
            if x!=0 and x<=a_i+1:
                m=max(m,dp[x-1][xy-x]+a*(a_i+1-x))
            if x!=xy and n-xy+x>=a_i:
                m=max(m,dp[x][xy-x-1]+a*(n-xy+x-a_i))
            dp[x][xy-x]=m
            if xy==n:
                ans=max(ans,m)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    l = []
    for i in range(n):
        l.append([a[i], i])
    l.sort(reverse=True)
    dp = [[0]*(n+1) for _ in range(n)]
    for i in range(n):
        if i == 0:
            dp[i][0] = l[i][0] * (n-1-l[i][1])
            dp[i][1] = l[i][0] * l[i][1]
        else:
            for j in range(n, -1, -1):
                if dp[i-1][j] > 0:
                    dp[i][j+1] = max(dp[i][j+1], dp[i-1][j] + l[i][0] * abs(j-l[i][1]))
                    dp[i][j] = max(dp[i][j], dp[i-1][j] + l[i][0] * abs(n-i+j-1-l[i][1]))
    print(max(dp[-1]))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class Solver:

    def __init__(self, n, students):
        self.n = n
        self.students = students
        self.ordered = self.make_ordered() # var[i] = (active, pos), dec ordered
        self.dp = self.make_dp_container() # var[l][r] = max ans

    def make_ordered(self):
        ordered = [None] * self.n
        for i, active in enumerate(self.students):
            pos = i
            #pos = i + 1
            ordered[i] = (active, pos)
        ordered = sorted(ordered, key=lambda tpl: tpl[0])
        ordered = list(reversed(ordered))
        return ordered

    def make_dp_container(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [0] * (self.n + 1)
        return dp

    def run(self):
        for s, (active, pos) in enumerate(self.ordered):
            for l in range(s + 1):
                v = active * abs(pos - l)
                self.update(s + 1, l + 1, self.dp[s][l] + v)
                r = s - l
                r_key = self.n - 1 - r
                v = active * abs(pos - r_key)
                self.update(s + 1, l, self.dp[s][l] + v)
        #print('self.dp') # debug
        #print(self.dp) # debug
        ans = max(self.dp[-1])
        return ans

    def update(self, s, l, value):
        self.dp[s][l] = max(self.dp[s][l], value)


if __name__ == '__main__':
    n = int(input())
    students = list(map(int, input().split()))
    ans = Solver(n, students).run()
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
from sys import stdin


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

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

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

    ans = 0

    for i in range(n + 1):
        for j in range(n + 1 - i):
            s1 = s2 = 0
            if i > 0:
                s1 = dp[i - 1][j] + a2[i + j - 1][0] * (a2[i + j - 1][1] - (i - 1))
            if j > 0:
                s2 = dp[i][j - 1] + a2[i + j - 1][0] * ((n - j) - a2[i + j - 1][1])
            dp[i][j] = max(s1, s2)
        ans = max(ans, dp[i][n - i])

    print(ans)


if __name__ == "__main__":
    main()