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: Time Limit Exceeded

Solution code:
#coding: utf-8
import numpy as np
N = int(input())
A = np.array(input().split(" ")).astype(np.int32)

base = np.arange(N)
ex = base.reshape(1, -1)
for i in range(N):
  for j in range(N):
    if j != i:
      for ex1 in ex:
        koho = ex1.copy()
        v = koho[j]
        koho[j] = koho[i]
        koho[i] = v
        if not np.all(ex == koho, axis = 1).any():
          ex = np.append(ex, koho.reshape(1, -1), axis = 0)
champ = 0
for ex1 in ex:
  champ = max(champ, (A * np.abs(base - ex1)).sum())
print(champ)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1-i):
        if i+j==0:
            continue
        v=b[i+j-1][0]
        pos=b[i+j-1][1]
        if i==0:
            dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
        elif j==0:
            dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
        else:
            dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[(v,s) for s,v in enumerate(a)]
b.sort(reverse=True)

dp=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i+j<=n and (i>0 or j>0):
            v=b[i+j-1][0]
            pos=b[i+j-1][1]
            if i==0:
                dp[0][j]=dp[0][j-1]+v*abs(n-j-pos)
            elif j==0:
                dp[i][0]=dp[i-1][0]+v*abs(i-1-pos)
            else:
                dp[i][j]=max(dp[i-1][j]+v*abs(i-1-pos),dp[i][j-1]+v*abs(n-j-pos))
ans=0
for i in range(n):
    happy=dp[i][n-i]
    if happy>ans:
        ans=happy
print(ans)

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
import heapq
import math
import random
import sys
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())),
                 key=lambda x: x[1], reverse=True)
    dp = np.zeros((n+1, n+1), dtype=np.int)

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

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

Submission status: Time Limit Exceeded

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)
from operator import itemgetter

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())),
                 key=itemgetter(1), reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]

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

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

Submission status: Time Limit Exceeded

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)

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())),
                 key=lambda x: x[1], reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]

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

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

Submission status: Time Limit Exceeded

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)

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 = [(num, i) for i, num in enumerate(int(c) for c in input().split())]
    arr.sort(reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]    

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

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

Submission status: Time Limit Exceeded

Solution code:

if __name__ == "__main__":
    n = int(input())
    arr = [(num, i) for i, num in enumerate(int(c) for c in input().split())]
    arr.sort(reverse=True)
    dp = [[0] * (n+1) for _ in range(n+1)]    

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

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

Submission status: Time Limit Exceeded

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)

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

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort(key=lambda x: -x[0])
    dp = [[0] * (n+1) for _ in range(n+1)]    

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

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

Submission status: Time Limit Exceeded

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:
            break
        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: Time Limit Exceeded

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)

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

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    arr = [(num, i) for i, num in enumerate(nums)]
    arr.sort(key=lambda x: -x[0])
    dp = [[0] * (n+1) for _ in range(n+1)]    

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

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

Submission status: Time Limit Exceeded

Solution code:
#################################3
#################################3
#################################3
#################################3


def read(container_type, data_type):
    return container_type(data_type(x) for x in input().split())


n, = read(tuple, int)
arr = read(list, int)

i_sorted = sorted(range(n), key=lambda i: arr[i], reverse=True)

# import functools
# import sys
#
# sys.setrecursionlimit(1000000)
#
#
# @functools.lru_cache(None)
# def dp_func(left, right):
#     if left >= right:
#         return 0
#     i = i_sorted[n - right + left]
#     x = arr[i]
#     dl = abs(i - left)
#     dr = abs(i - right + 1)
#     # if dl > dr:
#     #     return x * dl + dp(left + 1, right)
#     # elif dl < dr:
#     #     return x * dr + dp(left, right - 1)
#     return max(x * dl + dp_func(left + 1, right), x * dr + dp_func(left, right - 1))


dp = [[0] * (n + 1) for _ in range(n + 1)]
for ll in range(1, n + 1):
    for left in range(n - ll + 1):
        right = left + ll
        i = i_sorted[n - right + left]
        x = arr[i]
        dl = abs(i - left)
        dr = abs(i - right + 1)
        dp[left][right] = max(x * dl + dp[left + 1][right], x * dr + dp[left][right - 1])

sol = dp[0][n]
print(sol)

#################################3
#################################3
#################################3
#################################3

Submission status: Time Limit Exceeded

Solution code:
#################################3
#################################3
#################################3
#################################3


def read(container_type, data_type):
    return container_type(data_type(x) for x in input().split())


n, = read(tuple, int)
arr = read(list, int)

i_sorted = sorted(range(n), key=lambda i: arr[i], reverse=True)
left = 0
right = n - 1
sol = 0

import functools
import sys

sys.setrecursionlimit(1000000)


@functools.lru_cache(None)
def dp(left, right):
    if left >= right:
        return 0
    i = i_sorted[n - right + left]
    x = arr[i]
    return max(x * abs(i - left) + dp(left + 1, right), x * abs(i - right + 1) + dp(left, right - 1))


sol = dp(0, n)
print(sol)

#################################3
#################################3
#################################3
#################################3

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
sys.setrecursionlimit(10**7)

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)
    
    def point(x,y,ind):
        if ind == N:
            return 0
        else:
            ret1 = point(x+1,y,ind+1)+active[ind][0]*(abs(active[ind][1]-x))
            ret2 = point(x,y-1,ind+1)+active[ind][0]*(abs(active[ind][1]-y))
            ret = max(ret1,ret2)
            return ret
    
    print(point(0,N-1,0))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)

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

for t, (e, idx) in enumerate(a, 1):
    for i in range(1, t + 1):
        j = t - i
        dp[i][j] = max(dp[i][j], dp[i-1][j] + e * abs(idx - i))

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

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split(' ')]

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)
DP =[]
for _ in range(N+1):
    DP.append([0]*(N+1))

for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1][y] = max(DP[x+1][y], DP[x][y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x][y+1] = max(DP[x][y+1], DP[x][y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

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

for r in range(N+1):
    for l in range(N-r+1):
        if r==0 and l==0:
            dp[l][r]=0
        else:
            dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
              dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))

for m in range(N):
    if(dp[m][N-m] > maxnum):
        maxnum = dp[m][N-m]
    
print(maxnum)

Submission status: Time Limit Exceeded

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()))):d=[min(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k))for k,t in e(d)]
print(-min(d))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

dp = [[-INF] * (N+1) for _ in range(N+1)]
        
for r in range(N+1):
    for l in range(N-r+1):
        if r==0 and l==0:
            dp[l][r]=0
        else:
            dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
              dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))
            maxnum=dp[l][r] if maxnum<dp[l][r] else maxnum

print(maxnum)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
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=defaultdict(lambda: [])
for i in range(n):
    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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

n = 0
a = []

sorted_a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**3)
		a = [rng(1, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

	global sorted_a
	sorted_a = list(reversed(sorted(a)))

def sum_happiness(left, right):
	if left + right >= n:
		return 0
	activeness = sorted_a[left + right]
	indexes = [i for i in range(n) if a[i] == activeness]
	offset = left + right - sorted_a.index(activeness)

	left_happiness = activeness * (indexes[offset] - left) + sum_happiness(left + 1, right)
	right_happiness = activeness * (n - 1 - right - indexes[offset]) + sum_happiness(left, right + 1)
	return max(left_happiness, right_happiness)

def get_answer():
	return sum_happiness(0, 0)

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

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

# dp[i][j] := 左にi人、右にj人確定した状態での最大値
dp = list2d(N+1, N+1, -INF)
dp[0][0] = 0
for i, (a, x) in enumerate(A):
    # j := 今左に確定してる人数
    for j in range(i+1):
        # k := 今右に確定してる人数
        k = i - j
        # このaを左にする遷移
        y = j
        dp[j+1][k] = max(dp[j+1][k], dp[j][k] + abs(x - y) * a)
        # このaを右にする遷移
        y = N - 1 - k
        dp[j][k+1] = max(dp[j][k+1], dp[j][k] + abs(x - y) * a)
ans = 0
for i in range(N+1):
    # 左右に計N人決まった状態での最大を取る
    ans = max(ans, dp[i][N-i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:

# -*- coding: utf-8 -*-
import numpy as np
N=int(input())
As=list(map(int, input().split()))

As=np.array(As)
inds=np.argsort(As)[::-1]
As=As[inds]

ds=np.empty((N+1,N+1),dtype=np.int64)

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

for xy in range(2,N+1):
    a=As[xy-1]
    i=inds[xy-1]
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1,y]+a*(i-(x-1))
        c2=ds[x,y-1]+a*(N-y-i)
        ds[x,y]=max(c1,c2)

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

Submission status: Time Limit Exceeded

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):
    nds=[0]*(xy+1)
    nds[-1]=ds[-1]+As[inds[xy-1]]*(inds[xy-1]-(xy-1))
    nds[0]=ds[0]+As[inds[xy-1]]*(N-xy-inds[xy-1])

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


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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a.sort(reverse=True)
INF = float('inf')
#print(a)

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

for num, (A, pos) in enumerate(a):
    #print("="*5, num, "="*5)
    for i in range(num+1):
        j = num - i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A*abs(pos-i))  # 左からi番目の時
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A*abs((n-1-j)-pos))  # 右からj番目の時

        # print("="*3, i, "="*3)
        # for k in range(len(dp)):
        #     print(dp[k])
    

ans = 0
for i in range(n+1):
    j = n-i
    ans = max(ans, dp[i][j])
    # print(f"i = {i}")
    # print(f"j = {j}")
    # print(max(ans, dp[i][j]))

print(ans)

Submission status: Time Limit Exceeded

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

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

for num, (A, pos) in enumerate(a):
    for i in range(num+1):
        j = num - i
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A*abs(pos-i))  # 左からi番目の時
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A*abs((n-1-j)-pos))  # 右からj番目の時


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

print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
N = int(input())

A = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, key=lambda x: x[1], reverse = True)

dp = [[-10 ** 15] * (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)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = map(int,input().split())
A = sorted([(b,a) for a, b in enumerate(a)])[::-1]
dp = [[-1 for _ in range(N+10)]for _ in range(N+10)]
#dp[x][y]: 活発度順でx+y人詰めた時,左にx人右にy人詰めたときの最大値
dp[0][0] = 0
import sys
sys.setrecursionlimit(100000000)

def memo(x, y):
    if x < 0 or y < 0: return -1000000000000 #ありえん
    if dp[x][y] != -1: return dp[x][y]
    val, pre = A[x+y-1][0], A[x+y-1][1]
    dp[x][y] = max(
            #x-1からくるパターン
            memo(x - 1,y) + abs(pre - (x - 1)) * val,
            #y-1からくるパターン
            memo(x, y - 1) + abs(pre - (N - y )) *val,
            )
    return dp[x][y]
ans = 0
for i in range(N): ans = max(ans, memo(i,N - i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]
dp[1][0]=dp[0][0]+B[0][0]*(B[0][1]-1)
dp[0][1]=dp[0][0]+B[0][0]*(N-B[0][1])
for k in range(1,N):
    #j=0
    dp[0][k+1]=dp[0][k]+B[k][0]*(N-k-B[k][1])
    dp[1][k]=max(dp[0][k]+B[k][0]*(B[k][1]-1), dp[1][k-1]+B[k][0]*(N-k+1-B[k][1]))
    #j=k
    dp[k+1][0]=dp[k][0]+B[k][0]*(B[k][1]-k-1)
    dp[k][1]=max(dp[k-1][+1]+B[k][0]*(B[k][1]-k), dp[k][0]+B[k][0]*(N-B[k][1]))
    for j in range(1,k):
        dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))

Submission status: Time Limit Exceeded

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

for i in range(n):
    a[i] = [a[i],i]
l1 = 0
r1 = n-1
l2 = l1
r2 = r1
a.sort(reverse=1)
dp = [[0]*(n+1) for i in range(n+1)]
ans = 0
for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + a[i-1][0] * abs(a[i-1][1]-i+1)
    dp[0][i] = dp[0][i-1] + a[i-1][0] * abs(n-(a[i-1][1])-i)
    for j in range(1,i):
        dp[j][i-j] = max(dp[j-1][i-j]+a[i-1][0]*abs(a[i-1][1]-j+1),dp[j][i-j-1]+a[i-1][0]*abs(n-(a[i-1][1])-(i-j)))
for i in dp:
    ans = max(ans,max(i))
print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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])
        #print(i,j,right,num,ind,NL)
    L=NL
print(max(L))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[]
for k in range(N):
    B.append([A[k],k+1])
B.sort(key=lambda x: x[0], reverse=True)
dp=[[0 for k in range(N+1)]for k in range(N+1)]

for k in range(N):
    for j in range(k+1):
        if k>j:
            dp[j+1][k-j]=max(dp[j][k-j]+B[k][0]*(B[k][1]-j-1), dp[j+1][k-j-1]+B[k][0]*(N-k+j+1-B[k][1]))
        if k==j:
            dp[j+1][0]=dp[j][0]+B[k][0]*(B[k][1]-j-1)
        if j >0:
            dp[j][k-j+1]=max(dp[j-1][k-j+1]+B[k][0]*(B[k][1]-j), dp[j][k-j]+B[k][0]*(N-k+j-B[k][1]))
        if j==0:
            dp[0][k-j+1]=dp[0][k-j]+B[k][0]*(N-k+j-B[k][1])
ans=[]
for k in range(N+1):
    ans.append(dp[k][N-k])
print(max(ans))

Submission status: Time Limit Exceeded

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)]
x_plus_y = 0
ans = 0

for i in range(n):
    if x_plus_y == 0:
        dp[0][1] = a[i][0] * abs((n - a[i][1]))
        dp[1][0] = a[i][0] * abs((a[i][1] - 1))

    else:
        for x in range(x_plus_y + 1):
            y = x_plus_y - x
            dp[x][y+1] = max(dp[x][y+1], a[i][0] * abs((n - y) - a[i][1]) + dp[x][y])
            dp[x+1][y] = max(dp[x+1][y] , a[i][0] * abs((a[i][1] - (1+x))) + dp[x][y])

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

    x_plus_y += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

from functools import lru_cache

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


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


print(dp(0, N - 1))

Submission status: Time Limit Exceeded

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, i)] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = {(j, 0): 0 for j in range(n + 1)}

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

print(dp[(0, n)])