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:
n=int(input())
D=[int(i) for i in input().split()]
D=[(D[i],i) for i in range(n)]
D.sort(reverse=True)

dp={(x,y):0 for x in range(0,n+1) for y in range(0,n+1-x)}

ymax=n-1
for i in range(n):
    genki=D[i][0]
    posit=D[i][1]
    for p in range(i+1):
        x=i-p
        y=p
        now=dp[(x,y)]
        dp[(x+1,y)]=max(now+genki*abs(x-posit),dp[(x+1,y)])
        dp[(x,y+1)]=max(now+genki*abs(ymax-y-posit),dp[(x,y+1)])

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

Submission status: Time Limit Exceeded

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

dp={(x,y):0 for x in range(0,n+1) for y in range(0,n+1-x)}

for i in range(n):
    for p in range(i+1):
        x=i-p
        y=p
        now=dp[(x,y)]
        x_side=D[i][0]*abs(x-D[i][1])
        y_side=D[i][0]*abs(n-y-1-D[i][1])
        dp[(x+1,y)]=max(now+x_side,dp[(x+1,y)])
        dp[(x,y+1)]=max(now+y_side,dp[(x,y+1)])
    
res=[]
for p in range(n+1):
    x=n-p
    y=p
    res.append(dp[(x,y)])
print(max(res))

Submission status: Time Limit Exceeded

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

INF = float("inf")
MX = 2005
dp = [[-INF for _ in range(MX)] for _ in range(MX)]
dp[0][0] = 0
p = []
for i in range(N):
  p.append([A[i], i])
p.sort(reverse = True)
for i in range(N):
  pi = p[i][1]
  for l in range(i + 1):
    r = i - l
    dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + (pi - l) * A[pi])
    dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + ((N - r - 1) - pi) * A[pi])

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

Submission status: Time Limit Exceeded

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

for i, a in enumerate(A):
    table.append([a,i])
table.sort()

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + baby * abs(pos-x+1)) * (x>0),\
                     (DP[x][y-1] + baby * abs(pos-(N-y)) * (y>0)))

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

Submission status: Time Limit Exceeded

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

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

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + table[i-1][0] * abs(table[i-1][1] - x+1)) * (x>0),\
                     (DP[x][y-1] + table[i-1][0] * abs(table[i-1][1] - (N - y)) * (y>0)))

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

Submission status: Time Limit Exceeded

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

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

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + table[i-1][0] * abs(table[i-1][1]  - x+1)) * (x>0),\
                     (DP[x][y-1] + table[i-1][0] * abs(table[i-1][1]   - (N - y))*(y>0)))


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

from itertools import permutations

lis = [i for i in range(N)]

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
from collections import defaultdict

sys.setrecursionlimit(4000)


def main():
  n = int(input())
  arr = map(int, input().split())
  arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

  dp = defaultdict(int)

  def cal(ln, rn):
    if ln + rn > n:
      return

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

    cal(ln + 1, rn)
    cal(ln, rn + 1)

  cal(1, 0)
  cal(0, 1)

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


main()

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = [[0] * (n + 1) for _ in range(n + 1)]
for i, (p, a) in enumerate(arr):
  for l in range(i + 1):
    dp[i + 1][l] = max(dp[i + 1][l], dp[i][l] + a * abs(p - (n - (i - l) - 1)))
    dp[i + 1][l + 1] = max(dp[i + 1][l + 1], dp[i][l] + a * abs(p - l))

print(max(dp[n]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)
for i, (p, a) in enumerate(arr):
  for l in range(i + 1):
    dp[i + 1, l] = max(dp[i + 1, l], dp[i, l] + a * abs(p - (n - (i - l) - 1)))
    dp[i + 1, l + 1] = max(dp[i + 1, l + 1], dp[i, l] + a * abs(p - l))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = sorted(enumerate(arr), key=lambda tpl: -tpl[1])

dp = defaultdict(int)

def cal(ln, rn):
  if ln < 0 or rn < 0 or ln == rn == 0:
    return 0

  if dp[ln, rn] == 0:
    p, a = arr[ln + rn - 1]
    val_l = cal(ln - 1, rn) + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = cal(ln, rn - 1) + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  return dp[ln, rn]


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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = {}
for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp.get((ln, rn)):
      continue

    if ln == rn == 0:
      dp[0, 0] = 0
    else:
      p, a = arr[ln + rn - 1]
      val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
      val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

      dp[ln, rn] = max(val_l, val_r)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

for ln in range(n + 1):
  for rn in range(n + 1 - ln):
    if ln + rn > n or dp[ln, rn]:
      continue

    p, a = arr[ln + rn - 1]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

def cal(ln, rn):
  if ln + rn > n:
    return

  p, a = arr[ln + rn - 1]
  val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
  val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

  dp[ln, rn] = max(val_l, val_r)

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(1, 0)
cal(0, 1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(4000)

n = int(input())
arr = map(int, input().split())
arr = tuple(sorted(enumerate(arr), key=lambda tpl: -tpl[1]))

dp = defaultdict(int)

def cal(ln, rn):
  if ln + rn > n:
    return

  if ln > 0 or rn > 0:
    idx = ln + rn - 1
    p, a = arr[idx]
    val_l = dp[ln - 1, rn] + a * abs(p - (ln - 1)) if ln > 0 else 0
    val_r = dp[ln, rn - 1] + a * abs(p - (n - rn)) if rn > 0 else 0

    dp[ln, rn] = max(val_l, val_r)

  cal(ln + 1, rn)
  cal(ln, rn + 1)

cal(0, 0)

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

Submission status: Time Limit Exceeded

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

infants = [[i, A[i]] for i in range(N)]
infants.sort(key=lambda x:x[1], reverse=True)

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

for x in range(N):
    for y in range(N-x):
        pos, infant = infants[x+y]
        dp[x][y+1] = max(dp[x][y+1], dp[x][y]+infant*abs(N-1-y-pos))
        dp[x+1][y] = max(dp[x+1][y], dp[x][y]+infant*abs(pos-x))

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

Submission status: Time Limit Exceeded

Solution code:
def slove(n, a_list):

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

    return max([max(i) for i in dp])

if __name__ == "__main__":
    n = int(input())
    k = sorted([(int(x),i) for i,x in enumerate(input().split())], reverse=True)
    print(slove(n, k))

Submission status: Time Limit Exceeded

Solution code:
def slove(n, k):
    a_list = sorted([(int(x),i) for i,x in enumerate(k.split())], reverse=True)
    dp = [[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n-i):
            dp[i+1][j] = max(dp[i+1][j],
                         dp[i][j]+a_list[i+j][0]*abs(a_list[i+j][1]-i))
            dp[i][j+1] = max(dp[i][j+1],
                         dp[i][j]+a_list[i+j][0]*abs((n-1-j)-a_list[i+j][1]))

    return max([max(i) for i in dp])

if __name__ == "__main__":
    n = int(input())
    k = input()
    print(slove(n, k))

Submission status: Time Limit Exceeded

Solution code:
def slove(n, k):
    a_list = sorted([(int(x),i) for i,x in enumerate(k.split())], reverse=True)
    dp = [[0]*(n+1) for i in range(n+1)]
    ans = []
    for i in range(n):
        for j in range(n-i):
            dp[i+1][j] = max(dp[i+1][j],
                         dp[i][j]+a_list[i+j][0]*abs(a_list[i+j][1]-i))
            dp[i][j+1] = max(dp[i][j+1],
                         dp[i][j]+a_list[i+j][0]*abs((n-1-j)-a_list[i+j][1]))
        ans.append(max(dp[i][:-1]))
    return max(ans)

if __name__ == "__main__":
    n = int(input())
    k = input()
    print(slove(n, k))

Submission status: Time Limit Exceeded

Solution code:
import itertools

n = int(input())
arr = tuple(map(int, input().split()))

results = []
for dst in itertools.permutations(range(n)):
  results.append(sum(
    [a * abs(i - dst[i]) for i, a in enumerate(arr)]
  ))

print(max(results))

Submission status: Time Limit Exceeded

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

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

dp = [[0 for _ in range(n+1)] for _ 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] + activeness * abs(ind - l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + activeness * abs(ind - (n - 1 - r)))
print(ans)

Submission status: Time Limit Exceeded

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

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

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

dp=[[0]*(N+1) for _ in range(N+1)]
for i,(a,p) in enumerate(A):
  for j in range(i+1):
    #左詰
    dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(p-j)*a)
    #右詰
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+((N-1-(i-j))-p)*a)
print(max(dp[-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

input()
arr = [(v, idx) for idx, v in enumerate(map(int, input().split()))]

dp = [-1 for _ in range(len(arr))]


def maximize(global_idx, temp_arr):
    if len(temp_arr) == 0:
        return 0

    # if dp[global_idx] != -1:
    #     return dp[global_idx]

    mx = 0

    for idx, child in enumerate(temp_arr):
        v, local_idx = child
        mx = max(mx, abs(global_idx - local_idx) * v + maximize(global_idx + 1, temp_arr[:idx] + temp_arr[idx + 1:]))

    dp[global_idx] = mx
    return dp[global_idx]


print(maximize(0, arr[:]))

Submission status: Time Limit Exceeded

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

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

p = []
for i in range(n):
    p.append((a[i], i))
p.sort(key=lambda x: -x[0])

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

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

print(ans)

Submission status: Time Limit Exceeded

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

m = []
for x, c in enumerate(l):
    m.append((c, x))
m.sort(reverse=True)

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

result = 0
for i, (c, x) in enumerate(m):
    s = n-i-2
    for j in range(i+2):
        if j + s + 1 < n:
            dp[j][j + s] = max(dp[j][j + s], dp[j][j + s + 1] + c * abs(x - (j + s + 1)))
        if j > 0:
            # print(j, s)
            try:
                dp[j][j+s] = max(dp[j][j+s], dp[j-1][j+s] + c * abs(x - (j-1)))
            except Exception as e:
                continue
        result = max(result, dp[j][j+s])
        # print("res: ", result)
print(result)

Submission status: Time Limit Exceeded

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

m = {}
for x, c in enumerate(l):
    if c in m:
        m[c].append(x)
    else:
        m[c] = [x]

s = {(0, n): 0}
result = 0

def add(new, l, r, v):
    # print("adding: ", l, r, v)
    if l == r:
        # print("here")
        global result
        result = max(result, v)
        return
    if (l, r) in new:
        new[(l, r)] = max(new[(l, r)], v)
    else:
        new[(l, r)] = v
        

m = list(sorted(list(m.items()), reverse=True))
for c, posx in m:
    rposx = list(reversed(posx))
    z = len(posx)
    new = {}
    for (left, right), value in s.items():
        # print("abc: ", left, right, value, rposx)
        l = left + z
        r = right
        d0 = sum((abs(left+i-x) for i, x in enumerate(rposx)))
        # print("do: ", d0)
        add(new, l, r, value + d0*c)
        for i, x in enumerate(posx):

            l -= 1
            r -= 1
            d0 = d0 - abs(l - x) + abs(r - x)
            

            # print("d0: ", d0)
            add(new, l, r, value + d0*c)
    s = new
    
print(result)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(v) for v in input().split()]
P = sorted([(v, i) for i, v in enumerate(A)], key=lambda x: x[0], reverse=True)
dp = [[0 for j in range(2005)] for i in range(2005)]

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, *A = map(int, open(0).read().split())

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

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

print(max(dp[N]))

Submission status: Time Limit Exceeded

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

# dp[i][j] 左端からi個、右端からj個を入れた場合の最適
dp = [[0]*(n+1) for _ in range(n+1)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ch=[]
for i in range(n):
    ch.append((a[i],i))
ch.sort(reverse=True)
#print(ch)
dp=[[0]*(n+1) for _ in range(n+1)]
dp[1][1]=ch[0][0]*ch[0][1]
dp[1][0]=ch[0][0]*(n-1-ch[0][1])
for i in range(2,n+1):
    for j in range(i+1):
        if j>=1:
            dp[i][j]=max(dp[i][j],dp[i-1][j-1]+ch[i-1][0]*abs(ch[i-1][1]-j+1))
        if i-1>=j:
            dp[i][j]=max(dp[i][j],dp[i-1][j]+ch[i-1][0]*abs(n-i+j-ch[i-1][1]))
print(max(dp[n]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
INF=10**9
dp=[[-INF for i in range(N+1)] for j in range(N+1)]
dp[0][0]=0
AI=[]

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

for i in range(1,N+1):
    a=AI[i-1][0]
    I=AI[i-1][1]
    for j in range(N+1):
        if j==0:
            dp[i][j]=dp[i-1][j]+abs(I-(N+1-i))*a
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+abs(I-j)*a
        else:
            dp[i][j]=max(dp[i-1][j-1]+abs(I-j)*a,dp[i-1][j]+abs(I-(N+1-(i-j)))*a)
ans=0
for i in range(N+1):
    ans=max(ans,dp[N][i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

DP = {}
DP[(0, 0)] = 0

for wa in range(1, N+1):
    # AA[:wa]までを考える
    a, i = AA[wa-1]
    for x in range(wa+1):
        y = wa - x
        DP[(x, y)] = 0
        if x - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x-1, y)]+a*(i-x))
        if y - 1 >= 0:
            DP[(x, y)] = max(DP[(x, y)], DP[(x, y-1)]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

print(max([DP[(x, N-x)] for x in range(N+1)]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

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

for wa in range(1, N+1):
    # AA[:wa]までを考える
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)


# def guchoku():
#     AA = [(a, i) for i, a in enumerate(A)]
#     mt = 0
#     mp = None
#     for p in itertools.permutations(AA):
#         tot = 0
#         for i in range(N):
#             a1, i1 = p[i]
#             tot += a1*abs(i1-i)
#         if mt < tot:
#             mt = tot
#             mp = p
#     return mt, mp


# print(guchoku())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())
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: Time Limit Exceeded

Solution code:
n = int(input())
*A, = map(int, input().split())
# n = 6
# A = [8, 6, 9, 1, 2, 1]
# n = 4
# A = [1, 3, 4, 2]
A = [(a, i) for i, a in enumerate(A)]
A.sort(reverse=True)
DP = [[0 for r in range(n+1)] for l in range(n+1)]
for l in range(n):
    for r in range(n-l):
        a, i = A[l+r]
        DP[l+1][r] = max(DP[l+1][r], DP[l][r]+a*abs(i-l))
        DP[l][r+1] = max(DP[l][r+1], DP[l][r]+a*abs(i-(n-1-r)))
print(max([DP[l][n-l] for l in range(n)]))

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

for i in range(N):
    a, idx = A_and_i[i]

    for j in range(N):
        # 右に持っていく
        if j <= i:
            DP[i + 1][j] = max(DP[i + 1][j], DP[i][j] +
                               a * abs(N - 1 - (i - j) - idx))
            DP[i + 1][j + 1] = max(DP[i + 1][j + 1], DP[i]
                                   [j] + a * abs(idx - j))

ans = max(DP[N])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!python3
import sys
sys.setrecursionlimit(1000000000)
from functools import lru_cache

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(enumerate(iim()))

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

    @lru_cache
    def rec(i, j1, j2):
        if i == N:
            return 0
        pos, ai = A[i]

        ax = abs(pos - j1) * ai + rec(i+1, j1+1, j2)
        bx = abs(pos - j2) * ai + rec(i+1, j1, j2-1)

        return max(ax, bx)

    print(rec(0, 0, N-1))

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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


def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(aii, index, left, right):
    res = 0
    ai, i = aii[index]
    if index == 0:
        return ai * abs(i-left)

    index -= 1
    # to leftmost
    res1 = ai * abs(i-left) + solve(aii, index, left+1, right)
    # to rightmost
    res2 = ai * abs(right-i) + solve(aii, index, left, right-1)
    return max(res1, res2)


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted((a[i], i)for i in range(n))
    print(solve(aii, n-1, 0, n-1))

Submission status: Time Limit Exceeded

Solution code:
def input_one_number():
    return int(input())

def input_multiple_number():
    return map(int, input().split())

def input_multiple_number_as_list():
    return list(map(int, input().split()))

N = input_one_number()
A = input_multiple_number_as_list()

#Aのindexつきのやつ
A2 = [[i,A[i]] for i in range(len(A))]

#元気さん順
A2.sort(key=lambda x:x[1],reverse=True)


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

def wkwk(a,x,y):
	return a*abs(x-y)


for i in range(1,N+1):
	dp[i][0] = dp[i-1][0]+wkwk(A2[i-1][1],A2[i-1][0],i-1)
	dp[0][i] = dp[0][i-1]+wkwk(A2[i-1][1],A2[i-1][0],N-i)

ans = 0
for first in range(1,N+1):
	for last in range(1,N+1-first):
		yoji_index = first+last-1
		dp[first][last] = max(dp[first-1][last]+wkwk(A2[yoji_index][1],A2[yoji_index][0],first-1),
								dp[first][last-1]+wkwk(A2[yoji_index][1],A2[yoji_index][0],N-last))
		ans = max(ans,dp[first][last])


print(ans)

Submission status: Time Limit Exceeded

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

#output
idx = np.argsort(-A)

dp = np.zeros((N+1, N+1), int)
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。

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

print(answer)

Submission status: Time Limit Exceeded

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

#output
idx = np.argsort(-A)

dp = np.zeros((N+1, N+1), int)
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。
for i in range(N):
    dp[i+1, 0] = dp[i, 0] + A[idx[i]]*(abs(idx[i]-i))
for j in range(N):
    dp[0, j+1] = dp[0, j] + A[idx[j]]*(abs(N-1-idx[j]-j))

for i in range(N):
    for j in range(N):
        if i+j+1 < N:
            dp[i+1, j+1] = max(dp[i, j+1]+A[idx[i+j+1]]*(abs(idx[i+j+1]-i)), dp[i+1, j] + A[idx[i+j+1]]*(abs(N-1-idx[i+j+1]-j)))

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

print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        if dp[i+1][j] == 0:
            d.appendleft((i+1,j))
        dp[i+1][j] = tmp
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        if dp[i][j+1] == 0:
            d.appendleft((i,j+1))
        dp[i][j+1] = tmp
        
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]
d = deque([(0,0)])
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
while(len(d)>0):
    i, j = d.pop()
    if i + j > N - 1:
        continue
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        d.appendleft((i+1,j))
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp > dp[i][j+1]:
        dp[i][j+1] = tmp
        d.appendleft((i,j+1))
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0][i] = dp[0][i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i][0] = dp[i-1][0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x][y]= max((k-x >= 0)*(dp[x-1][y] + (k-x)*val),
                     (N-y-k+1 >= 0)*(dp[x][y-1] + (N-y-k+1) * val))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

def rec(i, j):
    flag = False
    flag_ = False
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        flag = True
    tmp_ = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp_ > dp[i][j+1]:
        dp[i][j+1] = tmp_ if tmp_ > dp[i][j+1] else dp[i][j+1]
        flag_ = True
    if i + j == N - 1:
        return
    if flag:
        rec(i + 1, j)
    if flag_:
        rec(i, j + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
rec(0, 0)
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)