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:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

B = np.sort(A)[::-1]
B_index = np.argsort(A)[::-1]
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
        ind = B_index[x+y-1]
        if x==0 and y==0:
            dp[x][y] = 0
        elif x==0:
            dp[x][y] = dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1)))
        elif y==0:
            dp[x][y] = dp[x-1][y]+B[x+y-1]*abs(ind-(x-1))
        else:
            dp[x][y] = max(dp[x-1][y]+B[x+y-1]*abs(ind-(x-1)),dp[x][y-1] + B[x+y-1]*abs(ind-((N-1)-(y-1))))
        ans = max(ans,dp[x][y])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
a = list(map(int, input().split()))
array = [(a[i], i+1) for i in range(n)]
array.sort(reverse=True)
dp = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n):
    for j in range(n):
        if i + j >= n:
            break
        count = i + j
        #右に移した場合
        value, index = array[count]
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + value * abs((n - j) - index))
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + value * abs((i + 1) - index))
ans = 0
for i in range(n+1):
    for j in range(n+1):
        ans = max(ans, dp[i][j])
print(ans)

Submission status: Time Limit Exceeded

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

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

B = np.sort(A)[::-1]
B_index = np.argsort(A)[::-1]
dp = [[0]*(N+1) for _ in range(N+1)]
ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AAwIdx = [(i,A) for i, A in enumerate(map(int, input().split()))]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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
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]))

print(int(np.max(dp)))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
dp=[[0 for j in range(n+1)] for i in range(n+1)]
e=[]
for i in range(n):
    e.append([l[i],i])
e.sort(reverse=True)
for i in range(1,n+1):
    p=e[i-1][0]
    q=e[i-1][1]
    for j in range(i+1):
        if j<i:
            a1=dp[i-1][j]+p*abs(n-(i-j)-q)
        else:
            a1=0
        if j>0:
            a2=dp[i-1][j-1]+p*abs(q-j+1)
        else:
            a2=0
        dp[i][j]=max(a1,a2)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

B = np.sort(A)[::-1]
B_index = np.argsort(A)[::-1]
dp = [[0]*(N+1) for _ in range(N+1)]

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

print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

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

values = []
num_indcies = {}
for i, a in enumerate(A):
    if not a in num_indcies:
        num_indcies[a] = [i]
        values.append(a)
    else:
        num_indcies[a].append(i)

values = sorted(values, reverse=True)
ans = 0
# indexの配列
dp_indices = []
for v in values:
    dp_indices.extend(num_indcies[v])


dp = [[0] * (N+1) for _ in range(N+1)]
for no, (a, pos) in enumerate(A):
    for i in range(no+1):
        j = no - i
        #k = dp_indices[i+j-2]
        #a = A[k]
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * (pos -i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a * abs(pos - (N-1-j)))

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

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][0]=0
for i in range(1,N+1):
    ds[i][0]=ds[i-1][0]+As[inds[i-1]]*(inds[i-1]-(i-1))
    ds[0][i]=ds[0][i-1]+As[inds[i-1]]*(N-i-inds[i-1])

for xy in range(2,N+1):
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1][y]+As[inds[xy-1]]*(inds[xy-1]-(x-1))
        c2=ds[x][y-1]+As[inds[xy-1]]*(N-y-inds[xy-1])
        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:
N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
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
        answer[i+1-no][no] = max(answer[i+1-no][no],answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1])
        answer[i-no][no+1] = max(answer[i-no][no+1],answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1])
        #print('idx:',AA_sorted[i][0], 'val:',AA_sorted[i][1],'idx_i:',idxi, 'idx_f:',idxf)
        #print('idx:',i-no,no,'ans:',answer[i-no][no])
        #print('idx:',i+1-no,no,'ans:',abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1])
        #print('idx:',i-no,no+1,'ans:',abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1])
        ans_all = max(answer[i+1-no][no], ans_all)
        ans_all = max(answer[i-no][no+1], ans_all)
#print(np.array(answer))
#    print(AAs)
#print(AnsIdx)
print(ans_all)

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

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):
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1,y]+As[xy-1]*(inds[xy-1]-(x-1))
        c2=ds[x,y-1]+As[xy-1]*(N-y-inds[xy-1])
        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:
n=int(input())
a=map(int,input().split())

babies=[(a,i) for i ,a in enumerate(a)]

babies.sort(reverse=True)

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

ans=0

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

print(ans)

Submission status: Time Limit Exceeded

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

a2list=[]
for i in range(N):
  a2list.append((alist[i],i))
a2list.sort(reverse=True)
#print(a2list)

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

for i in range(1,N+1):
  aa,ii=a2list[i-1]
  for j1 in range(i+1):
    j2=i-j1
    if j1==0:
      dp[j1][j2]=dp[j1][j2-1]+aa*abs((N-1)-(j2-1)-ii)
    elif j2==0:
      dp[j1][j2]=dp[j1-1][j2]+aa*abs(ii-(j1-1))
    else:
      dp[j1][j2]=max(dp[j1][j2-1]+aa*abs((N-1)-(j2-1)-ii),dp[j1-1][j2]+aa*abs(ii-(j1-1)))

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

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]

ds=np.zeros((N+1,N+1),dtype=int)

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

for xy in range(2,N+1):
    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1,y]+As[inds[xy-1]]*(inds[xy-1]-(x-1))
        c2=ds[x,y-1]+As[inds[xy-1]]*(N-y-inds[xy-1])
        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:
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)]

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i])

#二次元配列初期化
ar = [[-1 for i2 in range(N)] for i1 in range(N)]

A.sort(reverse=True)

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l,nn):
    global r_max
    if ar[h][l] > r:
        return
    else:
        ar[h][l] = r
    if i == nn:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)

for nn in range(10,N-1,10):
    test(0,0,N-1,0,min(N-1,nn))

test(0,0,N-1,0,N-1)

print(r_max)

Submission status: Time Limit Exceeded

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = sorted([[i+1, d] for i, d in enumerate(lr())], key=lambda x: x[1])[::-1]
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0] = 0
    for s in range(1, N+1):
        for x in range(s):
            for y in range(s-x):
                i, d = A[x+y]
                dp[x+1, y] = max(dp[x, y]+d*(i-x-1), dp[x+1, y])
                dp[x, y+1] = max(dp[x, y]+d*(N-y-i), dp[x, y+1])
    ans = 0
    for i in range(N+1):
        ans = max(ans, dp[i, N-i])
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i])

#二次元配列初期化
ar = [[-1 for i2 in range(N)] for i1 in range(N)]

A.sort(reverse=True)

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l,nn):
    global r_max
    if ar[h][l] > r:
        return
    else:
        ar[h][l] = r
    if i == nn:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)
'''
for nn in range(10,N-1,10):
    test(0,0,N-1,0,min(N-1,nn))
'''
test(0,0,N-1,0,N-1)

print(r_max)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i])

#二次元配列初期化
ar = [[-1 for i2 in range(N)] for i1 in range(N)]

A.sort(reverse=True)

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l,nn):
    global r_max
    if ar[h][l] > r:
        return
    else:
        ar[h][l] = r
    if i == nn:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)

for n in range(5,N,2):
    test(0,0,N-1,0,n)

test(0,0,N-1,0,N-1)

print(r_max)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[l-1][r] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[l][r+1] + a * abs(r+1-idx)
        dp[l][r] = max(lsc, rsc)
print(max(dp[i][i-1] for i in range(N)))

Submission status: Time Limit Exceeded

Solution code:
import sys
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline

N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = sorted(zip(map(int, (input().split())) ,range(N)), reverse=True)
# print(A)

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

L = [[x, i] for i, x in enumerate(A)]
L.sort()
@lru_cache(maxsize=None)
def rec(l, r):
	if l > r:
		return 0
	idx = r-l  # 次に選ぶ幼児
	val, i = L[idx]
	ret = max(abs(i-l)*val + rec(l+1, r), abs(r-i)*val + rec(l, r-1))
	return ret

print(rec(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [(int(x), int(y)) for x, y in zip(input().split(), range(n))]
a.sort(reverse=True)

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i])

#二次元配列初期化
ar = [[-1 for i2 in range(N)] for i1 in range(N)]

A.sort(reverse=True)

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l,nn):
    global r_max
    if ar[h][l] > r:
        return
    else:
        ar[h][l] = r
    if i == nn:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1,nn)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l,nn)

for n in range(N):
    test(0,0,N-1,0,n)

print(r_max)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(i, l, r):
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (i, l, r) in dp:
        return dp[(i, l, r)]
    res = max((idx-l)*a + dfs(i+1, l+1, r), (r-idx)*a + dfs(i+1, l, r-1))
    dp[(i, l, r)] = res
    return res
ans = dfs(0, 0, n-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# My Answer -> TLE
N = int(input())
A = list(map(int, input().split()))

from itertools import permutations

lis = [0]*N
for i in range(N):
    lis[i] = i

scores = []
for i, v in enumerate(permutations(lis, N)):
    score = 0
    for j in range(N): 
        score += abs(v.index(j)-j) * A[j]
    scores.append(score)

print(max(scores))

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = [[-1]*n for _ in range(n)]
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if dp[l][r] != -1:
        return dp[l][r]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[l][r] = res
    return res
ans = dfs(0, n-1)
print(ans)

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int, input().split()))
L = [(a, i) for i, a in enumerate(A)]
L.sort(reverse=True)
dp = dict()
def dfs(l, r):
    i = (n-1-r) + l
    a, idx = L[i]
    if i == n-1:
        res = max(idx-l, r-idx) * a
        return res
    if (l, r) in dp:
        return dp[(l, r)]
    res = max((idx-l)*a + dfs(l+1, r), (r-idx)*a + dfs(l, r-1))
    dp[(l, r)] = res
    return res
ans = dfs(0, n-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N=int(input())
actlist=list(map(int,input().split()))
alllist=list(itertools.permutations(range(1,N+1)))

count=1
l=len(alllist)
maxnum=0

for i in range(0,l-1):
    for j in range(i+1,l):
        hapsum=0
        for m,n in zip(alllist[i],alllist[j]):
            hapsum+=actlist[m-1]*abs(m-n)
        if maxnum<hapsum:
            maxnum=hapsum
        
print(maxnum)

Submission status: Time Limit Exceeded

Solution code:
import sys

# 整数を一つ入力
N = int(input())
# スペース区切りの整数をリストに入力
t = [int(x) for x in input().split()]

A = []
for i in range(N):
    A.append([t[i],i])

#二次元配列初期化
ar = [[-1 for i2 in range(N)] for i1 in range(N)]

A.sort(reverse=True)

r_max = 0

sys.setrecursionlimit(2500)
def test(i,r,h,l):
    global r_max
    if ar[h][l] >= r:
        return
    else:
        ar[h][l] = r
    if i == N-1:
        r_max = max(r_max, r+abs(A[i][1]-h)*A[i][0])
    else:
        if abs(h-A[i][1]) > abs(l-A[i][1]):
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l)
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1)
        else:
            test(i+1,r+abs(A[i][1]-l)*A[i][0],h,l+1)
            test(i+1,r+abs(A[i][1]-h)*A[i][0],h-1,l)

test(0,0,N-1,0)

print(r_max)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: x[1])

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        idx, a = arridx[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a * abs(l-1-idx)
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a * abs(r+1-idx)
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i) for i in range(n)]
a.sort(key=lambda x: -x[0])
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for x in range(n+1):
    for y in range(n+1):
        if x + y > n:
            break
        active, idx = a[x+y-1]
        if x > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x-1][y] + active * abs(idx - (x-1)))

        if y > 0:
            dp[x][y] = max(dp[x][y],
                           dp[x][y-1] + active * abs(idx - (n-y)))

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

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for p in permutations(range(N)):
    tmp = 0
    for i in range(N):
        tmp += A[i] * abs(i-p[i])
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
arr=[[arr[i],i] for i in range(n)]
arr=sorted(arr,reverse=True,key=lambda x:x[0])
dp=[[-1]*(n+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
  for j in range(n):
    if dp[i][j]==-1:
      continue
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+arr[i][0]*abs(arr[i][1]-j))
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+arr[i][0]*abs(n-1-(i-j)-arr[i][1]))
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

#((0, 1), (1, 3), (2, 4), (3, 2))
#((0, 1), (1, 3), (3, 2), (2, 4))
def calc1(target):
  global First
  list = []
  for i in range(len(First)):
    list.append(abs(target.index(First[i]) - i))
  return list

def calc2(ret):
  global First
  sum = 0
  for i in range(len(First)):
    sum += First[i][1] * ret[i]
  return sum

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

M = list(enumerate(A))
#print(M)

L = list(itertools.permutations(M))
#print(L)
First = L[0]

max = 0

for i in range(len(L)):
#  print(calc1(L[i]))
  ret = calc2(calc1(L[i]))
  #print(ret)
  if max < ret:
    max = ret

print(max)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

N = int(input())
A_map = map(int, input().split())
A = list(A_map)
#NUM = [0]*N
#for i in range(N):
#    NUM[i] = i
NUM = [i for i in range(N)]
a = list(itertools.permutations(A,N))
num = list(itertools.permutations(NUM,N))
ureshisa = 0
ureshisa_max = 0

for aa, nnum, i in zip(a, num ,range(len(a))):
    #print(aa)
    #print(nnum)
    #print(i)
    ureshisa = 0
    for j in range(N):
        ureshisa = ureshisa + aa[j]*abs(j-nnum[j])
    if ureshisa >= ureshisa_max:
        ureshisa_max = ureshisa
print(ureshisa_max)
#for i in range(len(a)):
#    for j in range(N):

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

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

memo = {}

def solve(i, l, r):
    if i==N: return 0

    key = (i,l,r)
    if key in memo: return memo[key]
    
    a, loc = A[i]
    score_l = a*abs(l-loc) + solve(i+1, l+1, r)
    score_r = a*abs(r-loc) + solve(i+1, l, r-1)
    retval = max(score_l, score_r)
    memo[key]=retval
    
    return retval
    
print(solve(0, 0, N-1))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def happy(A, order):
    s = 0
    for i in range(N):
        s += A[i] * abs(order[i]-i)
    return s

a = []
for i in range(N):
    a.append(i)

orders = list(itertools.permutations(a,N))

happies = []

for o in orders:
    happies.append(happy(A,o))

happies.sort()

print(happies[len(happies)-1])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = list(map(int, input().split()))
B = [n for n in range(N)]
mx = 0
for v in itertools.permutations(B, N):
    P = list(v)
    t = 0
    for i in range(N):
        idx = P.index(i)
        t += A[i] * abs(idx-i)
    mx = max([t,mx])
print(mx)

Submission status: Time Limit Exceeded

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

children=[{"A":A[i],"x":i} for i in range(len(A))]
children.sort(key=lambda x:x["A"],reverse=True)

state=[(
    N-1,#RightEnd
    0,#leftEnd
    0 #grad
)]

for child in children:
    newState=[]
    for s in state:
        rightEnd=s[0]
        leftEnd=s[1]
        grad=s[2]
        rval=abs(rightEnd-child["x"])
        lval=abs(leftEnd-child["x"])
        newState+=[(
            rightEnd-1,
            leftEnd,
            grad+rval*child["A"]
        ),
        (
            rightEnd,
            leftEnd+1,
            grad+lval*child["A"]
        )]
    state=newState

state.sort(key=lambda x:x[2],reverse=True)
print(state[0][2])

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

N = int(input())
A_map = map(int, input().split())
A = list(A_map)
NUM = [0]*N
for i in range(N):
    NUM[i] = i
a = list(itertools.permutations(A,N))
num = list(itertools.permutations(NUM,N))
ureshisa = 0
ureshisa_max = 0

for aa, nnum, i in zip(a, num ,range(len(a))):
    #print(aa)
    #print(nnum)
    #print(i)
    ureshisa = 0
    for j in range(N):
        ureshisa = ureshisa + aa[j]*abs(j-nnum[j])
    if ureshisa >= ureshisa_max:
        ureshisa_max = ureshisa
print(ureshisa_max)
#for i in range(len(a)):
#    for j in range(N):

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from collections import defaultdict

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

hp = []
for i, e in enumerate(a, 1):
    heappush(hp, [-e, i])

dp = defaultdict(int)
dp[(0, n + 1)] = 0
while hp:
    e, i = heappop(hp)
    e = -e
    dp2 = defaultdict(int)
    for k, v in dp.items():
        l, r = k
        dp2[(l + 1, r)] = max(dp2[(l + 1, r)], v + abs(l + 1 - i) * e)
        dp2[(l, r - 1)] = max(dp2[(l, r - 1)], v + abs(r - 1 - i) * e)

    dp = dp2

ans = 0
for k, v in dp.items():
    ans = max(ans, v)

print(ans)