Problem:


Score : 500 points

Problem Statement

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

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

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

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

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

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Runtime Error

Solution code:
n = int(input())
a  = list(map(int,input().split()))
cnt = {}
for i in range(n):
    if a[i] not in cnt:cnt[a[i]] = [i]
    else:cnt[a[i]].append(i)

    
lcnt,rcnt = 0,0
ans = 0
for val,ind in res:
    if ind-lcnt < n-ind-1-rcnt:
        
        ans +=val*(n-ind-1-rcnt)
        rcnt+=1
    else:
        ans +=val*(ind - lcnt)
        lcnt+=1
print(ans)

Submission status: Runtime Error

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

left = 0
right = N-1
pos_and_a = list(sorted(enumerate(a_s), key=lambda x: -(x[1] * max(x[0]-left, right-x[0]))))

def inner(index, total, left, right):
  if index == len(pos_and_a):
    return total
  past_pos, a = pos_and_a[index]
  dist_left = abs(past_pos - left) 
  dist_right = abs(right - past_pos)
  if dist_left == dist_right:
  	return max(inner(index+1, total + a * dist_left, left+1, right), 
    		   inner(index+1, total + a * dist_right, left, right-1))
  if dist_left > dist_right:
    return inner(index+1, total + a * dist_left, left+1, right)
  return inner(index+1, total + a * dist_right, left, right-1) 

print(inner(0, 0, left, right))

Submission status: Runtime Error

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

print(N)
print(A)

m=0
for x = range(N):
  m = max(m, A[x]*max(x,N-1-x))
#
print(m)

Submission status: Runtime Error

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

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

Solution code:
#include<stdio.h>
int main()
{
int A[1000000000],N,n, i, sum=0;
scanf("%d",&N);
if(N>=2&&N<=2000)
{
for(i=1;i<=N;i++)
  {
  scanf("%d", &A[i]) ;
  }
  n=1;
for(i=1;i<=N;i++) 
{
if(n>=A[i])
  sum=sum+n*(A[i]-n) ;
  n++;
else
  sum=sum+n*(n-A[i]) ;
  n++;
}
printf("%d",sum);
}
}

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

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))