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: Runtime Error

Solution code:
from operator import itemgetter as get
N = int(input())

A = map(int, input().split())
SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

def solve(a, i, prev, th):
  pl, pr, ps = 0, -1, 0
  for l, r, s in prev:
    if s < th:
      continue
    if pr == r-1:
      yield l, r-1, max(s+abs(r-i)*a, ps+abs(i-pl)*a)
    else:
      if pl:
        yield pl+1, pr, ps+abs(i-pl)*a
      yield l, r-1, s+abs(r-i)*a
    pl, pr, ps = l, r, s
  yield pl+1, pr, ps+abs(i-pl)*a

prev = [(1, N, 0)]
pm = 0
for j, (a,b,i) in enumerate(ABI):
  M = 0
  prev = [(M:=max(M,s)) and (l, r, s) for l, r, s in solve(a,i, prev, pm-SB)]
  pm = M
  SB -= b

print(pm)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
lst = [i for i in range(n)]
start = 0
end = n-1
max_happy = 0
for _ in range(n):
  m = 0
  for j in lst:
    if abs(j - start) > abs(j - end):
      happy = a[j] * abs(j - start)
      idx = 0
    else:
      happy = a[j] * abs(j - end)
      idx = 1
    if happy > m:
      m = happy
      m_idx = idx
      m_point = j
  max_happy += m
  lst.remove(m_point)
  if m_idx == 0:
    start += 1
  else:
    end -= 1
print(max_happy)

Submission status: Runtime Error

Solution code:
N = int(input())
A = np.array(list(map(int,input().split())))
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a, i) in enumerate(ABI)
    curr = [0]*(k+2)
    for l in range(k+1):
        curr[l] = max(curr[l], prev[l] + a*abs(N-i-(k-l)))
        curr[l+1] = prev[l]+a*abs(i-l-1)
    prev = curr
print (max(prev))

Submission status: Runtime Error

Solution code:
def func(a_list, index_list):

    if len(a_list) == 0:
        score = 0
    else:
        i,x = a_list.pop()
        hoge = []
        for j in index_list:
            tmp = index_list.copy()
            tmp.pop(tmp.index(j))
            hoge.append(x*abs(i-j)+func(a_list.copy(), tmp))

        score = max(hoge)

    return score

def slove(n, k):
    a_list = sorted([(i, int(x)) for i,x in enumerate(k.split(), 1)],
                    key= lambda x:x[1], reverse=True)
    index_list = list(range(1,n+1))
    a = func(a_list, index_list)
    return a

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

Submission status: Runtime Error

Solution code:
from copy import deepcopy

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

index = [i for i in range(N)]
index = sorted(index, key=lambda i: A[i], reverse=True)


def LorR(index, res):
    i = index[0]
    dist = max(i, N - 1 - i)
    end = False
    cand1 = cand2 = 0
    while not end:
        j = i + dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand1 = A[i] * dist + loop(index[1:], r)
            end = True

        j = i - dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand2 = A[i] * dist + loop(index[1:], r)
            end = True

        dist -= 1
    return max(cand1, cand2)


def loop(index, res):
    if not index:
        return 0

    return LorR(index, res)


print(loop(index, [False] * N))

Submission status: Runtime Error

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

#output
import numpy as np    
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
def rec(i,j):
    if i + j == N:
        return
    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
    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]
    if tmp > dp[i+1][j]:
        rec(i + 1, j)
    if tmp_ > dp[i][j+1]:
        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)] for _ in range(N)]
rec(0, 0)
ans = -1
for i in range(4):
    for j in range(4):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(v, i) for i, v in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i, (a, b) in enumerate(AA, start=1):
        for x in range(i+1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x-1][y] + abs(b - x+1) * a
            elif x == 0:
                dp[x][y] = dp[x][y-1] + abs(N-y-b) * a
            else:
                dp[x][y] = max(dp[x-1][y] + abs(b - x + 1) * a, dp[x][y-1] + abs(N-y-b) * a)
    for i in range(N+1):
        r = max(r, dp[i][N-i])
    return r
print(main())

Submission status: Runtime Error

Solution code:
from copy import deepcopy

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

index = [i for i in range(N)]
index = sorted(index, key=lambda i: A[i], reverse=True)

print(A)
print(index)


def LorR(index, res):
    i = index[0]
    dist = max(i, N - 1 - i)
    end = False
    cand1 = cand2 = 0
    while not end:
        j = i + dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand1 = A[i] * dist + loop(index[1:], r)
            end = True

        j = i - dist
        if 0 <= j and j < N and not res[j]:
            r = deepcopy(res)
            r[j] = True
            cand2 = A[i] * dist + loop(index[1:], r)
            end = True

        dist -= 1
    return max(cand1, cand2)


def loop(index, res):
    if not index:
        return 0

    num = 0
    a = A[index[0]]
    while num < len(index) and A[index[num]] == a:
        num += 1

    cand = [0] * num
    for i in range(num):
        ind = deepcopy(index)
        head = ind.pop(i)
        ind.insert(0, head)
        cand[i] = LorR(ind, res)

    return max(cand)


print(loop(index, [False] * N))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

def rec(i,j,k):
    if k == N or i == N - 1 or j == N - 1:
        return
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        rec(i + 1, j, k + 1)
    tmp = dp[i][j] + A[k][0] * abs(A[k][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]
        rec(i, j + 1, k + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

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

Submission status: Runtime Error

Solution code:
def rec(i,j,k):
    if k == N or i == N - 1 or j == N - 1:
        return
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        rec(i + 1, j, k + 1)
    tmp = dp[i][j] + A[k][0] * abs(A[k][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]
        rec(i, j + 1, k + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

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

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10000)
@lru_cache(maxsize = None)
def rec(i,j,k):
    if k == N or i == N - 1 or j == N - 1:
        return
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - i)
    dp[i+1][j] = tmp if tmp > dp[i+1][j] else dp[i+1][j]
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - N + j + 1)
    dp[i][j+1] = tmp if tmp > dp[i][j+1] else dp[i][j+1]
    rec(i + 1, j, k + 1)
    rec(i, j + 1, k + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

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

Submission status: Runtime Error

Solution code:
def rec(i,j,k):
    if k == N or i == N - 1 or j == N - 1:
        return
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - i)
    dp[i+1][j] = tmp if tmp > dp[i+1][j] else dp[i+1][j]
    tmp = dp[i][j] + A[k][0] * abs(A[k][1] - N + j + 1)
    dp[i][j+1] = tmp if tmp > dp[i][j+1] else dp[i][j+1]
    rec(i + 1, j, k + 1)
    rec(i, j + 1, k + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

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

Submission status: Runtime Error

Solution code:
n = int(input())
l = map(int, input().split())
r = 0
left, right = 0, n-1
while left <= right:
  m = max(l)
  p = l.index(m)
  l[p] = -1
  if abs(p-left) < abs(p-right):
    r += m*abs(p-left)
    left += 1
  else:
    r += m*abs(p-right)
    right -= 1

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np

def solve(N: int, A: "List[int]"):
    a=np.argsort(A)[::-1]

    dp = np.zeros((N+1,N+1), dtype=np.int)
    for i, a_ind in enumerate(a):
        x_p_y = i+1
        a_ = A[a_ind]
        # print("a_ : {}, a_ind : {}".format(a_, a_ind))
        for x in range(0, x_p_y+1):
            y = x_p_y - x
            if x-1<0: x_add = 0
            else : x_add = dp[x-1, y] + a_*abs(a_ind-x+1)
            if y-1<0: y_add = 0
            else : y_add = dp[x, y-1] + a_*abs(N-y - a_ind)
            dp[x, y] = max(x_add, y_add)
    print(np.max(dp))

    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
 
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    
  prev = curr
 
print(max(prev))

Submission status: Runtime Error

Solution code:
N = int(input())
 
A = [int(s) for s in input().split(" ")]
ABI = sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True)
prev = [0]
for k, (a,i) in enumerate(ABI):
  curr = [0]*(k+2)
  for l in range(k+1):
    curr[l] = max(curr[l], prev[l]+abs(N-i-k+l)*a)
    curr[l+1] = prev[l]+abs(i-l-1)*a
    print(curr,k,i)
  prev = curr
 
print(max(prev))

Submission status: Runtime Error

Solution code:
import numpy as np
import math
import itertools
n = int(input())
l = list(map(int, input().split()))
ans = 0
pos = [0] * n
for i in range(n):
    pos[i] = list(map(lambda x: abs(x - i), list(range(n))))
pos = np.array(pos)
tot = np.zeros(math.factorial(n))
for i in range(n):
    pos[i, :] = pos[i, :] * l[i]
for i, x in enumerate(itertools.permutations(range(n))):
    tot[i] = np.sum(pos[list(range(n)), x])
print(int(np.max(tot)))

Submission status: Runtime Error

Solution code:
from collections import *
from itertools import *

N = int(input())

A = map(int, input().split())
SA = SB = 0
ABI = sorted(((b:=max(N-i, i-1)*a, SA:=SA+a, SB:=SB+b) and (a, b, i) for i, a in enumerate(A, 1)), reverse=True)

prev = {0:0}
prev_max = 0
for k, (a, b, i) in enumerate(ABI):
  curr = defaultdict(int)
  for l, p in prev.items():
    r = k-l
    if p + SB - (k-1)*SA < prev_max:
      continue
    curr[l] = max(curr[l], p+abs(N-i-r)*a)
    curr[l+1] = p+abs(i-l-1)*a
  SA -= a
  SB -= b
  prev = curr
  prev_max = max(prev.values())

print(prev_max)

Submission status: Runtime Error

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

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))
print(champ)

Submission status: Runtime Error

Solution code:
#At Coder E: Active Infants

import random
N = 10
A = [random.randrange(1,10) for n in range(N)]

f = [n for n in range(N)]
ans = 0

for n in range(N):
    a = sA.pop()
    print(a,sA)
    i = A.index(a)
    if i - f[0] > f[-1] - i:
        ans += (i-f.pop(0)) * a
    else:
        ans += (f.pop()-i) * a

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
aj = [a[0]]
for i in range(1,n-1):
    if a.index(b[i]) < n/2:
        aj += [b[i]]
    else:
        aj = [b[i]]+aj
if aj[0] == b[n-1]:
    aj += [b[n]]
else:
    aj = [b[n]]+aj

ans = 0
for i in range(n):


print(ans)

Submission status: Runtime Error

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


@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: Runtime Error

Solution code:
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=dict()
for i in range(n):
    if a[i] not in place:
        place[a[i]]=[i+1]
    else:
        place[a[i]].append(i+1)
ans = 0
dp=[[-INF]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
    if i!=0 and sorted_a[i] == sorted_a[i - 1]:
        index += 1
    else:
        index = 0
    for j in range(n):
        _place = place[sorted_a[i]][index]
        #右
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + sorted_a[i] * abs(n - (i - j) - _place))
        #左
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + sorted_a[i] *  abs(_place - j - 1))

print(max(dp[n]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
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: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [1, 3, 4, 2]
# n = 6
# A = [5, 5, 6, 1, 1, 1]
# n = 6
# A = [8, 6, 9, 1, 2, 1]
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: Runtime Error

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

Submission status: Runtime Error

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

a.sort()
dp = [[-1]*n for _ in range(n)]

def recursive(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    energy, pos = a[k]
    from_l = energy * abs(l - pos)
    from_r = energy * abs(r - pos)
    ans = dp[l][r] = max(from_l + recursive(l+1, r), from_r + recursive(l, r-1))
    return ans

print(recursive(0, n-1))

Submission status: Runtime Error

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

a.sort()
dp = [[-1]*n for _ in range(n)]

def recursive(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    k = r - l
    energy, pos = a[k]
    from_l = energy * abs(l - pos)
    from_r = energy * abs(r - pos)
    dp[l][r] = max(from_l + recursive(l+1, r), from_r + recursive(l, r-1))
    return dp[l][r]

print(recursive(0, n-1))

Submission status: Runtime Error

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):
    =ds[x,N-x]
    ans=max(c,ans)
print(ans)
#print(ds)
#print(inds)

Submission status: Runtime Error

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

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

print(solve(0, N-1))

Submission status: Runtime Error

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

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

print(solve(0, N-1))

Submission status: Runtime Error

Solution code:
#他人のコードです
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
N = int(readline())
A = np.array(read().split(), np.int64)
I = np.argsort(A)[::-1].tolist()
A = A[I].tolist()
 
dp = np.zeros(1, np.int64)
 
for n, (i, x) in enumerate(zip(I, A)):
    newdp = np.zeros(len(dp) + 1, np.int64)
    left_ind = np.arange(len(dp))
    right_ind = N - 1 - n + left_ind
    left_cost = x * np.abs(left_ind - i)
    right_cost = x * np.abs(right_ind - i)
    np.maximum(newdp[:-1], dp + right_cost, out=newdp[:-1])
    np.maximum(newdp[1:], dp + left_cost, out=newdp[1:])
    dp = newdp
 
print(dp.max())

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))
import copy

def maxmize(members, seats):
    if seats == []:
        return 0
    else:
        saidai = max(members)
        saidai_index = members.index(saidai)
        newmembers = copy.deepcopy(members)
        newmembers[saidai_index] = 0
        
        right = maxmize(newmembers,seats[:-1]) + saidai * abs(saidai_index - seats[-1])
        left = maxmize(newmembers,seats[1:]) + saidai * abs(saidai_index - seats[0])                                                      
        
        
    return max(left,right)

givenseats = [j for j in range(n)]
maxmize(li, givenseats)

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))
import copy

def maxmize(members, seats):
    if seats == []:
        return 0
    else:
        saidai = max(members)
        saidai_index = members.index(saidai)
        newmembers = copy.deepcopy(members)
        newmembers[saidai_index] = 0
        right = maxmize(newmembers,seats[:-1]) + saidai * abs(saidai_index - seats[-1])
        left = maxmize(newmembers,seats[1:]) + saidai * abs(saidai_index - seats[0])                                                      
    return max(left,right)

givenseats = [j for j in range(n)]
maxmize(li, givenseats)

Submission status: Runtime Error

Solution code:
n = int(input())
li = list(map(int,input().split()))
import copy

def maxmize(members, seats):
    if seats == []:
        return 0
    else:
        saidai = max(members)
        saidai_index = members.index(saidai)
        newmembers = copy.deepcopy(members)
        newmembers[saidai_index] = 0
        #print("members",members)
        #print("seats",seats[:-1])
        #print("saidai",saidai)
        #print("hoge",abs(saidai_index - seats[-1]))
        right = maxmize(newmembers,seats[:-1]) + saidai * abs(saidai_index - seats[-1])
        left = maxmize(newmembers,seats[1:]) + saidai * abs(saidai_index - seats[0])                                                      
        
        #print(left,right)
    return max(left,right)

givenseats = [j for j in range(n)]
maxmize(li, givenseats)

Submission status: Runtime Error

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

A_mat = []
for i,A in enumerate(As):
    A_mat.append([A,i])

A_mat.sort(reverse=True)

map1 = []

for i in range(N+1):
    temp = [-1]*(N+1)
    map1.append(temp)



def DP(x, y): #Asのなかからx+y個の数列をすでに端に移動していて、x個左端に, y個右端に移動している状態から始めたときに追加で得られるスコア
    if map1[x][y]>=0:
        return map1[x][y]
    
    if x+y == N:
        return 0

    a_val = A_mat[x+y][0]
    a_pos = A_mat[x+y][1]

    left_case = abs(a_pos-x)
    right_case = abs((N-y-1)-a_pos)

    map1[x][y] = max(DP(x+1,y)+left_case*a_val, DP(x,y+1)+right_case*a_val)

    return map1[x][y]

print(DP(0,0))

Submission status: Runtime Error

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

B = A
ans = 0
a = 0

for i in range(N-1):
      c = max(B)
      R = list(reversed(B))
      if (B.index(c)-(N-i)/2)*c > (R.index(c)-(N-i)/2)*c:
            if (N-i-B.index(c))>B.index(c):
                  ans+=(a+N-i-B.index(c))*c
            else:
                  ans+=B.index(c)*c
                  a+=1
            B.pop(B.index(c))
      else:
            if (N-i-R.index(c))>R.index(c):
                  ans+=(a+N-i-R.index(c))*c
            else:
                  ans+=R.index(c)*c
                  a+=1
            B.pop(N-i-R.index(c))

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
ans = 0
minN = 0
maxN = N-1
flag = [1]*N
    
for i in range(N):
    maxpr = 0
    maxj = 0
    flagj = 0
    for j in range(N):
        if flag[j]:
            if maxN - j >= j - minN and A[j]*(maxN - j) > maxpr:
                maxpr = A[j]*(maxN - j)
                maxj = j
                flagj = 1
            elif  maxN - j <= j - minN and A[j]*(j - minN) > maxpr:
                maxpr = A[j]*(j - minN)
                maxj = j
                flagj = 0
    
    flag[maxj] = 0
    if flagj:
        maxN -= 1
    else:
        minN += 1
    ans += maxpr
    
print(ans

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[i for i in range(N)]#移し替えた後の並び
dp2=[i for i in range(N)]#i番めの人の行く先

for i in range(1,N):
  max=0
  maxj=i
  for j in range(i):
    if A[i]*abs(i-dp2[j])+A[j]*abs(j-dp2[i])-A[i]*abs(i-dp2[i])-A[j]*abs(j-dp2[j])>max:
      max=A[i]*abs(i-dp2[j])+A[j]*abs(j-dp2[i])-A[i]*abs(i-dp2[i])-A[j]*abs(j-dp2[j])
      maxj=j
  z=dp[maxj]
  dp[maxj]=dp[i]
  dp[i]=z
  z1=dp2.index(i)
  z2=dp2.index(maxj)
  z=dp2[dp[maxj]]
  dp2[dp[maxj]]=dp2[dp[i]]
  dp2[dp[i]]=dp2[dp[maxj]]

ans=0    
for i in range(N):
  ans+=abs(i-dp2[i])*A[i]
print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = [0 for _ in range(n)]

score = 0
for i in range(n):
    l = s.index(0)
    r = n - 1 -s[::-1].index(0)
    #right
    score_r, score_l = score, score
    sr, sl = s.copy(), s.copy()
    if r >= i:
        sr[r] = a[i]
        score_r += a[i] * (r - i)
        while r < n-1 and sr[r] > sr[r+1]:
            score_r += sr[r] - sr[r+1]
            sr[r], sr[r+1] = sr[r+1], sr[r]
            r += 1

    if l <= i:
        sl[l] = a[i]
        score_l += a[i] * (i - l)
        while l > 0 and sl[l-1] < sl[l]:
            score_l += sl[l] - sl[l-1]
            sl[l-1], sl[l] = sl[l], sl[l-1]
            l += 1

    if score_r >= score_l:
        score = score_r
        s = sr

    else:
        score = score_l
        s = sl


print(score)
#print(s)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
a= list(map(int,input().split()))
score=np.array(a)
b=np.sort(score)
c=b[-1::-1]
#print(c)
x=np.argsort(a)
y=x[-1::-1]
#print(y)

#c:score、y:index
cand=list(range(N))

count=0
for i in range(N):
    if (y[i]-cand[0])>(cand[-1]-y[i]):
        count+=c[i]*abs(y[i]-cand[0])
        cand.pop(0)
    elif (y[i]-cand[0])<(cand[-1]-y[i]):
        count+=c[i]*abs(cand[-1]-y[i])
        cand.pop(-1)
    else:
        if y[i+1]>y[i]:
            count+=c[i]*abs(y[i]-cand[0])
            cand.pop(0)
        else:
            count+=c[i]*abs(cand[-1]-y[i])
            cand.pop(-1) 

print(count)

Submission status: Runtime Error

Solution code:
import itertools

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

def make_key(select):
    key = ''
    for i in select:
        key += str(i)
    return key

dp = {}
def f(select):
    try:
        key = make_key(select)
        return dp[key]
    except KeyError:
        if len(select) == 1:
            return 0
        if len(select) == 2:
            i, j = select
            return abs(i - j) * (a[i] + a[j])
        happy = 0
        for i, j in itertools.combinations(select, 2):
            tmp = abs(i - j) * (a[i] + a[j]) + f(select - {i, j})
            happy = max(tmp, happy)
        key = make_key(select)
        dp[key] = happy
        return happy

select = set([i for i in range(n)])
print(f(select))