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: Wrong Answer

Solution code:
x = int(input())

line = [int(x) for x in input().split()]

dic = {}

for i in range(0, x):
    if dic.get(line[i]) != None:
        dic[line[i]].append(i)
    else:
        dic[line[i]] = [i]


availL = 0
availR = x-1

temp = sorted(line, reverse = True)

total = 0

for i in temp:
    a1 = min(dic[i])
    a2 = max(dic[i])

    v1 = abs(availL-a2)
    v2 = abs(availR-a1)

    if v1 > v2:
        #print(str(i) + " who was from "+ str(a2)+ " goes to " + str(availL))
        total = total + (v1*i)
        availL = availL + 1
        dic[i].remove(a2)
    else:
        #print(str(i) + " who was from "+ str(a1)+ " goes to " + str(availR))
        total = total + (v2*i)
        availR = availR - 1
        dic[i].remove(a1)

print(total)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        return self._sum(r) - self._sum(l)


n = int(input())
a = list(map(int, input().split()))
bit = BIT(n)
for i in range(n):
    bit.add(i, a[i])

a = [[a[i], i] for i in range(n)]
a = sorted(a, reverse=True)

l = 0
r = n - 1
ans = 0
for i in range(n):
    val, i = a[i]
    l_sum = bit.get_sum(0, i)
    r_sum = bit.get_sum(i + 1, n)
    l_sum += val * (i - l)
    r_sum += val * (r - i)
    if l_sum >= r_sum:
        ans += val * (i - l)
        l += 1
    else:
        ans += val * (r - i)
        r -= 1
    bit.add(i, -val)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[(j,i) for i,j in enumerate(map(int,input().split()))]
ans=0
for x in range(1,n):
    L=l[:x]
    R=l[x:]
    L.sort()
    R.sort(reverse=True)
    y=0
    for i,j in enumerate(R+L):
        y+=j[0]*abs(j[1]-i)
    ans=max(ans,y)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
active = list(map(int, input().split(" ")))
ans = 0


head = 0 
tail = N-1
for _ in range(N) :
    _max = -float('inf')
    at_head = True
    idx = -1
    
    for j in range(N) :
        if active[j] == -1 :
            continue
        v1 = abs(head-j)*active[j] 
        v2 = abs(tail-j)*active[j] 
        if _max < v1 :
            _max = v1
            idx = j
            at_head = True
        elif _max == v1 :
            if active[idx] > active[j] :
                idx = j
                at_head = True


        if _max < v2 :
            _max = v2
            idx = j
            at_head = False
        elif _max == v2 :
            if active[idx] > active[j] :
                idx = j
                at_head = False

    active[idx] = -1
    ans += _max
    if at_head :
        head += 1
    else :
        tail -= 1

print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    A=LI()
    ans=0
    used=[0]*N#動かしたか
    
    for i in range(N//2+3):
        for k in range(2):
            if k==0:
                target=N-1-i
            else:
                target=i
            maxx=0
            maxj=-1
            for j in range(N):
                if used[j]==0:
                    temp=A[j]*abs(target-j)
                    if temp>maxx:
                        maxx=temp
                        maxj=j
            ans+=maxx
            used[maxj]=1
            
    print(ans)
        
        
        

main()

Submission status: Wrong Answer

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

def solve(N: int, A: "List[int]"):
    heap = []

    for i in range(N):
        for j in range(N):
            heapq.heappush(heap,(-A[i]*abs(i-j),i,j))
    
    moved_infant = set()
    moved_index = set()
    answer = 0
    while len(moved_index) < N:
        score,index,infant = heapq.heappop(heap)

        if index not in moved_index and infant not in moved_infant:
            moved_infant.add(infant)
            moved_index.add(index)
            answer -= score
    print(answer)
    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: Wrong Answer

Solution code:
import random
maxa = 0

n = int(input())
arr = list(map(int,input().split()))
children = [[i, arr[i]] for i in range(n)]

for ii in range(15):
    buf = [i for i in range(n)]
    random.shuffle(buf)
    ans = 0

    for i,b in enumerate(buf):
        il  = children[b][0]
        ans += children[b][1]*abs(il-i)

    while True:
        dif = 0
        for i in range(n-1):
            l = buf[i]
            r = buf[i+1]
            il = children[l][0]
            ir = children[r][0]

            tp = -(children[l][1]*abs(il-i)+children[r][1]*abs(ir-(i+1))-children[l][1]*abs(il-(i+1))-children[r][1]*abs(ir-i))
            if tp > 0:
                buf[i],buf[i+1] = buf[i+1],buf[i]
                dif += tp
            else:
                continue
        if dif > 0:
            ans += dif
        else:
            break

    if ans > maxa:
        maxa = ans
print(maxa)

Submission status: Wrong Answer

Solution code:
import random
maxa = 0

n = int(input())
arr = list(map(int,input().split()))
children = [[i, arr[i]] for i in range(n)]

for ii in range(12):
    buf = [i for i in range(n)]
    random.shuffle(buf)
    ans = 0

    for i,b in enumerate(buf):
        il  = children[b][0]
        ans += children[b][1]*abs(il-i)

    while True:
        dif = 0
        for i in range(n-1):
            l = buf[i]
            r = buf[i+1]
            il = children[l][0]
            ir = children[r][0]

            tp = -(children[l][1]*abs(il-i)+children[r][1]*abs(ir-(i+1))-children[l][1]*abs(il-(i+1))-children[r][1]*abs(ir-i))
            if tp > 0:
                buf[i],buf[i+1] = buf[i+1],buf[i]
                dif += tp
            else:
                continue
        if dif > 0:
            ans += dif
        else:
            break

    if ans > maxa:
        maxa = ans
print(maxa)

Submission status: Wrong Answer

Solution code:
import heapq

NN = 202020
MOD = 10**9+7
INF = float("inf")

n = int(input())
A = list(map(int, input().split()))
que = []
for i in range(len(A)):
    for j in range(len(A)):
        que.append((-A[i]*abs(i-j), abs(i-j), i, j))

heapq.heapify(que)
ans = [-1]*len(A)
seen = set()
while que:
    val, _, i, j = heapq.heappop(que)
    # print(val, x)
    if ans[j] == -1 and i not in seen:
        ans[j] = -val
        seen.add(i)
    # print(val, j, ans)

# print(ans)
print(sum(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
raw = [i for i in range(n)]
for _ in range(10):
  for i in range(n):
    tmp = []
    for j in range(n):
      tmp.append(abs(raw[i]-j)*a[i] + abs(raw[j]-i)*a[j]
                -abs(raw[i]-i)*a[i] - abs(raw[j]-j)*a[j])
    maxi = max(tmp)
    #print(tmp)
    for j in range(n):
      if tmp[j] == maxi:
        raw[i],raw[j] = raw[j],raw[i]
        a[i],a[j] = a[j],a[i]
  #print(raw)
  #print(a)
ans = 0
for i in range(n):
  ans += a[i] * abs(i-raw[i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
raw = [i for i in range(n)]
for i in range(n):
  tmp = []
  for j in range(n):
    tmp.append(abs(raw[i]-j)*a[i] + abs(raw[j]-i)*a[j]
              -abs(raw[i]-i)*a[i] - abs(raw[j]-j)*a[j])
  maxi = max(tmp)
  #print(tmp)
  for j in range(n):
    if tmp[j] == maxi:
      raw[i],raw[j] = raw[j],raw[i]
      a[i],a[j] = a[j],a[i]
#print(raw)
#print(a)
ans = 0
for i in range(n):
  ans += a[i] * abs(i-raw[i])
print(ans)

Submission status: Wrong Answer

Solution code:
def calc(a,k):
    b = a.copy()
    ret = 0
    if k == 0:
        b.sort()
    elif k == n:
        b.sort(reverse=True)
    else:
        c = b[:k]
        d = b[k:]
        c.sort
        d.sort(reverse=True)
        b = d+c
    #print(b)
    for i in range(n):
        ret += b[i][0] * abs(b[i][1] - i)
    #print(k,ret)
    return ret

n = int(input())
a = [[int(num),-1] for num in input().split()]

for i in range(n):
    a[i][1] = i
    
ans = 0
for k in range(n+1):
    ans = max(ans,calc(a,k))
    
print(ans)

Submission status: Wrong Answer

Solution code:
import random
maxa = 0

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

for ii in range(15):
    children = [[i,arr[i]] for i in range(n)]
    buf = [i for i in range(n)]
    random.shuffle(buf)

    ans = 0
    while True:
        dif = 0
        for i in range(n-1):
            l = buf[i]
            r = buf[i+1]
            il = children[l][0]
            ir = children[r][0]

            tp = -(children[l][1]*abs(il-i)+children[r][1]*abs(ir-(i+1))-children[l][1]*abs(il-(i+1))-children[r][1]*abs(ir-i))
            if tp > 0:
                buf[i],buf[i+1] = buf[i+1],buf[i]
                dif += tp
            else:
                continue
        if dif > 0:
            ans += dif
        else:
            break

    if ans > maxa:
        maxa = ans
print(maxa)

Submission status: Wrong Answer

Solution code:
N = int(input())
active = list(map(int, input().split(" ")))
ans = 0


head = 0 
tail = N-1
for _ in range(N) :
    _max = -float('inf')
    at_head = True
    idx = -1
    
    for j in range(N) :
        if _max < abs(head-j)*active[j] :
            _max = abs(head-j)*active[j]
            idx = j
            at_head = True
        elif _max == abs(head-j)*active[j] :
            if active[idx] > active[j] :
                idx = j

        if _max < abs(tail-j)*active[j] :
            _max = abs(tail-j)*active[j]
            idx = j
            at_head = False
        elif _max == abs(tail-j)*active[j] :
            if active[idx] > active[j] :
                idx = j


    active[idx] = -1
    ans += _max
    if at_head :
        head += 1
    else :
        tail -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
inf=[[a[i],i] for i in range(n)]
inf.sort(reverse=True)
ans=[False]*n
l=0;r=n-1
for i in range(n):
    a=inf[i][0];x=inf[i][1]
    if x-l>=r-x: ans[l]=[a,x];l+=1
    if x-l<r-x: ans[r]=[a,x];r-=1

x=0
for i in range(n):
    x+=ans[i][0]*abs(ans[i][1]-i)
print(x)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=[[a[i],i]for i in range(n)]
c=0
for i in range(n):
    for j in range(n-1,i,-1):
        if abs(a[i][1]-i)*a[i][0]+abs(a[j][1]-j)*a[j][0]<abs(a[i][1]-j)*a[i][0]+abs(a[j][1]-i)*a[j][0]:
            c+=abs(a[i][1]-j)*a[i][0]+abs(a[j][1]-i)*a[j][0]-abs(a[i][1]-i)*a[i][0]-abs(a[j][1]-j)*a[j][0]
            a[i],a[j]=a[j],a[i]
print(c)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        return self._sum(r) - self._sum(l)


n = int(input())
a = list(map(int, input().split()))
bit = BIT(n)
for i in range(n):
    bit.add(i, a[i])

a = [[a[i], i] for i in range(n)]
a = sorted(a, reverse=True)

l = 0
r = n - 1
ans = 0
for i in range(n):
    val, i = a[i]
    l_sum = bit.get_sum(0, i)
    r_sum = bit.get_sum(i + 1, n)
    l_sum += val * (i - l)
    r_sum += val * (r - i)
    if l_sum > r_sum:
        ans += val * (i - l)
        l += 1
    else:
        ans += val * (r - i)
        r -= 1
    bit.add(i, -val)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
children = [[i,arr[i]] for i in range(n)]
buf = [i for i in range(n)]

ans = 0
while True:
    dif = 0
    for i in range(n-1):
        l = buf[i]
        r = buf[i+1]
        il = children[l][0]
        ir = children[r][0]

        tp = -(children[l][1]*abs(il-i)+children[r][1]*abs(ir-(i+1))-children[l][1]*abs(il-(i+1))-children[r][1]*abs(ir-i))
        if tp >= 0:
            buf[i],buf[i+1] = buf[i+1],buf[i]
            dif += tp
        else:
            continue
    if dif > 0:
        ans += dif
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    used = [False] * N

    first = 0
    back = N - 1
    ans = 0
    for _ in range(N):
        maxValue = 0
        toMove = -1
        for i in range(N):
            if not used[i]:
                if maxValue < A[i] * max(abs(i - first), abs(i - back)):
                    maxValue = A[i] * max(abs(i - first), abs(i - back))
                    toMove = i
        if abs(toMove - first) >= abs(toMove - back): first += 1
        else: back -= 1
        ans += maxValue
        used[toMove] = True
        #print(toMove, ans)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[(j,i) for i,j in enumerate(map(int,input().split()))]
ans=[]
for x in range(1,n):
    L=l[:x]
    R=l[x:]
    L.sort()
    R.sort(reverse=True)
    y=0
    for i,j in enumerate(R+L):
        y+=j[0]*abs(j[1]-i)
    ans.append(y)
print(max(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = list(map(int,input().split()))
children = [[i,arr[i]] for i in range(n)]
buf = [i for i in range(n)]

ans = 0
while True:
    dif = 0
    for i in range(n-1):
        l = buf[i]
        r = buf[i+1]
        il = children[l][0]
        ir = children[r][0]

        tp = -(children[l][1]*abs(il-i)+children[r][1]*abs(ir-(i+1))-children[l][1]*abs(il-(i+1))-children[r][1]*abs(ir-i))
        if tp > 0:
            buf[i],buf[i+1] = buf[i+1],buf[i]
            dif += tp
        else:
            continue
    if dif > 0:
        ans += dif
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
active = list(map(int, input().split(" ")))
ans = 0


head = 0 
tail = N-1
for _ in range(N) :
    _max = -float('inf')
    at_head = True
    idx = -1
    
    for j in range(N) :
        if _max < abs(head-j)*active[j] :
            _max = abs(head-j)*active[j]
            idx = j
            at_head = True
        
        if _max < abs(tail-j)*active[j] :
            _max = abs(tail-j)*active[j]
            idx = j
            at_head = False
        
    active[idx] = -1
    ans += _max
    if at_head :
        head += 1
    else :
        tail -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from scipy.optimize import linear_sum_assignment as lsa


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

cost = np.arange(N).reshape(N,1)
cost = -np.abs(cost - cost.T)
cost[np.arange(N),np.arange(N)] = 1000000
cost *= A.reshape(N,1)

row_ind, col_ind = lsa(cost)

print(-cost[row_ind, col_ind].sum())

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
aa = [(int(a), i) for i, a in enumerate(input().split())]
ans = 0
for i in range(1, N):
    ll = np.array(sorted(aa[:i]))
    rr = np.array(sorted(aa[i:], reverse=True))
    L = sum(ll[:, 0] * (np.arange(N - i, N) - ll[:, 1]))
    R = sum(rr[:, 0] * (rr[:, 1] - np.arange(0, N - i)))
    ans = max(ans, L + R)
print(ans)

Submission status: Wrong Answer

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

    ans = 0

    ax = []
    for i in range(n):
        ax.append((a[i], i))

    for _ in range(n):
        for i in range(n-1):
            if ax[i][0] * abs(ax[i][1] - (i+1)) + ax[i+1][0] * abs(ax[i+1][1] - i) > ax[i][0] * abs(ax[i][1] - i) + ax[i+1][0] * abs(ax[i+1][1] - (i+1)):
                ax[i], ax[i+1] = ax[i+1], ax[i]

    total = 0
    for i in range(n):
        total += ax[i][0] * abs(ax[i][1] - i)
        
    ans = max(ans, total)

    ax = []
    for i in range(n):
        ax.append((a[i], n-i-1))
    ax.reverse()

    for _ in range(n):
        for i in range(n-1):
            if ax[i][0] * abs(ax[i][1] - (i+1)) + ax[i+1][0] * abs(ax[i+1][1] - i) > ax[i][0] * abs(ax[i][1] - i) + ax[i+1][0] * abs(ax[i+1][1] - (i+1)):
                ax[i], ax[i+1] = ax[i+1], ax[i]

    total = 0
    for i in range(n):
        total += ax[i][0] * abs(ax[i][1] - i)

    ans = max(ans, total)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))

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

    dp = np.zeros((N+1,N+1), dtype='int64')
    #dp = [[0]*(N+1-i) for i in range(N+1)]

    #m = 0
    for i in range(1,len(A)+1):
        index,a = A[i-1]
        for j in range(i+1):
            if (i-j,j) == (0,0):
                dp[i-j][j] = 0
            elif i-j == 0:
                dp[i-j][j] = dp[i-j][j-1] + (N-j-index)*a
            elif j == 0:
                dp[i-j][j] = dp[i-j-1][j] + (abs(index-(i-j-1)))*a
            else:
                dp[i-j][j] = max(dp[i-j][j-1] + (N-j-index)*a, dp[i-j-1][j] + (abs(index-(i-j-1)))*a)
            #if i == len(A):
            #    m = max(m, dp[i-j][j])

    #print(dp)
    print(np.max(dp))
    #print(m)

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        dp[L+1][R] = max(dp[L+1][R], dp[L][R] + A_index[i][0] * abs(L - A_index[i][1]))
        dp[L][R+1] = max(dp[L][R+1], dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1]))


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = []

for i in range(len(A_list)):
    A_index.append( (A_list[i], i) )

A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


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

Submission status: Time Limit Exceeded

Solution code:
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
A_sort = list(np.sort(A)[::-1])
A_index = list(np.argsort(A)[::-1])

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N):
    dp_new = [-float('inf')]*(N+1)
    pi = A_index[i]  #もともといた場所
    for l in range(i+1): 
        r = i - l   #右を選んだ回数
        dp_new[l+1] = max(dp_new[l+1],dp[l] + A_sort[i] * (pi-l)) 
        dp_new[l] = max(dp_new[l],dp[l] + A_sort[i] * ((N-r-1)-pi))
    dp = dp_new
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
A_sort = list(np.sort(A)[::-1])
A_index = list(np.argsort(A)[::-1])

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

for i in range(N):
    pi = A_index[i]  #もともといた場所
    for l in range(i+1): 
        r = i - l   #右を選んだ回数
        dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l] + A_sort[i] * (pi-l)) 
        dp[i+1][l] = max(dp[i+1][l],dp[i][l] + A_sort[i] * ((N-r-1)-pi))

print(max(dp[N]))

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [(A[i], i) for i in range(N)]
    B.sort(reverse = True)

    DP = [[-1 for j in range(N + 1)] for _ in range(N)] #i番目の幼児まで見た時、左からi番目まで埋まっている時の最大値
    DP[0][0] = B[0][0] * abs(B[0][1] - (N - 1))
    DP[0][1] = B[0][0] * B[0][1]

    for i in range(1, N):
        for j in range(i + 1):
            #右に詰める時はjの値は変わらない
            #左に詰めるときはj += 1
            DP[i][j] = max(DP[i][j], DP[i-1][j] + B[i][0] * abs(B[i][1] - (N - 1 - i + j)))
            DP[i][j+1] = max(DP[i][j+1], DP[i-1][j] + B[i][0] * abs(B[i][1] - j))
    print(max(DP[N-1]))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ab = []
for i in range(N):
  Ab.append([A[i], i])
  
Ab.sort(reverse=True)
#dp[i][j] Aの大きいじゅんにi個とったとき、左寄せj個、右寄せi-j個としたときのMAX
dp = [[0 for _ in range(N+5)] for _ in range(N+5)]
dp[0][0] = 0

for i in range(0,N):
  a, p = Ab[i]
  for j in range(0,i+1):
    r = i - j
    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + a * (p-j))
    dp[i+1][j]  = max(dp[i+1][j], dp[i][j] + a * (N-r-p-1))
                      
ans = 0
for i in range(N):
  ans = max(ans, dp[N][i])
  
print(ans)
#for a in dp:
#  print(a)

Submission status: Time Limit Exceeded

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

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

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

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

    for i in range(N):
        for j in range(N-i):
            score=dp[i][j]

            dp[i+1][j]=max(dp[i+1][j],score+A[i+j]*(A_index[i+j]-i))
            dp[i][j+1]=max(dp[i][j+1],score+A[i+j]*((N-1-j)-A_index[i+j]))

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

    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

    AA=zip(A,A_index)
    AA=sorted(AA,reverse=True)
    A,A_index=zip(*AA)

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

            if (scoreLeft<score+A[i+j]*(A_index[i+j]-i)):
                dp[i+1][j]=score+A[i+j]*(A_index[i+j]-i)

            scoreRight=dp[i][j+1]

            if (scoreRight<score+A[i+j]*((N-1-j)-A_index[i+j])):
                dp[i][j+1]=score+A[i+j]*((N-1-j)-A_index[i+j])

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

    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
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]


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

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
a = list(map(int,input().split()))
hq = []
for i, ai in enumerate(a):
    heapq.heappush(hq,(-ai,i))

dp = [[-1 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
ai,hi = heapq.heappop(hq)
dp[1][0] = -ai*hi
dp[0][1] = -ai*(n-1-hi)
for i in range(2,n+1):
    ai,hi = heapq.heappop(hq)
    dp[i][0] = dp[i-1][0] - ai*abs(hi-i+1)
    dp[0][i] = dp[0][i-1] - ai*abs(n-i-hi)
    for j in range(1,i):
        dp[i-j][j] = max(dp[i-j-1][j]-ai*abs(hi-i+j+1),dp[i-j][j-1]-ai*abs(n-j-hi))

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

Submission status: Time Limit Exceeded

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

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

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

pos = [i for i in range(N)]
ls = [[i,j] for (i,j) in zip(A,pos)]

ans = 0

import itertools
for v in itertools.permutations(ls):
    count = 0
    for i in range(N):
        count += v[i][0]*abs(v[i][1]-i)
    if ans < count:
        ans = count



print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = [(i+1, a) for i, a in enumerate(map(int, input().split()))]
As.sort(key=lambda x: x[1], reverse=True)
 
dp = [[0 for _ in range(N+1)] for _ in range(N+1)] # dp[x*N+y] = max when l=x r=y

r = 0
for n in range(1, N+1): # x+y = n
    i, a = As[n-1]
    for m in range(n+1): # x = m
        x = m
        y = n - m
        if x > 0:
            tl = dp[x-1][y] + a * abs(i - x)
        else:
            tl = 0
        if y > 0:
            tr = dp[x][y-1] + a * abs((N-y+1) - i)
        else:
            tr = 0
        dp[x][y] = max(tl, tr)
        r = max(r, dp[x][y])
 
print(r)

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(N+1)] for _ in range(N+1)] # dp[x*N+y] = max when l=x r=y

for n in range(1, N+1): # x+y = n
    i, a = As[n-1]
    for m in range(n+1): # x = m
        x = m
        y = n - m
        if x > 0:
            tl = dp[x-1][y] + a * abs(i - x)
        else:
            tl = 0
        if y > 0:
            tr = dp[x][y-1] + a * abs((N-y+1) - i)
        else:
            tr = 0
        dp[x][y] = max(tl, tr)

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

print(r)

Submission status: Time Limit Exceeded

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

dp = [0] * ((N+1)**2) # dp[x*N+y] = max when l=x r=y

for n in range(1, N+1): # x+y = n
    i, a = As[n-1]
    for m in range(n+1): # x = m
        x = m
        y = n - m
        if x > 0:
            tl = dp[(x-1)*N+y] + a * abs(i - x)
        else:
            tl = 0
        if y > 0:
            tr = dp[x*N+(y-1)] + a * abs((N-y+1) - i)
        else:
            tr = 0
        dp[m*N+(n-m)] = max(tl, tr)

r = 0
for n in range(N+1):
    x = n
    y = N - n
    r = max(dp[x*N+y], r)

print(r)