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:
from collections import defaultdict

#dpa[(0,0)] = 0

n = int(input())

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

d = {}
for i in range(n):
	d[i] = a[i]

dp = defaultdict(lambda: 0)

i = 0
x = 0
y = 0
maxr = 0
for k,v in sorted(d.items(), key=lambda x: -x[1]):
	i+=1
	print(k,": ",v)
	for j in range(i+1):
		if j == 0:
			migi = 0
		else:
			migi = abs(n - j - k)*v
		
		if i - j == 0:
			hida = 0
		else:
			hida = abs(k - (i - j)+1)*v
		dp[(j,i-j)] = max(dp[(j-1,i-j)]+migi,dp[(j,i-j-1)]+hida)
		
		if i == n:
			maxr = max(maxr,dp[(j,i-j)])
#		print(j,i-j,k,hida,migi,dp[(j,i-j)])

print(maxr)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

#dpa[(0,0)] = 0

n = int(input())

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

d = {}
for i in range(n):
	d[i] = a[i]

dp = defaultdict(lambda: 0)

i = 0
x = 0
y = 0
maxr = 0
for k,v in sorted(d.items(), key=lambda x: -x[1]):
	i+=1
#	print(k,": ",v)
	for j in range(i+1):
		if j == 0:
			migi = 0
		else:
			migi = abs(n - j - k)*v
		
		if i - j == 0:
			hida = 0
		else:
			hida = abs(k - (i - j)+1)*v
		dp[(j,i-j)] = max(dp[(j-1,i-j)]+migi,dp[(j,i-j-1)]+hida)
		
		if k == n - 1:
			maxr = max(maxr,dp[(j,i-j)])
#		print(j,i-j,k,hida,migi,dp[(j,i-j)])

print(maxr)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[-1] * (n+1) for i in range(n+1)]
A = []
for i in range(n):
    A.append([a[i], i])
A.sort(reverse=True)
for i in range(1, n+1):
    for j in range(i+1):
        if j == 0:
            dp[j][i-j] = dp[j][i-j-1] + A[i-1][0] * abs(n-i-A[i-1][1])
        elif j == i:
            dp[j][i-j] = dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-i+1)
        else:
            dp[j][i-j] = max(dp[j][i-j-1] + A[i-1][0] * abs(n-i+j-A[i-1][1]), dp[j-1][i-j] + A[i-1][0] * abs(A[i-1][1]-j+1))
ans = 0
for i in range(n+1):
    ans = max(ans, dp[i][n-i])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
s=list(map(int, input().split()))
p={}
for i in range(n):
    p[i+1]=s[i]
a=0
b=[0]
c=0
e=0
f=0
g=[]
h=n
l=1
m=0
for j in range(1,n+1):
    c=0
    f=0
    for i in range(1,n+1):

        d=0
        if not(i in g):


            d=max((h-i),i-l)
            # print(c,d,h,i,j,l)
            if c<p[i]*d:
                c=p[i]*d
                f=i

            elif c==p[i]*d and d>e:
                e=d
                c=p[i]*d
                f=i

    if (h-f)>(f-l):
        h-=1
    else:
        l+=1
    g.append(f)
    m+=c
print(m)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
place = [0]*n
active = sorted(a,reverse=True)
for i in range(n):
    place[i] = a.index(active[i])
    a[a.index(active[i])] = -1

#dp[x][y] x,y:0~n+1 (x[-1]=x[n+1]=0にすることで端の処理を楽にする)
dp = [[0 for i in range(n+2)]for j in range(n+2)]

for i in range(n):
    dp[0][i+1] = dp[0][i]+active[i]*abs(n-i-1-place[i])
    dp[i+1][0] = dp[i][0]+active[i]*abs(place[i]-i)



def check(mat):
    for i in range(len(mat)):
        print(mat[i])
    print("\n")

check(dp)

for i in range(n):
    for x in range(i+2):
        y = i+1 - x
        if x != 0 and y != 0:
            dp[x][y] = max(dp[x-1][y]+active[i]*abs(place[i]-x+1),dp[x][y-1]+active[i]*abs(n-y-place[i]))
            if i == n-1:
                ans = max(ans,dp[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

# input
N = int(input())
A = list(map(int, input().split()))
N = 2000
A = [i for i in range(1, N + 1)]


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        x, y = p
        for i in range(n):
            j = n - 1 - i
            left = dp[i][j] + x * abs(y - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            right = dp[i][j] + x * abs(y - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

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

r = 0
left, right = 0, n-1
while left <= right:
  m = max(l)
  p = l.index(m)
  l[p] = -1
  if abs(p-left) > abs(p-right):
    r += m*abs(p-left)
    left += 1
  else:
    r += m*abs(p-right)
    right -= 1

    
print(r)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a, reverse=True)
left, right = 0, 0
sum = 0
for i in range(n):
    index = a.index(b[i])
    a[index] = 0
    sum += b[i]* max((index - left), (((n - 1) - right) - index))
    if (index - left) <= (((n - 1) - right) - index) or index < n / 2:
        right += 1
    else:
        left += 1
print(sum)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a, reverse=True)
left, right = 0, 0
sum = 0
for i in range(n):
    index = a.index(b[i])
    a[index] = 0
    sum += b[i]* max((index - left), (((n - 1) - right) - index))
    if (index - left) < (((n - 1) - right) - index) or index < n / 2:
        right += 1
    else:
        left += 1
print(sum)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

aa = [[a[i],i] for i in range(n)]

aa.sort(reverse = True)

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

for i in range(1,n+1):
    on = aa[i-1]
    for j in range(i+1):
        if j-1 >= 0:
            dp[i-j][j] = max(dp[i-j][j-1] + on[0] * abs(on[1] - (n-1 - (j - 1))),dp[i-j][j])
            if i == 1:
                print(dp[i-j][j-1] + on[0] * abs(on[1] - j),dp[i-j][j])
        if i-j-1 >= 0:
            #dp[i-j][j] = max(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (n-1 - (i-j))))
            dp[i-j][j] = max(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """
            if i == 1:
                print(on,(n-1 - (i-j)),n-1,i-j)
                print(dp[i-j-1][j],on[0] * abs(on[1] - (n-1 - (i-j))))
                print(dp[i-j][j],dp[i-j-1][j] + on[0] * abs(on[1] - (i-j-1)))
            """

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

Submission status: Wrong Answer

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

dp = []
for _ in range(n+1):
    dp.append([0] * (n+1))
for j in range(1,n+1): # all go bigger
    yb = n - (j-1)
    a, i = A_l[j-1]
    dp[j][0] = dp[j-1][0] + a*(yb-(i+1))
for k in range(1,n+1): # all go smaller
    ys = 1 + (k-1)
    a, i = A_l[k-1]
    dp[0][k] = dp[0][k-1] + a*((i+1)-ys)

for j in range(1,n+1):
    for k in range(1,n-j+1):
        yb = n - (j-1)
        ys = 1 + (k-1)
        a, x = A_l[j+k-1]
        j_plus = a*(yb-(i+1))
        k_plus = a*((i+1)-ys)
        dp[j][k] = max(dp[j-1][k]+j_plus, dp[j][k-1]+k_plus)

result = 0
for j in range(0,n+1):
    k = n-j
    result = max(result, dp[j][k])
print(result)
#for l in range(n+1):
#    print(dp[l])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0 for _ in range(N+1)] for i in range(N+1)]

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0][i] = dp[0][i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i][0] = dp[i-1][0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x][y]= max((k-x > 0)*(dp[x-1][y] + (k-x)*val),
                     (N-y-k+1 > 0)*(dp[x][y-1] + (N-y-k+1) * val))

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = np.zeros((N+1, N+1))

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0,i] = dp[0,i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i,0] = dp[i-1,0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x,y]= max((k-x > 0)*(dp[x-1, y] + (k-x)*val),
                     (N-y-k+1 > 0)*(dp[x, y-1] + (N-y-k+1) * val))

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = np.zeros((N+1, N+1))

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0,i] = dp[0,i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i,0] = dp[i-1,0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x,y]= max((k-x > 0)*(dp[x-1, y] + (k-x)*val),
                     (N-y-k+1 > 0)*(dp[x, y-1] + (N-y-k+1) * val))

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
_A = list(map(int, input().split()))
A = []
for i, a in enumerate(_A, 1):
    A.append((i, a))

dp = [0] * (N+1)
for i in range(N+1):
    _left = A[0:i]
    _right = A[i:]
    perm = list(range(1, N + 1))
    left = sorted(_left, key=lambda x: x[1], reverse=True)
    right = sorted(_right, key=lambda x: x[1], reverse=True)

    happiness = 0

    idx = N
    for k, Ak in left:
        happiness += (idx-k) * Ak
        idx -= 1
    idx = 1
    for k, Ak in right:
        happiness += (k - idx) * Ak
        idx += 1
    dp[i] = happiness


print(max(dp))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
_A = list(map(int, input().split()))
A = []
for i, a in enumerate(_A, 1):
    A.append((i, a))

dp = [0] * N
for i in range(N):
    _left = A[0:i]
    _right = A[i:]
    perm = list(range(1, N + 1))
    left = sorted(_left, key=lambda x: x[1], reverse=True)
    right = sorted(_right, key=lambda x: x[1], reverse=True)

    happiness = 0

    idx = N
    for k, Ak in left:
        happiness += (idx-k) * Ak
        idx -= 1
    idx = 1
    for k, Ak in right:
        happiness += (k - idx) * Ak
        idx += 1
    dp[i] = happiness


print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *

N = int(input())

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

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

print(curr_max)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *

N = int(input())

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

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

print(curr_max)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())
_A = list(map(int, input().split()))
A = []
for i,a in enumerate(_A, 1):
    A.append((i, a))
perm = list(range(1,N+1))
A = sorted(A, key=lambda x:x[1], reverse=True)

happiness = 0
for k, Ak in A:
    if abs(perm[0]-k) > abs(perm[-1]-k):
        d, v = perm[0],abs(perm[0]-k)
    d, v = max([(0, abs(perm[0]-k)), (-1, abs(perm[-1]-k))], key=lambda x:x[1])
    happiness += v * Ak
    del perm[d]

print(happiness)

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *

N = int(input())

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


print(1)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

info = [[] for _ in range(N)]
for i,a in enumerate(A):
    for j in range(N):
        heappush(info[j], ((-1) * a * abs(i - j), i))

Submission status: Wrong Answer

Solution code:
from collections import *
from itertools import *

N = int(input())

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

ABI = sorted(((a, max(N-i, i-1)*a, i) for i, a in enumerate(A, 1)), reverse=True)
SA, SB = map(sum, islice(zip(*ABI), 0, 2))

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

print(curr_max)

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
    n = int(input())
    a = [int(x) for x in input().split()]
    ex = [x for x in range(n)]

    s = 0
    e = n - 1
    p_max = 1
    ans = 0
    
    for j in range(n):
        for i, exi in enumerate(ex):
            p = max([exi - s, e - exi]) * a[exi]
            if p_max <= p:
                p_max = p
                p_max_arg = i
        ans += p_max
        p_max = 0
        if ex[p_max_arg] - s < e - ex[p_max_arg]:
            e -= 1
        else:
            s += 1
        ex.pop(p_max_arg)
    
    print(ans)

Submission status: Wrong Answer

Solution code:
class segtree:
    def __init__(self, size, identity, combine):
        self.size = size
        self.identity = identity
        self.combine = combine
        self.tree = [identity for i in range(2 * (size + 1))]
    def update(self, i, x):
        i += self.size; self.tree[i] = x; i >>= 1
        while i:
            self.tree[i] = self.combine(self.tree[i << 1], self.tree[(i << 1) | 1])
            i >>= 1
    def query(self, a, b, inclusive=True):
        ans_l, ans_r = self.identity, self.identity
        a += self.size; b += self.size + inclusive
        while a < b:
            if a & 1: 
                ans_l = self.combine(ans_l, self.tree[a]); a += 1
            if b & 1: 
                b -= 1; ans_r = self.combine(self.tree[b], ans_r)
            a >>= 1; b >>= 1
        return self.combine(ans_l, ans_r)
    def point_query(self, i):
        return self.query(i, i)

n = int(input())
a = [(int(x), i) for i, x in enumerate(input().split())]
gain_by_swapping = segtree(n, (0, 0), max)

def gain_by_moving(val, source_index, dest_index):
    return val * abs(source_index - dest_index)

def gain_by_swapping_with_pred(i):
    old = gain_by_moving(*a[i - 1], i - 1) + gain_by_moving(*a[i], i)
    new = gain_by_moving(*a[i - 1], i) + gain_by_moving(*a[i], i - 1)
    return new - old

for i in range(n):
    gain_by_swapping.update(i, (gain_by_swapping_with_pred(i), i))

while True:
    gain, i = gain_by_swapping.query(1, n)
    if gain <= 0:
        break
    a[i], a[i - 1] = a[i - 1], a[i]
    if i - 1 >= 1:
        gain_by_swapping.update(i - 1, (gain_by_swapping_with_pred(i - 1), i - 1))
    gain_by_swapping.update(i, (gain_by_swapping_with_pred(i), i))
    if i + 1 < n:
        gain_by_swapping.update(i + 1, (gain_by_swapping_with_pred(i + 1), i + 1))

print(sum(gain_by_moving(*a[i], i) for i in range(n)))

Submission status: Wrong Answer

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

def gain(i, j):
    val, index = a[i]
    return val * abs(index - j)

ans = 0
def do_swap():
    global ans
    for i in range(1, n):
        old = gain(i - 1, i - 1) + gain(i, i)
        new = gain(i - 1, i) + gain(i, i - 1)
        if old < new:
            a[i - 1], a[i] = a[i], a[i - 1]
            ans += new - old
            return True
    return False

while do_swap():
    pass

print(ans)

Submission status: Wrong Answer

Solution code:
#At Coder E: Active Infants

import random
#N = 10
#A = [random.randrange(1,10) for n in range(N)]
N = int(input())
A = list(map(int,input().split()))
sA = sorted(A)
f = [n for n in range(N)]
ans = 0
new = [0 for n in range(N)]

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

Submission status: Wrong Answer

Solution code:
#At Coder E: Active Infants

import random
N = int(input())
A = list(map(int,input().split()))
sA = sorted(A)
f = [n for n in range(N)]
ans = 0
new = [0 for n in range(N)]

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

Submission status: Wrong Answer

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

enumAs = list(enumerate(As))
maxscore = 0
for i in range(1, N):
    As_former = enumAs[:i]
    As_latter = enumAs[i:]
    possibleAs = sorted(As_latter, key = lambda t:t[1], reverse = True) + sorted(As_former, key = lambda t:t[1])
    score = sum(map(lambda A: A[1][1] * abs(A[0] - A[1][0]), enumerate(possibleAs)))
    maxscore = max(score, maxscore)

print(maxscore)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    dp = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(i+1):
            x,y = j,i-j
            dp[x+1][y] = max(dp[x+1][y],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-x)))
            dp[x][y+1] = max(dp[x][y+1],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-(N-y-1))))
    
    ans = 0
    for i in range(N+1):
        ans = max(ans,dp[i][i])
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    active = []
    
    for i in range(N):
        active.append((a[i],i))
        
    active.sort(key=itemgetter(0),reverse=True)
    dp = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(i+1):
            x,y = j,i-j
            dp[x+1][y] = max(dp[x+1][y],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-x)))
            dp[x][y+1] = max(dp[x][y+1],dp[x][y]+active[x+y][0]*(abs(active[x+y][1]-(N-y-1))))
    
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i])
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
b = sorted(a, reverse=True)
left, right = 0, 0
sum = 0
for i in range(n):
    index = a.index(b[i])
    a[index] = 0
    sum += b[i]* max((index - left), (((n - 1) - right) - index))
    if (index - left) < (((n - 1) - right) - index):
        right += 1
    else:
        left += 1
print(sum)

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())
ans=0
L=0
R=N-1

h=0
while h<=N-1:
    i=0
    B=[[0]]*N
    while i<=N-1:
        if i-L>R-i:
            B[i]=[A[i]*(i-L),L,i]
        elif i-L<R-i:
            B[i]=[A[i]*(R-i),R,i]
        else:
            B[i]=[A[i]*0,R,i]
        i+=1

    B=sorted(B)
    ans+=B[-1][0]
    if B[-1][1]==L:
        L+=1
    else:
        R-=1
    A[B[-1][2]]=0
    h+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
*A,=map(int,input().split())
ans=0
L=0
R=N-1
Siz=N-1

h=0
while h<=N-1:
    i=0
    B=[[0]]*N
    while i<=N-1:
        if i-L>=R-i:
            B[i]=[A[i]*(i-L),L,i]
        else:
            B[i]=[A[i]*(R-i),R,i]
        i+=1

    B=sorted(B)
    ans+=B[-1][0]
    if B[-1][1]==L:
        L+=1
    else:
        R-=1
    A[B[-1][2]]=0
    h+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = [int(i) for i in input().split(' ')]

AA = []
for i,a in enumerate(A):
    AA.append(tuple([a,i]))

AA = sorted(AA,reverse=True)

DP = np.zeros((N+1,N+1),dtype=np.int32)
for i,a in enumerate(AA):
    for x in range(i+1):
        y = i - x
        if x+ 1 <= N:
            DP[x+1,y] = max(DP[x+1,y], DP[x,y]+a[0]*abs(x-a[1]))
        if y+1 <= N:
            DP[x,y+1] = max(DP[x,y+1], DP[x,y]+a[0]*abs(N- 1 - y - a[1]))

MAX = 0
for x in range(N):
    y = N - x
    MAX = max(DP[x][y],MAX)

print(MAX)

Submission status: Wrong Answer

Solution code:
e=enumerate
n,a=open(0)
d=[0]+[-9e9]*2001
for j,(a,i)in e(sorted((-int(a),i)for i,a in e(a.split()))):d=[max(t-a*abs(~i-j+k+int(n)),d[k-1]-a*abs(~i+k))for k,t in e(d)]
print(max(d))

Submission status: Wrong Answer

Solution code:
from collections import deque


class Move:
    def __init__(self, rems, left, right, joy):
        self.rems = rems
        self.left = left
        self.right = right
        self.joy = joy


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

moves = deque([Move(set(range(n)), 0, n - 1, 0)])
max_joy = 0

while moves:
    move = moves.pop()
    
    if not move.rems:
        if move.joy > max_joy:
             max_joy = move.joy
             continue
    
    max_add_joy = 0
    max_moves = []
    
    for rem in move.rems:
        left_dist = abs(move.left - rem)
        right_dist = abs(move.right - rem)
        
        if left_dist >= right_dist:
            add_joy = a[rem] * left_dist
            
            if add_joy > max_add_joy:
                max_add_joy = add_joy
                max_moves = [(rem, 'l')]
            elif add_joy == max_add_joy:
                max_moves.append((rem, 'l'))
        
        if left_dist <= right_dist:
            add_joy = a[rem] * right_dist
            
            if add_joy > max_add_joy:
                max_add_joy = add_joy
                max_moves = [(rem, 'r')]
            elif add_joy == max_add_joy:
                max_moves.append((rem, 'r'))
        
        for max_move in max_moves:
            child_rem = set(move.rems)
            child_rem.remove(max_move[0])
            
            child_left = move.left
            child_right = move.right
            if max_move[1] == 'l':
                child_left += 1
            else:
                child_right -= 1
            
            moves.append(Move(child_rem, child_left, child_right, move.joy + max_add_joy))

print(max_joy)

Submission status: Wrong Answer

Solution code:
N=int(input())
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

INF = float('inf')
left=1
right=N
maxnum=0

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

dp[0][0]=0
for r in range(N+1):
    for l in range(N-r+1):
        dp[l][r]=max(dp[l][r-1]+As[l+r-1][0]*abs(N-r-As[l+r-1][1]),\
          dp[l-1][r]+As[l+r-1][0]*abs(l-1-As[l+r-1][1]))
        maxnum=dp[l][r] if maxnum<dp[l][r] else maxnum

    
print(maxnum)

Submission status: Wrong Answer

Solution code:
e=enumerate
n,a=open(0)
n=int(n)
d=[0]+[-9e9]*n
for j,(a,i)in e(sorted((int(a),i)for i,a in e(a.split()))[::-1]):d=[max(t+a*abs(~i-j+k+n),d[k-1]+a*abs(~i+k)if k else 0)for k,t in e(d)]
print(max(d))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
l = list(map(int, input().split()))
ans = 0
pos = [0] * n
for i in range(n):
    pos[i] = list(map(lambda x: abs(x - i), list(range(n))))
pos = np.array(pos)
pos_2 = np.zeros_like(pos)
for i in range(n):
    for j in range(n):
        pos_2[j, :] = pos[j, :] * l[j]
    ans += np.max(pos_2)
    index = pos_2.argmax()
    x = index // n
    y = index % n
    l[x] = 0
    pos[:, y] = 0
print(ans)

Submission status: Wrong Answer

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

dp = [[0]*(n+1) for _ in range(n+1)]
for i, (v, p) in enumerate(a):
    dp[i+1][0] = dp[i][0] + v*abs(0 - p)
    for j in range(1, i+1):
        dp[i+1][j] = max(dp[i][j] + v*abs(i - p),
                         dp[i][j-1] + v*abs((n-1 - (j-1)) - p))
    dp[i+1][i+1] = dp[i][i] + v*abs((n-1 - i) - p)
print(max(dp[n]))

Submission status: Wrong Answer

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

As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

left=1
right=N
sumnum=0

for i in As:
    move=0
    moveleft=abs(i[1]+1-left)
    moveright=abs(i[1]+1-right)
    if moveleft>moveright:
        move=moveleft
        left+=1
    else:
        move=moveright
        right=right-1
    sumnum+=move*i[0]
    
print(sumnum+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
actlist=list(map(int,input().split()))
As = sorted([(A, i) for i, A in enumerate(actlist)])[::-1]

left=1
right=N
sumnum=0

for i in As:
    move=0
    moveleft=abs(i[1]+1-left)
    moveright=abs(i[1]+1-right)
    if moveleft>moveright:
        move=moveleft
        left+=1
    else:
        move=moveright
        right=right-1
    sumnum+=move*i[0]
    
print(sumnum)

Submission status: Wrong Answer

Solution code:
import heapq
import math
import random
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, namedtuple, UserDict
from functools import cmp_to_key, lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**6+1)
write = sys.stdout.write
# input = sys.stdin.buffer.readline

MOD = 10**9 + 7


if __name__ == "__main__":
    n = int(input())
    nums = [int(c) for c in input().split()]
    nodes = [(-num, i) for i, num in enumerate(nums)]
    left, right = 0, n-1
    heapq.heapify(nodes)
    ans = 0
    while nodes:
        cur, i = heapq.heappop(nodes)
        if i >= (left + right)//2:
            ans += abs((i-left) * cur)
            left += 1
        else:
            ans += abs((i-right) * cur)
            right -= 1
        print(i, cur, left, right)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

A = [int(i) for i in input().split()]
left_index = 0
right_index = N-1

ans = 0

for i in range(N):
  update_num = 0
  max_num_index = -1
  for j in range(N):
    alpha = A[j] * max(abs(left_index-j),abs(right_index-j))
    if alpha >= update_num:
      update_num = alpha
      max_num_index = j
  if abs(left_index-max_num_index) > abs(right_index-max_num_index):
    left_index += 1
  else:
    right_index -= 1
  ans += update_num
  A[max_num_index] = -1


print(ans)

Submission status: Wrong Answer

Solution code:


n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**3)
		a = [rng(1, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	b = [0] * n
	max_happiness = []
	for i in range(n):
		b[i] = a[i]
		max_happiness.append(a[i]*max(i, n-1 - i))

	answer = 0
	left = 0
	right = n-1
	for i in range(n):
		k = max_happiness.index(max(max_happiness))
		answer += max_happiness[k]
		b[k] = 0
		if k - left < right - k:
			right -= 1
		else:
			left += 1 
		for i in range(n):
			max_happiness[i] = b[i] * max(i - left, right - i)

	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

# -*- coding: utf-8 -*-

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

inds=sorted(range(len(As)), key=lambda k: As[k])[::-1]


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

ds=[0]
for xy in range(1,N+1):
    nds=[0]*(xy+1)
    nds[-1]=ds[0]+As[inds[xy-1]]*(inds[xy-1]-(xy-1))
    nds[0]=ds[-1]+As[inds[xy-1]]*(N-xy-inds[xy-1])

    for x in range(1,xy):
        y=xy-x
        c1=ds[x-1]+As[inds[xy-1]]*abs(inds[xy-1]-(x-1))
        c2=ds[x]+As[inds[xy-1]]*abs(N-y-inds[xy-1])
        nds[x]=max(c1,c2)
    ds=nds.copy()
    #print(ds)


print(max(nds))
#print(ds)
#print(inds)