Problem:


Score : 500 points

Problem Statement

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

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

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

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

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

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

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

memo = {}

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

Submission status: Time Limit Exceeded

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

from itertools import permutations

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

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

print(max(scores))

Submission status: Time Limit Exceeded

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

scores = [[0 for _ in range(n)] for _ in range(n)] # score[index][baby_id]

for baby_id in range(n):
  for index in range(n):
    scores[index][baby_id] = ass[baby_id]*abs(index - baby_id)
 
predic = {():0}
for index in range(n):
  dic = {}
  for i in range(n):
    for key in predic.keys():
      if i in key:
        continue
      else:
        nkey = tuple(sorted(list(key) + [i]))
        if nkey not in dic:
          dic[nkey] = predic[key] + scores[index][i]
        else:
          if dic[nkey] < predic[key] + scores[index][i]:
            dic[nkey] = predic[key] + scores[index][i]
  predic = dic
print(dic[tuple([i for i in range(n)])])

Submission status: Time Limit Exceeded

Solution code:
import itertools 

N = int(input())
A = list(map(int, input().split()))
ureshisa = [
            [A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
  maxV = max(maxV, sum([ureshisa[P[i]][i] for i in range(N)]))
print(maxV)

Submission status: Time Limit Exceeded

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


def f(v):
    sorted_v = sorted(v)
    c = Counter(v)
    happy = 0
    for key in c.keys():
        v_idx = [n for n, i in enumerate(v) if i == key]
        sorted_v_idx = [n for n, i in enumerate(sorted_v) if i == key]
        move_idx = 0
        for i, j in zip(v_idx, sorted_v_idx):
            move_idx += j - i
        move_idx += (N - len(v)) * len(v_idx)
        happy += move_idx * key
    return happy


ans = 0
for i in range(1, N):
    l = A[:i]
    r = A[i:][::-1]
    # print('l, r', l, r, f(l), f(r))
    ans = max(ans, f(l) + f(r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a_sort = sorted(a)
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang, pos):
    lb_rang = 0
    ub_rang = len(rang) - 1
    lb_pos = 0
    ub_pos = len(pos) - 1
    ret= 0 
    while lb_rang <= ub_rang:
        if abs(rang[lb_rang]-pos[ub_pos]) < abs(rang[ub_rang]-pos[lb_pos]):
            ret += abs(rang[ub_rang]-pos[lb_pos])
            ub_rang -= 1
            lb_pos += 1
        else:
            ret += abs(rang[lb_rang]-pos[ub_pos]) 
            lb_rang += 1
            ub_pos -= 1
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        for j in range(n):
            dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        # dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, -1 - i, -1)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

A.sort(reverse=True)
for i in range(N):
    if i == 0:
        A[N-1-i][2] = A[N-1-i][0]
    else:
        A[N-1-i][2] = A[N-1-i+1][2] + A[N-1-i][0]

r_max = 0

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

test(0,0,N,1)
print(r_max)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

def solve(N: int, A: "List[int]"):
    flow = MinCostFlow(2*N+2)

    for i in range(N):
        for j in range(N):
            flow.add_edge(i,j+N,1,-A[i]*abs(i-j))
    
    for j in range(N):
        flow.add_edge(2*N,j,1,0)
        flow.add_edge(j+N,2*N+1,1,0)

    print(-flow.flow(2*N,2*N+1,N))
    return


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

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)

n = ni()
a = na()
b = []
for i in range(n):
    b.append((a[i],i))

b.sort(reverse=True)

ans = 0

def f(left,right,k,c):
    if k == n:
        return c
    i,j = b[k]
    x = abs(j-left)
    y = abs(right-j)
    return max(f(left+1,right,k+1,c+x*i), f(left,right-1,k+1,c+y*i))

ans = f(0,n-1,0,0)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools 

N = int(input())
A = list(map(int, input().split()))
ureshisa = [
            [A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
  pSum = 0
  for i in range(N):
    pSum += ureshisa[P[i]][i]
  maxV = max(maxV, pSum)
print(maxV)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[]
for i in range(N):
    L.append([A[i],i])
#print(L)
ans=0
import copy
from collections import deque
for i in range(1,N):
    cnt=0
    a=copy.deepcopy(L[:i])
    b=copy.deepcopy(L[i:])
    #print(a,b)
    a.sort(reverse=True)
    b.sort(reverse=True)
    #print("ab",a,b)
    A=deque([N-len(a)+j for j in range(len(a)) ])
    B=deque([j for j in range(len(b))])
    #print(A)
    #print(B)
    for j in range(len(a)):
        if abs(a[j][0]*(a[j][1]-A[0]))>abs(a[j][0]*(a[j][1]-A[-1])):
            cnt+=abs(a[j][0]*(a[j][1]-A[0]))
            A.popleft()
        else:
            cnt+=abs(a[j][0]*(a[j][1]-A[-1]))
            A.pop()
    #print("A",cnt)
    for j in range(len(b)):
        if abs(b[j][0]*(b[j][1]-B[0]))>abs(b[j][0]*(b[j][1]-B[-1])):
            cnt+=abs(b[j][0]*(b[j][1]-B[0]))
            B.popleft()
        else:
            cnt+=abs(b[j][0]*(b[j][1]-B[-1]))
            B.pop()
    #print(cnt)
    if ans<cnt:
        ans=cnt
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    dp = defaultdict(int)
    B = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
    for step, (i, a) in enumerate(B, 1):
        #print('i={}, a={}'.format(i, a))
        for left in range(step):
            right = N - step + left
            #print('[{},{}]'.format(left, right))
            #print('left[{},{}]: {} vs {}+{}'.format(left+1, right, dp[(left+1, right)], dp[(left, right)], abs(left-i)*a))
            #print('right[{},{}]: {} vs {}+{}'.format(left, right-1, dp[(left+1, right)], dp[(left, right)],abs(right-i)*a))
            dp[(left+1, right)] = max(dp[(left+1, right)], dp[(left, right)] + abs(left-i)*a)
            dp[(left, right-1)] = max(dp[(left, right-1)], dp[(left, right)] + abs(right-i)*a)    
    return max(v for v in dp.values())


# 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]"
    print(solve(N, A))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
a_sort = sorted(a)
from collections import Counter
dp = [[0 for _ in range(n+1)] for _ in range(n)]
cnt = Counter()
dic= {}
for i in range(n):
    if dic.get(a[i]) is None:
        dic[a[i]] = [i]
    else:
        dic[a[i]] += [i]
    cnt[a[i]]+=1

def maximize(rang_, pos_):
    pos = pos_.copy()
    rang = rang_.copy()
    ret= 0 
    while pos != []:
        if abs(rang[0]-pos[-1]) < abs(rang[-1]-pos[0]):
            ret += abs(rang[-1]-pos[0])
            del rang[-1]
            del pos[0]
        else:
            ret += abs(rang[0]-pos[-1]) 
            del rang[0]
            del pos[-1]
    return ret

sorted_keys = sorted(cnt.keys())
acm=0
for x in sorted_keys:
    num = cnt[x]
    for i in range(n):
        if i + acm + num <= n:
            if acm == 0:
                dp[i][acm+num] = x*maximize(list(range(i,i+num)), dic[x])
            else:
                for j in range(i,i+num+1):
                    #print(f"dp[{i}][{acm}+{num}] = max(dp[{i}][{acm}+{num}],dp[{j}][{acm}] + {x}*maximize(list(range({i},{j}))+list(range({j}+{acm},{i}+{acm}+{num})), dic[{x}]))")
                    #print(j,acm,dp[j][acm])
                    dp[i][acm+num] = max(dp[i][acm+num],dp[j][acm] + x*maximize(list(range(i,j))+list(range(j+acm,i+acm+num)), dic[x]))
    acm += num

print(max(dp[0]))

Submission status: Time Limit Exceeded

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


def f(v):
    sorted_v = sorted(v)
    c = Counter(v)
    happy = 0
    for key in c.keys():
        v_idx = np.where(v == key)[0]
        sorted_v_idx = np.where(sorted_v == key)[0]
        move_idx = sorted_v_idx - v_idx + (N - len(v))
        happy += move_idx.sum() * key
    return happy


ans = 0
for i in range(1, N):
    l = A[:i]
    r = A[i:][::-1]
    # print('l, r', l, r, f(l), f(r))
    ans = max(ans, f(l) + f(r))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n = int(input())
A = list(map(int, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = abs(i-j)*A[i-1]
ans = 0
for x in itertools.permutations(range(1, n+1), n):
    cnt = 0
    for i, j in enumerate(x):
        cnt += dp[i+1][j]
    ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = []
for i in range(n):
    b.append([a[i],i])
b.sort()
b = b[::-1]
#print(b)
dp = [[0]* (n+1) for i in range(n+1)]
cnt = 0
for i,j in b:
    for k in range(cnt+1):
        dp[cnt-k][k+1] = max(dp[cnt-k][k] + abs(n-1-j-k)*i,dp[cnt-k][k+1])
        dp[cnt-k+1][k] = max(dp[cnt-k][k] + abs(j-(cnt-k))*i,dp[cnt-k+1][k])
    cnt+=1
ans = 0
for k in range(n):
    ans = max(ans,dp[n+1-k-1][k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a2 = []
for i in range(n):
    a2.append((a[i], i))
a2.sort(reverse=True)

dp = np.full((n, n), -1)
for i2 in range(n-1, -1, -1):
    a, i = a2[i2]

    for s in range(i2+1):
        if i2 == n-1:
            dp[i2][s] = a * abs(s-i)
        else:
            dp[i2][s] = max(dp[i2+1][s+1] + a * abs(s - i),
                            dp[i2+1][s] + a * abs(n-1-i2+s - i))

print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = list(map(int,input().split()))
l = [i for i in range(1,N+1)]

s = []
for v in itertools.permutations(l, len(A)):
    n=0
    for i in range(N):
        n += A[i]*abs(i+1-v[i])
    s.append(n)
print(max(s))

Submission status: Time Limit Exceeded

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

import math
from itertools import permutations

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

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

print(max(scores))

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

A.sort(reverse=True)
for i in range(N):
    if i == 0:
        A[N-1-i][2] = A[N-1-i][0]
    else:
        A[N-1-i][2] = A[N-1-i+1][2] + A[N-1-i][0]


r_max = 0

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

test(0,0,N,1)

print(r_max)

Submission status: Time Limit Exceeded

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

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

b = []
for i in range(n):
  b.append((a[i],i))
b.sort(reverse = True)

ans = 0
def f(l,r,i,h):
  global ans
  if i == n:
    ans = max(ans,h)
    return
  x = b[i][0]
  y = b[i][1]
  f(l+1,r,i+1,h+x*abs(y-l))
  f(l,r-1,i+1,h+x*abs(y-r))

f(0,n-1,0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import queue
import itertools as it

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

#def comba(n):#1~nの組み合わせ
	#for i in range(1,n+1):
		#for j in range(1,n+1):

n = readInt()
a = readInts()

x = list(it.permutations(range(1,n+1),n))

point = []

for j in range(len(x)):
	p = 0
	for i in range(n):
		p += abs(x[j][i]-(i+1))*a[i]
		point.append(p)
		#print(p , x[j])

print(max(point))

Submission status: Time Limit Exceeded

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

B = [[i, a] for i, a in enumerate(A)]

C = sorted(B, key=lambda b: b[1], reverse=True)

l = 0
r = N - 1

ans = 0
queue = [[C, l, r, 0]]
while queue:
    D, l, r, total = queue.pop()

    total2 = total + abs(D[0][0] - l) * D[0][1]
    if len(D) == 1:
        ans = max(ans, total2)
        continue
    else:
        queue.append([D[1:], l+1, r, total2])

    total2 = total + abs(D[0][0] - r) * D[0][1]
    if len(D) == 1:
        ans = max(ans, total2)
        continue
    else:
        queue.append([D[1:], l, r-1, total2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
import sys
sys.setrecursionlimit(10**9)
def f(p):
    if not p:
        return 0
    i=N-len(p)
    return max([f(p-set([j]))+A[i]*abs(i-j) for j in p])
p=set(range(N))
print(f(p))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
import numpy as np
N = int(input())
stuff = np.array(list(map(int,input().split())))
#N = 6
#stuff = np.array([5, 5, 6, 1, 1, 1])
junban = np.array(range(N))
max_happness = 0
for subset in permutations(junban):
    happness = 0
    newjunban = np.array((subset))
#    for i in range(N):
#        happness +=stuff[i]*abs(newjunban[i]-i)
    happness = np.dot(stuff, abs(newjunban-junban))
    if happness>max_happness:
        max_happness = happness
print (max_happness)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

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

x = np.arange(N)
ys = np.array(list(itertools.permutations(x)))

print(np.max( np.sum(A * np.abs(x-ys),axis=1) ))

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

L = [i for i in range(N)]
p = list(itertools.permutations(L))
ans = 0
for i in range(len(p)):
    temp = 0
    for j in range(N):
        temp += A[j]*abs(p[i][j]-j)
    ans = max(ans,temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource

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

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

A.sort(reverse=True)

r_max = 0

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

test(0,0,N,1)

print(r_max)

Submission status: Time Limit Exceeded

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

dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    a,j = B.pop()
    for k in range(i+1):
        dp[k][i-k+1] = max(dp[k][i-k+1], dp[k][i-k] + a * abs(j-(N-1-(i-k))))
        dp[k+1][i-k] = max(dp[k+1][i-k], dp[k][i-k] + a * abs(j-k))

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N = int(input())
stuff = list(map(int,input().split()))
junban = list(range(N))
max_happness = 0
for subset in permutations(junban):
    happness = 0
    newjunban = (list(subset))
    for i in range(N):
        happness +=stuff[i]*abs(newjunban[i]-i)
    if happness>max_happness:
        max_happness = happness
print (max_happness)

Submission status: Time Limit Exceeded

Solution code:
from math import *
from collections import *
import sys
sys.setrecursionlimit(10**9)
mod = 10**9 + 7
test = 1
#test = int(input())
d = dict()
def mem(i,l,r):
	if(l > r):
		return 0
	if (l,r) in d:
		return d[(l,r)]
	ans1 = a[i][0]*abs(a[i][1]-l)+mem(i+1,l+1,r)
	ans2 = a[i][0]*abs(r-a[i][1])+mem(i+1,l,r-1)
	d[(l,r)] = max(ans1,ans2)
	return d[(l,r)]
for __ in range(test):
	n = int(input())
	a = list(map(int,input().split()))
	for i in range(n):
		a[i] = [a[i],i]
	a.sort(reverse = True)
	l,r = 0,n-1
	print(mem(0,l,r))

Submission status: Time Limit Exceeded

Solution code:
from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = {}
def opt(l, i):
    r = N - i + l - 1
    if i == N: return 0
    T = l, i
    if T in DP:
        return DP[T]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, i+1)
    DP[T] = max(v1, v2)
    return DP[T]

print(opt(0, 0))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N = int(input())
stuff = list(map(int,input().split()))
#stuff = [5, 5, 6, 1, 1, 1]
junban = list(range(N))

max_happness = 0
for subset in permutations(junban):
    happness = 0
    newjunban = (list(subset))
    for i in range(len(junban)):
        happness +=stuff[i]*abs(newjunban[i]-i)
    if happness>max_happness:
        max_happness = happness
print (max_happness)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
import itertools
import sys
sys.setrecursionlimit(10**5)
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()

X = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
p = [x for x, _ in X]
sc = [x for _, x in X]

DP = {}
def opt(l, r, i):
    if i == N: return 0
    T = l, r, i
    if T in DP:
        return DP[T]
    v1 = abs(p[i]- l)*sc[i] + opt(l+1, r, i+1)
    v2 = abs(p[i] - r)*sc[i] + opt(l, r-1, i+1)
    DP[T] = max(v1, v2)
    return DP[T]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
As = LII_split()

max_uresisa = 0
for n in permutations(range(1, N + 1), N):
    uresisa = 0
    former_index_plus = 1
    for a in n:
        # print((As[former_index_plus - 1]))
        uresisa += abs(a - former_index_plus) * As[former_index_plus - 1]
        former_index_plus += 1
    max_uresisa = max(max_uresisa, uresisa)
print(max_uresisa)

Submission status: Time Limit Exceeded

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

mod = 1000000007
INF = 110110110

N = int(input())
A = list(map(int, input().split()))
PA = []
for i in range(N):
    PA.append((A[i], i))
PA.sort(reverse=True)

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

for i in range(N+1):
    for j in range(N+1):
        dp[i][j] = -INF * INF

dp[0][0] = 0

for i in range(N):
    for j in range(N):
        if i+j >= N:
            continue
        w = PA[i+j][0]
        at = PA[i+j][1]
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + w * abs(at - i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + w * abs(at - (N-1-j)))
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 = map(int, input().split())

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

babies.sort(reverse=True)

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

from itertools import permutations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

init = np.array([i for i in range(N)])

ans = 0

for v in permutations(init):
    diff = abs(init - np.array(v))

    acc = (A * diff).sum()

    ans = max(ans, acc)

print(ans)

Submission status: Accepted

Solution code:
def sep():
    return map(int,input().strip().split(" "))
def lis():
    return list(sep())

n=int(input())
ar=lis()
data=[]
for i in range(n):
    data.append((ar[i],i))
data.sort(reverse=True)
dp = [[0] * (n+1) for _ in range(n+1)]

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

Submission status: Accepted

Solution code:
N = int(input())
A = sorted([(i, int(a)) for i, a in enumerate(input().split())], key=lambda x: x[1])[::-1]
dp = [[0] * (N+1) for _ in range(N+1)]  # 先頭からi+j人使ったときに(左にi人, 右にj人) => 最大の嬉しさ
cnt = 0
for k, a in A:
    for i in range(N):
        j = cnt - i
        if j < 0:
            continue
        # 左に移動
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a*max(0, k-i))
        # 右に移動
        dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * max(0, (N - 1) - j - k))
    cnt += 1
ans = 0
for i in range(N+1):
    ans = max(ans, dp[N-i][i])

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
xs = list(enumerate(map(int, input().split())))
xs.sort(key=lambda x: x[1])
xs.reverse()

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

for i in range(1, n + 1):
    (j, a) = xs[i - 1]

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

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

Submission status: Accepted

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

dp = [0] * (N + 1)
for i in range(N):
    dp2 = dp[:]
    for l in range(i + 1):
        a, pos = A[i]
        # add left side
        dp2[l + 1] = max(dp2[l + 1], dp[l] + abs(pos - l) * a)
        # add right side
        r = i - l + 1
        dp2[l] = max(dp2[l], dp[l] + abs(N - r - pos) * a)
    dp = dp2
print(max(dp))

Submission status: Accepted

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

dp = [0] * (N + 1)
for i in range(N):
    dp2 = dp[:]
    for l in range(i + 1):
        a, pos = A[i]
        # add left side
        dp2[l + 1] = max(dp2[l + 1], dp[l] + (pos - l) * a)
        # add right side
        r = i - l + 1
        dp2[l] = max(dp2[l], dp[l] + (N - r - pos) * a)
    dp = dp2
print(max(dp))

Submission status: Accepted

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

# 移動先xi
# p[i] = a[i]*|i-xi|
# if i > xi:ans = sum(p[i]) = sum(a[i]*(i-xi)) -> a[i]の大きい順にxiを小さくする
# if i < xi:ans = sum(p[i]) = sum(a[i]*(xi-i)) -> a[i]の小さい順にxiを小さくする
# dp[i][j]:i人がi-xi（左にいく）,j人がxi-i（右にいく）で計算（i*xi = j*xi)

A=[]
for i in range(n):
    A.append((a[i],i))
A.sort(key = lambda x:x[0], reverse=True)
dp = [[-float("inf")]*(n+1) for i in range(n+1)]
dp[0][0] = 0

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

print(max(dp[n]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    tmp = list(map(int, input().split()))
    a = [[v, i] for i, v in enumerate(tmp)]
    a.sort(reverse=True)
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(n):
        v, idx = a[i]
        for j in range(i+1):
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+v*abs(idx-j))
            dp[i+1][j] = max(dp[i+1][j] , dp[i][j]+v*abs(idx - (n-1-i+j)))
    print(max(dp[n]))

if __name__ == "__main__":
    main()