Problem:


Score : 500 points

Problem Statement

There are N children standing in a line from left to right. The activeness of the i-th child from the left is A_i.

You can rearrange these children just one time in any order you like.

When a child who originally occupies the x-th position from the left in the line moves to the y-th position from the left, that child earns A_x \times |x-y| happiness points.

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

If we move the 1-st child from the left to the 3-rd position from the left, the 2-nd child to the 4-th position, the 3-rd child to the 1-st position, and the 4-th child to the 2-nd position, the children earns 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 happiness points in total.

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Accepted

Solution code:
def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

    N = int(input())
    As = [(A, i) for i, A in enumerate(map(int, input().split()))]

    As.sort(reverse=True)

    dp = [[-INF]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for no, (A, pos) in enumerate(As):
        for i in range(no+1):
            j = no-i
            dp[i+1][j] = max2(dp[i+1][j], dp[i][j] + A*abs(pos-i))
            dp[i][j+1] = max2(dp[i][j+1], dp[i][j] + A*abs(pos-(N-1-j)))

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

    print(ans)


solve()

Submission status: Accepted

Solution code:
def examA():
    R = I()
    ans = R*2*3.141592
    print(ans)
    return

def examB():
    N, M = LI()
    A = LI()
    S = sum(A)
    if N>=S:
        ans = N-S
    else:
        ans = -1
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    ans = [0]*N
    for i in range(N-2,-1,-1):
        ans[A[i]-1] +=1
    for v in ans:
        print(v)
    return

def examD():
    N, K = LI()
    S = [0]*(N+2)
    for i in range(1,N+1):
        S[i+1] = S[i] + i
    #print(S)
    ans = 0
    for i in range(K,N+2):
        cur = (S[N+1] - S[N-i+1]) - (S[i] - S[0]) +1
        ans += cur
        ans %= mod
        #print(cur)

    print(ans)
    return

def examE():
    N = I()
    A = LI()
    S = [[]for _ in range(N)]
    for i in range(N):
        S[i] = [A[i],i]
    S.sort(reverse=True)
    #print(S)
    dp = [[0]*(N+1)for _ in range(N+1)]
    for i in range(N):
        s, x = S[i]
        for j in range(i+1):
            dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + s*(x-j))
            dp[i+1][j] = max(dp[i+1][j],dp[i][j] + s*(N-i-x+j-1))
            #print(N-i-x+j-1)
    ans = max(dp[-1])
    print(ans)
    #print(dp)
    return

def examF():
    N = I()
    C = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    ans = 0

    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
sa = [(a[i], i) for i in range(N)]
sa.sort(key = lambda x: (-x[0], -abs(x[1] - (N - 1) / 2)))
dp = [[0] * (N + 1) for _ in range(N + 1)]
for k in range(N):
  x, i = sa[k]
  for l in range(k + 1):
    r = k - l
    nr = N - 1 - r
    dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(l - i) * x)
    dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + abs(nr - i) * x)
res = 0
for l in range(N):
  r = N - l
  res = max(res, dp[l][r])
print(res)

Submission status: Accepted

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

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

dp = [[0]*(N+1) for _ in range(N+1)]
B = [(a, i) for i, a in enumerate(A)]
B.sort(reverse=True)

for l, (a, i) in enumerate(B):
    length = N-l
    for left in range(l+1):
        dp[left+1][left+length] = max(dp[left+1][left+length], dp[left][left+length] + a*abs(i-left))
        dp[left][left+length-1] = max(dp[left][left+length-1], dp[left][left+length] + a*abs(left+length-1-i))
ans = 0    
for n in range(N+1):
    ans = max(ans, dp[n][n])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [(a[i],i+1) for i in range(n)]
b.sort(reverse=True)
cntf = 0
cntb = n-1
dp = [[0 for i in range(n+1)] for j in range(n+1)]
dp[0][1] = -10**18
for i in range(1,n+1):
  x,ind = b[i-1]
  dp[i][0] = dp[i-1][0]+abs(n-i-ind+1)*x
  for j in range(1,i+1):
    dp[i][j] = max(dp[i-1][j-1]+abs(j-ind)*x,dp[i-1][j]+abs(n-(i-j)+1-ind)*x)
print(max(dp[n]))

Submission status: Accepted

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

al_id = [(a, idx) for idx, a in enumerate(al)]
al_id = sorted(al_id, reverse=True)
dp = [[-float("inf") for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
for count, (a, idx) in enumerate(al_id):
    for i in range(count+1):
        j = count - i
        dp[i+1][j] = max(dp[i][j] + abs(idx-i) * a, dp[i+1][j])
        dp[i][j+1] = max(dp[i][j] + abs(n-j-idx-1) * a, dp[i][j+1])


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

print(ans)

Submission status: Accepted

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

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

cnt = [0,n-1]

As = sorted(list(zip(A,range(n))), reverse = True)

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

# 配る
for i in range(n):
    for j in range(i+1):
        a,p = As[i]
        dp[i+1][j] = max(dp[i+1][j],dp[i][j] + a * (n-1 - p -i+j))
        dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j] + a * (p - j))

print(max(dp[n]))

Submission status: Accepted

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

ap = [(v, k) for k, v in enumerate(A)]
ap.sort(reverse=True)

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

for i, (a, p) in enumerate(ap) :
  for l in range(i + 1) :
    r = i - l
    if l + 1 <= N :
      dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + a * (p - l))
    if r + 1 <= N :
      dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a * (N - 1 - r - p))
  
print(max(dp[i][N - i] for i in range(N + 1)))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
sys.setrecursionlimit(10**6)
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
lis = [(e, i) for i, e in enumerate(a)]
lis.sort()
dp = [[-1]*n for _ in range(n)]

def solve(l, r):
    if l > r:
        return 0
    if dp[l][r] >= 0:
        return dp[l][r]
    idx = r - l
    e, i = lis[idx]
    dp[l][r] = max(abs(i-l)*e + solve(l+1, r), abs(r-i)*e + solve(l, r-1))
    return dp[l][r]

print(solve(0, n-1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import os
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


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

order = argsort(A)[::-1]
dp = [defaultdict(int) for _ in range(N + 1)]
l = 0
r = N - 1
dp[0][l, r] = 0
for i, p in enumerate(order):
    for (l, r), v in dp[i].items():
        dp[i + 1][l + 1, r] = max(dp[i + 1][l + 1, r], v + A[p] * abs(p - l))
        dp[i + 1][l, r - 1] = max(dp[i + 1][l, r - 1], v + A[p] * abs(p - r))
print(max(dp[-1].values()))

Submission status: Accepted

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:
import numpy as np
N = int(input())
A = np.array([int(x) for x in input().split()])
B = range(N)
left = 0
right = N-1
score = 0
for i in range(N-1):
  val = np.max(A)
  pos = B[np.argmax(A)]
  if (pos-left)>(right-pos):
    score+=val*(pos-left)
    left +=1
  else:
    score+=val*(right-pos)
    right -=1
  A=np.delete(A, pos)
  B=np.delete(B, pos)
print(score)

Submission status: Runtime Error

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    anumlist = []
    for i in range(n):
        anumlist.append([a[i], i])
    anumlist.sort(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] + anumlist[i + j][0] * (anumlist[i + j][1] - i))
            dp[i][j + 1] = max(dp[i][j+1],dp[i][j] + anumlist[i + j][0] * ((n - 1 - j) - anumlist[i + j][1]))
            
    ans = 0
    for i in range(n+1):
        ans = max(ans, dp[i][n - i])
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Runtime Error

Solution code:
import sys
import time

t = time.time()

n = int(input())
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))
# print(time.time()-t)

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


# sys.setrecursionlimit(2010)
print(dfs(0, n-1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


print(dfs(0, n-1))

Submission status: Runtime Error

Solution code:
N = int(input())
infants = []
for i, A in enumerate(map(int, input().split(' '))):
    infants.append((-A, i + 1))
infants.sort()
dp = [{} for _ in range(N)]


def search(i, l):
    # i番目の幼児を見ていて左にl人配置している
    if i == N:
        return 0
    if l in dp[i]:
        return dp[i][l]
    (act_val, pos) = infants[i]
    act_val = -act_val
    ans = max(search(i + 1, l + 1) + abs(l + 1 - pos) * act_val,
              search(i + 1, l) + abs(N - i + l - pos) * act_val)
    dp[i][l] = ans
    return ans


print(search(0, 0))

Submission status: Runtime Error

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    sortedA = sorted(A[[a,i] for i,a in enumerate(A)], reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][0]*abs((N-r-1)-sortedA[i][1]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][0]*abs(l-sortedA[i][1]))
    print(max(dp[N]))

main()

Submission status: Runtime Error

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

li1 = [i+1 for i in range(N)]
li2 = []
counter = 0

dp =[[0 for i in range(N)] for k in range(N)]
#dp[i][k] を　インデックス番号i からkに移動したときの得点とする

for i in range(N):
    for k in range(N):
        dp[i][k] = A[i]*max(i-k,k-i)

dp = np.array(dp)
i=0
k=0
counter = 0
for u in range(N):
    i,k = np.where(dp==dp.max())
    counter += dp.max()
    arr=np.delete(dp,i,0)
    dp=np.delete(arr,k,1)
print(counter)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
A_=list(map(int,input().split()))

N_list=[(j+1,k) for j,k in enumerate(A_)]
max_list=[]

for k in list(range(1,N+1)).reverse():
  for i in range(1,k):
    z=[math.abs(tup[0]-k)*tup[1] for tup in N_list]
    max_val=max(z)
    max_index=z.index(max_val)
    max_list.append(max_val)
    N_list.pop(max_index)
    
print(sum(max_list))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
import pysnooper # @pysnooper.snoop() # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class Solver:

    def __init__(self, n, students):
        self.n = n
        self.students = students
        self.ordered = self.make_ordered() # var[i] = (active, pos), dec ordered
        self.dp = self.make_dp_container() # var[l][r] = max ans

    def make_ordered(self):
        ordered = [None] * self.n
        for i, active in enumerate(self.students):
            pos = i
            #pos = i + 1
            ordered[i] = (active, pos)
        ordered = sorted(ordered, key=lambda tpl: tpl[0])
        ordered = list(reversed(ordered))
        return ordered

    def make_dp_container(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [0] * (self.n + 1)
        return dp

    def run(self):
        for s, (active, pos) in enumerate(self.ordered):
            for l in range(s + 1):
                v = active * abs(pos - l)
                self.update(s + 1, l + 1, self.dp[s][l] + v)
                r = s - l
                r_key = self.n - 1 - r
                v = active * abs(pos - r_key)
                self.update(s + 1, l, self.dp[s][l] + v)
        #print('self.dp') # debug
        #print(self.dp) # debug
        ans = max(self.dp[-1])
        return ans

    def update(self, s, l, value):
        self.dp[s][l] = max(self.dp[s][l], value)


if __name__ == '__main__':
    n = int(input())
    students = list(map(int, input().split()))
    ans = Solver(n, students).run()
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Runtime Error

Solution code:
#  入力
N = int(input())
B = [int(x) for x in input().split()]

# 初期化
dp = [[0] * (N+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(0,N):

    # 最も嬉しさの高い子供から場所を選択していく
    id = A.index(max(A))
    
    for x in range(0,i+1):
        y = i - x
        
        dp[x+1][y] = max(dp[x+1][y], dp[x][y] + A[id] * (id - x))
        dp[x][y+1] = max(dp[x][y+1], dp[x][y] + A[id] * (((N-1)-y) - id))
        
    A[id] = 0

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

Submission status: Runtime Error

Solution code:
import copy

n=int(input())
a0=input().split()
al=[int(a) for a in a0]
left0=[x for x in range(n)]

def max(l,left,hp):
  if left==[]:
    return hp
  else:
    re=0
    rel=[]
    nextp=len(l)#0--n-1
    for x in left:
      l2=copy.deepcopy(l)
      left2=copy.deepcopy(left)
      l2.append(x)
      left2.remove(x)
      hp2=hp+al[x]*abs(x-nextp)
      newhp=max(l2,left2,hp2)
      if re<newhp:
        re=newhp
    return re
        
hpz=max([],left0,0)
print(hpz)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <tuple>
#include <random>
#include <unordered_map>
#include <unordered_set>
using namespace std ;

int main() {
    int N ;
    long long int power; 
    cin >> N ;
    
    vector<pair<long long int, int>> active(N) ;
    for (int i=0;i<N;i++) {
        cin >> power ;
        active[i] = make_pair(power, i+1) ;     
    }
    sort(active.begin(), active.end()) ;
    reverse(active.begin(), active.end()) ;
    
    vector<vector<long long int>> dp(N+1, vector<long long int>(N+1, 0) ) ;
    for (int l=1;l<=N;l++) {
        pair<int, int> a = active[l-1];
        for (int i=0;i<l;i++) {
            dp[l-i][i] = max( dp[l-i][i], dp[l-i-1][i]+abs(l-i-a.second)*a.first );
            dp[i][l-i] = max( dp[i][l-i], dp[i][l-i-1]+abs(N+1-l+i-a.second)*a.first );  
        }
    }
    long long int ans = 0;
    for (int i=0;i<=N;i++) 
        ans = max(ans, dp[i][N-i]) ;
    cout << ans ;
}

Submission status: Runtime Error

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1], reverse=True)

for i in range(n):
    a[i][0] = a[i][0] + 1

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    DP[0][i] = DP[0][i-1] + abs(a[i-1][1] * (n - i + 1 - a[i-1][0]))
    DP[i][0] = DP[i-1][0] + abs(a[i-1][1] * (a[i-1][0] - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(a[i-1][1] * (a[i-1][0] - x)),  \
            DP[x][y-1] + abs(a[i-1][1] * (n - y + 1 - a[i-1][0])))

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

print(ans)

Submission status: Runtime Error

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

a = [(i, ai) for i, ai in enumerate(A)]
a = sorted(key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

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

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

Submission status: Runtime Error

Solution code:
def dp(x, y, curr):
	if len(l) <= x + y:
		return curr
	v, pos = l[x + y]
	return max([
		dp(x + 1, y, curr + v * (pos - (x + 1) )),
		dp(x, y + 1, curr +  v * (len(l) - y - pos))])
  
n = int(input())
l = [ (y, x + 1)  for  x, y in  enumerate(map(int, input().split(" "))) ]
l = sorted(l, reverse=True)

print(dp(0, 0, 0))

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
B = [[] for _ in range(N)]
for i, A in enumerate(input().split()):
    for j in range(N):
        B[j].append(int(A)*abs(i-j))
# print(B)
S = 0
while B != []:
    for i in range(len(B)):
        n = np.argmax(B[i])
        if np.argmax(np.array(B).T.tolist()[n]) == i:
            S += B[i][n]
            for j in range(len(B)):
                del B[j][n]
            del B[i]
print(S)

Submission status: Runtime Error

Solution code:
import sys

def calc(A, j, L, R):
    a, i = A[j]
    J = j + 1
    if L == R:
        s = a * abs(L - i)
    else:
        s = a * abs(L - i) + calc(A, J, L + 1, R)
        t = a * abs(R - i) + calc(A, J, L, R - 1)
        if s < t:
            s = t
    return s


def main():
    N = int(input())

	sys.setrecursionlimit(N + 10)

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

    print(calc(A, 0, 0, N - 1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import functools

input()

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


@functools.lru_cache(maxsize=None)
def dp(l, r, idx):
    if idx == len(arr):
        return 0

    left = abs(arr[idx][1] - l) * arr[idx][0] + dp(l + 1, r, idx + 1)
    right = abs(arr[idx][1] - r) * arr[idx][0] + dp(l, r - 1, idx + 1)

    return max(left, right)


print(dp(0, len(arr) - 1, 0))

Submission status: Runtime Error

Solution code:
import numpy as np
 
N = int(input())
A_list = map(int, input().split())
 
# [活発度, もとの番号] のリストを降順に並べる
A_list = [[A, index] for index, A in enumerate(A_list)]
A_list.sort(reverse=True)
 
# print(A_list)
 
dp = np.zeros((N+2, N+2), int)
# print(dp)
for left in range(0, N):
    for right in range(0, N - left):
        # print(f'left, righte: { left, right }')
        # print(A_list[left + right - 1][0])
        activity = A_list[left + right][0]
        distance_from_left = A_list[left + right][1] - left
        # print(f'distance_from_left: { distance_from_left }')
        distance_from_right = (N - 1 - right) - A_list[left + right][1]
        # print(f'distance_from_right: { distance_from_right }')
        dp[left + 1][right]\
            = max(dp[left + 1][right],
                  dp[left][right] + activity * distance_from_left)
        dp[left][right + 1]\
            = max(dp[left][right + 1],
                  dp[left][right] + activity * distance_from_right)
        # print('dp---')
        # print(dp)
        # print('---dp')
# print(dp)
print(np.max(dp))

Submission status: Runtime Error

Solution code:
# At code
def DFS(deep,ret):
    global N, a, use, num_list, result
    if deep == N:
        if ret > result:
            ret, result = result, ret
        return

    for i in range(0, N):
        if use[i] != 1:
            num_list[deep] = a[i]
            use[i] = 1
            DFS(deep + 1, ret + a[i]*abs(deep - i))
            use[i] = 0


if __name__ == "__main__":
    N = int(input())
    a = list(map(int, input().split(' ')))
    use = [0 for i in range(len(a))]
    num_list = [0 for i in range(len(a))]
    result = 0
    DFS(0, 0)
    print(result)

Submission status: Runtime Error

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][0] = DP[x-1][0] + baby * abs(pos-x+1))
        DP[0][y] = DP[x][y-1] + baby * abs(pos-(N-y))
        if x & y:
            DP[x][y] = max((DP[x-1][y] + baby * abs(pos-x+1)),\
                     (DP[x][y-1] + baby * abs(pos-(N-y)))

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

Submission status: Runtime Error

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 = {}
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)
  else:
    dp[ln, rn] = 0

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

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)

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

Solution code:

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

def cal(i, dst):
  if i == -1:
    return 0

  result = None
  for j in dst:
    next_dst = [v for v in dst if v != j]
    val = arr[i] * abs(i - j) + cal(i - 1, next_dst)
    result = max(result, val) if result else val

  return result

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

Submission status: Runtime Error

Solution code:
import copy

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


def cal(i, dst):
  if i == -1:
    return 0

  result = None
  for j in range(n):
    if dst[j]:
      continue
    dst[j] = i
    val = arr[i] * abs(i - j) + cal(i - 1, dst)
    dst[j] = None
    result = max(result, val) if result else val

  return result

print(cal(n - 1, [None for _ in range(n)]))

Submission status: Runtime Error

Solution code:
import copy

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


def cal(i, dst):
  if i == -1:
    return 0

  results = []
  for j in range(n):
    if dst[j]:
      continue
    dst[j] = i
    val = arr[i] * abs(i - j)
    results.append(val + cal(i - 1, dst))
    dst[j] = None

  return max(results)

print(cal(n - 1, [None for _ in range(n)]))

Submission status: Runtime Error

Solution code:
import copy

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


def cal(i, dst):
  if i == -1:
    return 0

  results = []
  for j in range(n):
    if dst[j]:
      continue
    next_dst = copy.deepcopy(dst)
    next_dst[j] = i
    val = arr[i] * abs(i - j)
    results.append(val + cal(i - 1, next_dst))

  return max(results)

print(cal(n - 1, [None for _ in range(n)]))

Submission status: Runtime Error

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)] for _ in range(n)]
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: Runtime Error

Solution code:
from functools import lru_cache

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

Solution code:
import sys
sys.setrecursionlimit(2 ** 2000)
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
a = [(i, v) for i, v in enumerate(a)]
a.sort(key=lambda x: x[1], reverse=True)

dp = [[-1] * (m + 1) for m in range(n + 1)]
# m: 何人選んだか, l: 左を選んだ人数
def f(m, l):
    if m == n: return 0
    if dp[m][l] != -1: return dp[m][l]
    r = n - m + l - 1
    i, v = a[m]
    if i >= l: dp[m + 1][l + 1] = f(m + 1, l + 1)
    if i <= r: dp[m + 1][l] = f(m + 1, l)
    return max(dp[m + 1][l + 1] + v * (i - l), dp[m + 1][l] + v * (r - i))
print(f(0, 0))

Submission status: Runtime Error

Solution code:
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, pd)]

print(max(prev))

Submission status: Runtime Error

Solution code:
N = int(input())

def solve(a, i, prev):
  r = N - len(prev) - i + 1
  p = -i*a
  for j, s in enumerate(prev):
    yield max(p+abs(j-i)*a, s+abs(j+r)*a)
    p = s
  yield s+abs(len(prev)-i)*a

pd = [0]
A = map(int, input().split())
for a,i in sorted(((a, i) for i, a in enumerate(A, 1)), reverse=True):
  pd = [*solve(a,i, prev)]

print(max(prev))