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 heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(reverse=True)
dp=[[0 for i in range(N+1)] for _ in range(N+1)]
for n in range(N):
    a,p=A[n]
    for x in range(1,n+2):
        y=n+1-x
        dp[x][y]=max(dp[x][y],dp[x-1][y]+round(abs(x-1 - p))*a)
    for y in range(1,n+2):
        x=n+1-y
        dp[x][y]=max(dp[x][y],dp[x][y-1]+round(abs(N-y - p))*a)
    #print(dp)
print(max([dp[x][y] for x in range(N+1) for y in range(N+1) if x+y==N]))

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 * 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 * abs(np.arange(n - k + 1, n + 1) - i)
    dp_new[:k] = np.maximum(dp_new[:k], dp[:k] + add_right)

    dp = dp_new.copy()

ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

def main():
    n = int(input())
    a = sorted(enumerate(map(int, input().split())), key=itemgetter(1), reverse=True)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for x in range(n):
        for y in range(n - x):
            i, ai = a[x + y]
            dp[x + 1][y] = max(ai * (i - x) + dp[x][y], dp[x + 1][y])
            dp[x][y + 1] = max(ai * (n - 1 - y - i) + dp[x][y], dp[x][y + 1])
    print(max(dp[i][n - i] for i in range(n)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	al = list(IN())
	#b , c = IN()
	#s = input()
	tl=[(v,i+1) for i,v in enumerate(al)]
	tl.sort(reverse=True)
	#print(tl)
	th = lambda f,t:100000*f + t
	fh = lambda hv : (hv//100000, hv%100000)
	
	ss = th(1,n)
	dd={ss:0}
	for uresisa, pos in tl:
		ndd={}
		for dk in dd:
			pu=dd[dk]
			f, t =fh(dk)
			temp_dkf = uresisa*abs(f-pos)+pu
			h=th(f+1, t)
			if h not in ndd:
				ndd[h] = temp_dkf
			else:
				ndd[h] = max(ndd[h], temp_dkf)
			
			temp_dkt = uresisa*abs(t-pos)+pu
			h=th(f, t-1)
			if h not in ndd:
				ndd[h]=temp_dkt
			else:
				ndd[h]=max(ndd[h], temp_dkt)
		else:
			dd=ndd
			#for d in dd:
			#	print(d, dd[d])
			
	rr=0
	for d in dd:
		rr=max(rr, dd[d])
	return rr
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
readline = sys.stdin.readline

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

inds = [v[1] for v in sorted([(a, i) for i, a in enumerate(A)], reverse=True)]

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

for y in range(N + 1):
    for x in range(N - y + 1):
        if x == 0 and y == 0:
            continue
        
        t = inds[x + y - 1]
        if y == 0:
            dp[y][x] = dp[y][x - 1] + A[t] * (t - (x - 1))
        elif x == 0:
            dp[y][x] = dp[y - 1][x] + A[t] * ((N - y) - t)
        else:
            dp[y][x] = max(dp[y][x - 1] + A[t] * (t - (x - 1)),
                dp[y - 1][x] + A[t] * ((N - y) - t))

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    AI = [(a, i) for i, a in enumerate(A)]
    AI.sort(reverse = 1)
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for l in range(n):
        for r in range(n):
            if l + r >= n:
                break
            a, i = AI[l + r]
            dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(i - l) * a)
            dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + abs((n - r - 1) - i) * a)
    print(max(dp[i][n - i] for i in range(n)))
resolve()

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-2**64]*n
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

Submission status: Accepted

Solution code:
n=int(input())
d=[0]+[-10**18]*n
for j,(a,i)in enumerate(sorted((-a,i)for i,a in enumerate(map(int,input().split())))):
    d=[max(t-a*abs(~i-j+k+n),d[k-1]-a*abs(~i+k))for k,t in enumerate(d)]
print(max(d))

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-1e18]*n
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[max(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
print(max(d))

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)
 
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
 
  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)
 
main()

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-1e18]*n
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[max(t+a*abs(~i-j+k+n),k and d[k-1]+a*abs(~i+k))for k,t in e(d)]
print(max(d))

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-9e18]*n
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[max(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k)if k else 0)for k,t in e(d)]
print(max(d))

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = np.array(read().split(), np.int64)
I = np.argsort(A)[::-1].tolist()
A = A[I].tolist()

dp = np.zeros(1, np.int64)

for n, (i, x) in enumerate(zip(I, A)):
    newdp = np.zeros(len(dp) + 1, np.int64)
    left_ind = np.arange(len(dp))
    right_ind = N - 1 - n + left_ind
    left_cost = x * np.abs(left_ind - i)
    right_cost = x * np.abs(right_ind - i)
    np.maximum(newdp[:-1], dp + right_cost, out=newdp[:-1])
    np.maximum(newdp[1:], dp + left_cost, out=newdp[1:])
    dp = newdp

print(dp.max())

Submission status: Accepted

Solution code:
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
def inpl_str():
    '''
    一行に複数の文字
    '''
    return list(input().split())

n=inp()
a = inpl()
sorted_a = sorted(a,reverse=True)
place=dict()
for i in range(n):
    if a[i] not in place:
        place[a[i]]=[i+1]
    else:
        place[a[i]].append(i+1)
ans = 0
dp=[[-INF]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    if i!=0 and sorted_a[i] == sorted_a[i - 1]:
        index += 1
    else:
        index = 0
    for j in range(n):
        _place = place[sorted_a[i]][index]
        #右
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + sorted_a[i] * abs(n - (i - j) - _place))
        #左
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + sorted_a[i] *  abs(_place - j - 1))

print(max(dp[n]))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [1, 3, 4, 2]
# n = 6
# A = [5, 5, 6, 1, 1, 1]
# n = 6
# A = [8, 6, 9, 1, 2, 1]
# n = 2000
# A = [10**9]*n
A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[None for r in range(n+1)] for l in range(n+1)]


def dp(l, r):
    if l == r:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    a, i = A[n-(r-l)]
    x = dp(l+1, r)+a*abs(i-l)
    y = dp(l, r-1)+a*abs(i-r+1)
    DP[l][r] = max(x, y)
    return DP[l][r]


print(dp(0, n))

Submission status: Accepted

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

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

lis = sorted(org, key=lambda x: x[1], reverse=True)

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


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

ans = 0
for i in range(n):
    for j in range(n):
        ans = max(ans, dp[i][j])
        
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)]
for i, (v, p) in enumerate(a):
    # 前にj人いる
    dp[i+1][0] = dp[i][0] + v*abs((n-1 - i) - p)
    for j in range(1, i+1):
        dp[i+1][j] = max(dp[i][j] + v*abs((n-1 - (i-j)) - p),
                         dp[i][j-1] + v*abs((j-1) - p))
    dp[i+1][i+1] = dp[i][i] + v*abs(i - p)
print(max(dp[n]))

Submission status: Accepted

Solution code:
def solve():
        
    N = int(input())
    A = [(a, i+1) for i, a in enumerate(map(int, input().split()))]

    A.sort(reverse=True)
    INF = float('inf')
    dp = [[-INF] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0

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

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

    print(ans)
solve()

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

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

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[d[0]+a*(~i-j+n)]+[max(d[k+1]+a*(n+k-i-j),t+a*abs(i-k))for k,t in e(d[:j])]+[d[j]+a*abs(i-j)]
print(max(d))

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1] #←
    a=As[i] #←この２行でメモリアクセス省略しないとTLEになる
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print(max(ds))
#print(ds)
#print(inds)

Submission status: Accepted

Solution code:
# かつっぱさん見て
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
babies=[(q,i) for i,q in enumerate(a)]
babies.sort(reverse=True)

dp=defaultdict(int)
ans=0
for l in range(n):
  for r in range(n):
    if l+r==n:
      ans=max(ans,dp[(l,r)])
      break
    act,ind=babies[l+r]
    dp[(l+1,r)]=max(dp[(l+1,r)],dp[(l,r)]+act*abs(ind-l))
    dp[(l,r+1)]=max(dp[(l,r+1)],dp[(l,r)]+act*abs(ind-(n-1-r)))

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]
 
def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res
 
print(solve(0, N-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  INF = float('inf')
  A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
  A = sorted(A, key=lambda x: x[1], reverse = True)

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

  for s in range(1, N+1):
    for l in range(s+1):
      r = s - l
      dp[l][r] = max(dp[l-1][r] + A[s-1][1] * abs(A[s-1][0]-l), dp[l][r-1] + A[s-1][1] * abs(N-r+1-A[s-1][0]))
    
  ans = 0
  for m in range(N):
    if(dp[m][N-m] > ans):
      ans = dp[m][N-m]
    
  print(ans)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]
#ds=[[0 for j in range(N+1-i)] for i in range(N+1)]

ds=[0]
for xy in range(1,N+1):
    i=inds[xy-1]
    a=As[i]
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+a*(i-(xy-1))
    nds[0]=ds[0]+a*(N-xy-i)

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+a*abs(i-(x-1))
        c2=ds[x]+a*abs(N-y-i)
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print(max(ds))
#print(ds)
#print(inds)

Submission status: Accepted

Solution code:
e=enumerate
n,*a=map(int,open(0).read().split())
d=[0]
for j,(a,i)in e(sorted((a,i)for i,a in e(a))[::-1]):d=[d[0]+a*abs(n-j-i-1)]+[max(d[k]+a*abs(n-j+k-i-1),d[k-1]+a*abs(i-k+1))for k in range(1,j+1)]+[d[j]+a*abs(i-j)]
print(max(d))

Submission status: Accepted

Solution code:
N=int(input());A=sorted((int(x),i)for i,x in enumerate(input().split()));t=[0]*N**2
for w in range(N):
 a,j=A[w]
 for l in range(N-w):
  r=l+w;p=a*abs(j-l);t[l*N+r]=max(p+t[(l+1)*N+r],a*abs(j-r)+t[l*N+r-1])if w else p
print(t[N-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,(input().split())))
B = [(0)*2 for _ in range(N)]
for i in range(N):
    B[i] = (A[i],i)
B.sort(reverse=True)

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

ans = []
for l in range(N+1):
    for r in range(N+1):
        if l+r == N:
            ans.append(dp[l][r])
            break
        if r+1 < N+1:
            dp[l][r+1] = max(dp[l][r+1], dp[l][r] + B[l+r][0] * abs(B[l+r][1] - (N-(r+1)) ))
        if l+1 < N+1:
            dp[l+1][r] = max(dp[l+1][r], dp[l][r] + B[l+r][0] * abs(B[l+r][1] - l))

print(max(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = list(map(int, input().split()))
acts = [(x, i) for i, x in enumerate(A)]
acts.sort()
dp = [[-1]*N for _ in range(N)]

def solve(l, r):
    if r < l:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    act, init_pos = acts[k]
    gain_l = act * abs(l - init_pos)
    gain_r = act * abs(r - init_pos)
    res = dp[l][r] = max(gain_l + solve(l+1, r), gain_r + solve(l, r-1))
    return res

print(solve(0, N-1))

Submission status: Accepted

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

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

A2=[(num,ind) for ind,num in enumerate(A)]
A2.sort(reverse=True)

L=[0]*N

for i in range(N):
    num,ind=A2[i]
    NL=[0]*N
    for j in range(i+1):
        right=N-1-(i-j)
        NL[j]=max(NL[j],abs(right-ind)*num+L[j])

        if j!=N-1:
            NL[j+1]=max(NL[j+1],abs(j-ind)*num+L[j])
    L=NL
print(max(L))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
A = inputIL()

dic = [[INF,0]]

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

dic.sort(reverse=True)

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


for n in range(1,N+1):
  for i in range(n+1):
    if i == 0:
      table[n][0] = table[n-1][0] + dic[n][0] * (dic[n][1] -n)
    elif i == n:
      table[0][n] = table[0][n-1] + dic[n][0] * (N -(n-1) - dic[n][1])
    else:
      table[n-i][i] = max(table[n-i-1][i] + dic[n][0] * (dic[n][1] -(n-i)), table[n-i][i-1] + dic[n][0] * (N -(i-1) - dic[n][1]))
  
m = 0
for i in range(0,N+1):
  m = max(m,table[N-i][i])
  
print(m)

Submission status: Accepted

Solution code:
# E - Active Infants

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

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] = 位置jから幅iの区間に小さい方から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 sys

sys.setrecursionlimit(2 * 10 ** 5)

N = int(input())

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

cache = [[None for i in range(N + 1)] for j in range(N + 1)]


def dp(l, r):
    if l > r:
        return 0
    if cache[l][r] is None:
        a, x = A[r - l]
        cache[l][r] = max(a * abs(x - l) + dp(l + 1, r), a * abs(x - r) + dp(l, r - 1))
    return cache[l][r]


print(dp(0, N - 1))

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([(int(a), i) for i, a in enumerate(input().split())], key = lambda x: x[0])[::-1]
X = [0] + [-1<<100] * (N + 5)
for k, (a, i) in enumerate(A):
    X = [max(X[j] + abs(N - (k - j) - 1 - i) * a, X[j-1] + abs(j - 1- i) * a if j else 0) for j in range(N + 5)]
print(max(X))

Submission status: Accepted

Solution code:
def solve(n, aaa):
    dp = [0]
    aaa_with_idx = list(zip(aaa, range(n)))
    aaa_with_idx.sort(reverse=True)
    for k in range(1, n + 1):
        ndp = [0] * (k + 1)
        a, i = aaa_with_idx[k - 1]
        for l in range(k):
            # 左に配置
            ndp[l + 1] = max(ndp[l + 1], dp[l] + a * abs(i - l))
            # 右に配置
            r = n - (k - l)
            ndp[l] = max(ndp[l], dp[l] + a * abs(i - r))
        dp = ndp
    return max(dp)


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  A = list(map(int,input().split()))
  A = [[a,i] for a,i in zip(A,range(1,N+1))]
  A = sorted(A,reverse=True)
  INF = float('inf')
  dp = [[-INF] * (N+1) for _ in range(N+1)]
  dp[0][0] = 0
  ans = 0
  for x_y in range(1,N+1):
    a = A[x_y-1]
    for x in range(x_y+1):
      y = x_y-x
      if x==0:
        dp[x][y] = dp[x][y-1] + a[0]*(N-y+1-a[1])
      elif y==0:
        dp[x][y] = dp[x-1][y] + a[0]*(a[1]-x)
      else:
        dp[x][y] = max(dp[x-1][y]+a[0]*(a[1]-x),dp[x][y-1] + a[0]*(N-y+1-a[1]))

      ans = max(ans,dp[x][y])
  print(ans)
  
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = [[a,i] for a,i in zip(A,range(1,N+1))]
A = sorted(A,reverse=True)
INF = float('inf')
dp = [[-INF] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for x_y in range(1,N+1):
  a = A[x_y-1]
  for x in range(x_y+1):
    y = x_y-x
    if x==0:
      dp[x][y] = dp[x][y-1] + a[0]*(N-y+1-a[1])
    elif y==0:
      dp[x][y] = dp[x-1][y] + a[0]*(a[1]-x)
    else:
      dp[x][y] = max(dp[x-1][y]+a[0]*(a[1]-x),dp[x][y-1] + a[0]*(N-y+1-a[1]))
    
    ans = max(ans,dp[x][y])
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    #AAwIdx = list(map(int,input().split()))
    AAwIdx = [(i,A) for i, A in enumerate(map(int, input().split()))]
    #for i in range(N):
    #    AAwIdx[i][0] = i
    #    AAwIdx[i][1] = AA[i]
    AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
    #print(AA_sorted)

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

    ans_all = 0
    Idx_i = 0
    Idx_f = N-1
    for i in range(0,N):
        for no in range(i+1):
            idxi = i-no
            idxf = Idx_f-no
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1]
            if ans>answer[i+1-no][no]:
                answer[i+1-no][no] = ans
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1]
            if ans>answer[i-no][no+1]:
                answer[i-no][no+1] = ans
    for i in range(N,N+1):
        for no in range(i+1):
            if ans_all<answer[i-no][no]:
                ans_all = answer[i-no][no]

    print(ans_all)
solve()

Submission status: Accepted

Solution code:
def solve():
    INF = float('inf')
 
    def max2(x, y): return x if x >= y else y
 
    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]
 
    As.sort(reverse=True)
 
    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))
 
    ans = 0
    for i in range(N+1):
        j = N-i
        ans = max2(ans, dp[i][j])
 
    print(ans)
 
 
solve()

Submission status: Accepted

Solution code:
#active infants

n=int(input())
lists=list(map(int,input().split()))
data=[]
for i in range(n):
    data.append((lists[i],i+1))
data=sorted(data,key=lambda x:-x[0])


#dp[K][i]=始めのKつまで考えてそのうちプラスの個数がiこの方法で最大のあたい(0<=i<=K)
#求める値はmax(dp[N][i]　for i in range(N+1))で与えられる
#dp[N][N]まで考えればいい

#計算量0(N**2)
dp=[[0 for i in range(n+1)] for j in range(n+1)]

dp[1][1]=n*(data[0][0])-data[0][0]*data[0][1]
dp[1][0]=data[0][0]*data[0][1]-data[0][0]

for i in range(2,n+1):
    #dp[i]について考える
    for j in range(i+1):
        x=data[i-1][0]
        y=data[i-1][1]
        #j=0,1,,,,,iまで
        #dp[i][j]-> 直前は i-1,j-1, or i-1 j のどちらか
        if i>j>=1:
            dp[i][j]=max(dp[i-1][j-1]+x*(n+1-j)-x*y,dp[i-1][j]-(i-j)*x+x*y)
        elif j==0:
            dp[i][j]=dp[i-1][0]-i*x+x*y
        elif j==i:
            dp[i][j]=dp[i-1][i-1]+x*(n+1-j)-x*y        
K=0
for i in range(n+1):
    K=max(K,dp[n][i])
print(K)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    infants = [(ai, i) for i, ai in enumerate(A)]
    infants.sort(reverse=True)
    
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    ans = 0
    for x in range(N):
        for y in range(N):
            if x + y == N:
                ans = max(ans, dp[x][y])
                break
            act_level, idx = infants[x + y]
            dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + act_level * abs(idx - x))
            dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + act_level * abs(idx - (N - y - 1)))
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)           

def main():
    n = int(input())
    a = list(enumerate(map(int,input().split())))
    a.sort(key = lambda x:x[1],reverse = True)

    dp = [[0] * (n + 1) for _ in range(1 + n)]
    for i in range(n + 1):
        for j in range(i + 1,n):
            dp[i][j] = -INF

    for j in range(n):
        i,num = a[j]
        i += 1
        for k in range(j + 2):
            if k == 0:
                dp[j + 1][k] = dp[j][k] + num * abs(i - n + j - k)
            else:
                dp[j + 1][k] = max(dp[j][k - 1] + num * abs(i - k),dp[j][k] + num * abs(i - n + j - k))
            
    print(max(dp[-1]))
if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int, input().split())
B=[(i+1,a) for i,a in enumerate(A)]
from operator import itemgetter
B.sort(reverse=True, key=itemgetter(1))

dp = [[-1] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
    idx, act = B[i-1]
    for j in range(i+1):
        k = i-j
        if 0<j: dp[j][k] = max(dp[j][k], dp[j-1][k] + act * abs(idx-j))
        if 0<k: dp[j][k] = max(dp[j][k], dp[j][k-1] + act * abs(idx-(N-k+1)))

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

Submission status: Accepted

Solution code:
N = int(input())
_L = list(map(int,input().split()))
L = [(v,i) for i,v in enumerate(_L)]
L = sorted(L,key=lambda x:(-x[0]))

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

ans=0
for x in range(N):#前から
    for y in range(N):#後ろから
        cur = x+y
        if  cur==N:
            ans = max(ans,dp[x][y])
            break
        val,ind = L[cur]
        dp[x+1][y] = max(dp[x+1][y],dp[x][y]+val*abs(ind-x))
        dp[x][y+1] = max(dp[x][y+1],dp[x][y]+val*abs(N-y-1-ind))
print(ans)

Submission status: Accepted

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

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

"""
参考にしました(写経)
https://atcoder.jp/contests/abc163/submissions/12137623

Axが大きい順に置ける部分の中で一番左か一番右に置きたい
dp[i][j]:左からi個目, 右からj個目まで埋まっているときの最大値
i個目を見ているとき左と右に埋まっている数はi-1個なので
dp[i][j]は(左の個数,右の個数) = (0,i-1),(1,i-2),...とO(N)で探索できる
"""
n = I()
a = LI()
b = [[a[i],i] for i in range(n)]
b.sort(reverse=1)
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
    a,j = b[i]
    for k in range(i+1):
        dp[k][i+1-k] = max(dp[k][i+1-k], dp[k][i-k] + a*abs(j-((n-1)-(i-k)))) #右側に追加
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a*abs(j-k)) #左側に追加
ans = 0
for i in range(n):
    ans = max(ans, dp[i][n-i])
print(ans)