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:
import heapq
N = int(input())
A = list(map(int, input().split()))
used = [False] * N
fixed = [0, N-1]
ans = 0
for _ in range(N):
    H = []
    for i in range(N):
        if used[i]:
            continue

        val = 0
        r = 1
        if A[i] * abs(i-fixed[0]) >= A[i] * abs(i - fixed[1]):
            val = A[i] * abs(i - fixed[0])
            r = 0
        else:
            val = A[i] * abs(i - fixed[1])
            r = 1

        heapq.heappush(H, (-val, i, r))
    val, index, r = H[0]
    ans += (-val)
    used[index] = True
    if r == 0:
        fixed[0] += 1
    else:
        fixed[1] -= 1
    del H
    # print(val, index, used)
print(ans)

Submission status: Wrong Answer

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


def solve(N: int, A: "List[int]"):
    moved = [False]*N
    result = 0
    actual =[]
    upIndex = N-1
    downIndex = 0
    up = True
    while upIndex >= downIndex:
        i = 0
        if up:
            i = downIndex
        else:
            i = upIndex
        maxScore = 0
        maxScoreIndex = -1
        for j in range(N):
            if not moved[j] and maxScore < abs(i-j)*A[j]:
                maxScoreIndex = j
                maxScore = abs(i - j) * A[j]
        moved[maxScoreIndex] = True
        # actual.append(f"{maxScoreIndex}(Ai={A[maxScoreIndex]})")
        result+=maxScore
        if up:
            downIndex +=1
        else:
            upIndex -=1
        up=not up
    # print(actual)
    print(result)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
n = int(input())
a = np.array(list(map(int, input().split())))

selected = [False]*n
left = 0
right = n-1
ans = 0
d = np.array([max(abs(i - left), abs(right - i)) for i in range(n)])
for _ in range(n):
    t = np.array([v if not selected[i] else 0 for i, v in enumerate(a)])
    r = t * d
    index = np.where(r == np.max(r))[0][0]
    selected[index] = True
    ans += r[index]
    if abs(index - left) == abs(index - right):
        if np.sum(t[:index]) > np.sum(t[index+1:]):
            right -= 1
        else:
            left += 1
    if d[index] == abs(index - left):
        left += 1
    else:
        right -= 1

print(ans)

Submission status: Wrong Answer

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

B = sorted(A, reverse=True)
C = [False for _ in range(len(A))]
ans = 0

for i in range(len(B)):
    x = A.index(B[i])
    A[x]=0
    p = x
    tmp = 0
    for j in range(len(C)):
        if abs(x-j) > tmp and C[j] == False:
            tmp = abs(x-j)
            p=j
    C[p] = True
    ans += B[i]* abs(x-p)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

n=int(input())
a=list(map(int,input().split()))
gg=a.copy()
tmp=a.copy()
tmp.sort()

ans=deque([tmp[0]])

for i in range(1,n):
    if a.index(tmp[i])<=n//2-1:
        ans.append(tmp[i])
        a[a.index(tmp[i])]+=float('inf')
    else:
        ans.appendleft(tmp[i])
        a[a.index(tmp[i])] += float('inf')

ans=list(ans)

cnt=0
for i in range(n):
    y=gg.index(ans[i])
    cnt+=abs(y-i)*ans[i]
    gg[y]+=float('inf')
print(cnt)

Submission status: Wrong Answer

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

D = [[0] * 2 for _ in range(N)]

for i in range(N):
  D[i] = [i, A[i]]

D.sort(key = lambda x: x[1], reverse = True)

ans = 0
l = 0
r = 0
for i in D:
  t, k = i
  na = (t - l) * k
  su = (N - t - r - 1) * k
  A[t] = 0
  ln = 0
  rn = 0
  for j in range(t):
    ln += A[j]
  for j in range(t, N):
    rn += A[t]
  if na + ln > su + rn:
    ans += na
    l += 1
  else:
    ans += su
    r += 1

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([num[0] for num in 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:
n = int(input())
ls_a = list(map(int,input().split()))
 
import numpy as np
nd = np.array([np.linspace(1,n,n),ls_a])
 
nd = nd[:, np.argsort(nd[1])[::-1]]
sum_ = 1
left = 1
right = n
 
for i, a in zip(nd[0], nd[1]):
    # 左か右か
    l = i-left
    r = right-i
    if l <= r:
        right -= 1
        sum_ += a*abs(r)
        print(a, i, l, r, sum_,'if')
    else:
        left += 1
        sum_ += a*abs(l)
        print(a, i, l, r, sum_, 'else')
print(sum_)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
A2 = sorted(A, reverse=True)
A2 * N
answer = 0
for i,value in enumerate(A):
    for i2,value in enumerate(A2):
        answer += value * (i - i2)
print(answer)

Submission status: Wrong Answer

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

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

for _ in range(N + 10):
    for i in range(N - 1):
        j = i + 1
        s, a = ans[i]
        t, b = ans[j]

        new = a * abs(s - j) + b * abs(t - i)
        old = a * abs(s - i) + b * abs(t - j)

        if new > old:
            ans[i], ans[j] = ans[j], ans[i]

res = 0
for i, (s, a) in enumerate(ans):
    res += a * abs(i - s)
print(res)

Submission status: Wrong Answer

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


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

ai = [(a, i) for i,a in enumerate(A)]
ai.sort(reverse=True)
_, indices = zip(*ai)

u = [0, N - 1]


ans = 0
for i in range(N):
    ind = indices[i]
    if u[0] == u[1]:
        t = 0
    else:
        if ind - u[0] < u[1] - ind:
            t = 1
        elif ind - u[0] > u[1] - ind:
            t = 0
        else:
            if indices[i + 1] - u[0] < u[1] - indices[i + 1]:
                t = 0
            else:
                t = 1
    
    ans += A[ind] * abs(u[t] - ind)
    if t == 0:
        u[t] += 1
    else:
        u[t] -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
nums=list(map(int,input().split()))
ans=0
r=0
l=n-1
for i in range(n):
    maxh=0
    pos=0
    lr=0
    c=(l+r)/2
    for j in range(n):
        happy=nums[j]*max(j-r,l-j)
        if happy>maxh or (happy==maxh and nums[j]>nums[pos]):
            maxh=happy
            pos=j
    if c.is_integer() and pos==c:
        forsum=0
        for j in range(int(c)):
            forsum+=nums[j]
        backsum=sum(nums)-forsum-nums[int(c)]
        if forsum>=backsum:
            lr=1
        else:
            lr=2
    if pos>c or lr==1:
        r+=1
    else:
        l-=1
    ans+=maxh
    nums[pos]=0
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

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

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

for _ in range(N + 10):
    for i in range(N - 1):
        j = i + 1
        s, a = ans[i]
        t, b = ans[j]

        new = a * abs(s - j) + b * abs(t - i)
        old = a * abs(s - i) + b * abs(t - j)

        if new > old:
            ans[i], ans[j] = ans[j], ans[i]

res = 0
for i, (s, a) in enumerate(ans):
    res += a * abs(i - s)
print(res)

Submission status: Wrong Answer

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

import numpy as np
nd = np.array([np.linspace(1,n,n),ls_a])

nd = nd[:, np.argsort(nd[1])[::-1]]
sum_ = 0
left = 1
right = n

for i, a in zip(nd[0], nd[1]):
    # 左か右か
    l = i-left
    r = right-i
    if l <= r:
        right -= 1
        sum_ += a*abs(r)
        print(a, i, l, r, sum_,'if')
    else:
        left += 1
        sum_ += a*abs(l)
        print(a, i, l, r, sum_, 'else')
print(sum_)

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
n = int(input())
a = np.array(list(map(int, input().split())))

selected = [False]*n
left = 0
right = n-1
ans = 0
for _ in range(n):
    d = np.array([max(abs(i-left), abs(right - i)) if not selected[i] else 0 for i in range(n)])
    r = a * d
    index = np.where(r == np.max(r))[0][0]
    selected[index] = True
    ans += r[index]
    if abs(index - left) == abs(index - right):
        if np.sum(r[:index]) > np.sum(r[index+1:]):
            right -= 1
        else:
            left += 1
    if d[index] == abs(index - left):
        left += 1
    else:
        right -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = []
for i, v in enumerate(a):
    b.append((v, i))
b.sort()
l = 0
r = n - 1
ans = 0
while len(b) > 0:
    v, i = b.pop()
    if abs(i - l) > abs(i - r):
        ans += abs(i - l) * v
        l += 1
    else:
        ans += abs(i - r) * v
        r -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

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

place = [False] * N
child = [False] * N

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

def main():
    ans = 0
    for _ in range(N):
        MAXH = {"happy":-1, "place":0, "child":0}
        for i in range(N):
            if place[i]: continue
            h, c = heappop(info[i])
            if MAXH["happy"] < (-1) * h:
                MAXH["happy"] = (-1) * h
                MAXH["place"] = i
                MAXH["child"] = c
            heappush(info[i], (h, c))
        
        place[MAXH["place"]] = True
        child[MAXH["child"]] = True

        heappop(info[MAXH["place"]])

        ans += MAXH["happy"]

        for i in range(N):
            if place[i]: continue
            while info[i]:
                h, c = heappop(info[i])
                if not child[c]:
                    heappush(info[i], (h, c))
                    break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
As = [int(s) for s in input().split()]

l = 0
r = N - 1

S = 0
for k in range(N):
    m, mp, il = 0, 0, False
    for p in range(N):
        v = As[p]

        tl = v * abs(l - p)
        tr = v * abs(r - p)
        tm = max(tl, tr)
        til = tl > tr

        if m < tm:
            m = tm
            mp = p
            il = til

    S += m
    As[mp] = 0
    if il:
        l += 1
    else:
        r -= 1

print(S)

Submission status: Wrong Answer

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

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

score = 0
for _ in range(N):
    for i in range(N-1):
        a, b = l[i], l[i+1]
        a_np = abs(a[0]-i)*a[1]
        b_np = abs(b[0]-(i+1))*b[1]
        np = a_np + b_np
        a_sp = abs(a[0]-(i+1))*a[1]
        b_sp = abs(b[0]-i)*b[1]
        sp = a_sp + b_sp
        diff = sp - np
        if diff >= 0:
            l[i], l[i+1] = l[i+1], l[i]
            score += diff

print(score)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = [(A[i], i) for i in range(N)]
res = 0
for i in range(N - 1):
    tres = 0
    l = L[: i + 1]
    r = L[i + 1 :]
    l.sort()
    r.sort(reverse=True)
    for j in range(i + 1):
        tres += abs(j + (N - i - 1) - l[j][1]) * l[j][0]
    for j in range(N - i - 1):
        tres += abs(j - r[j][1]) * r[j][0]
    res = max(res, tres)
print(res)

Submission status: Wrong Answer

Solution code:
import sys,math,copy,queue,itertools,bisect
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
A = LI()

ure = 0
top = 0
bot = N-1
for k in range(N):
    max_u = 0
    max_i = -1
    max_tb = -1
    for i in range(N):
        u1 = abs(top-i) * A[i]
        u2 = abs(bot-i) * A[i]
        if u1 > u2:
            if u1 > max_u:
                max_u = u1
                max_i = i
                max_tb = 1
        else:
            if u2 > max_u:
                max_u = u2
                max_i = i
                max_tb = 2
    ure += max_u
    A[max_i] = 0
    if max_tb == 1:
        top += 1
    else:
        bot -= 1
print (ure)

Submission status: Wrong Answer

Solution code:

N=int(input())
a=list(map(int,input().split()))
b = [(val,i) for i,val in enumerate(a)]
c = sorted(b, reverse=True)
res = [(0,0)]*N
left = 0
right = 0
ans = 0
now1=(-1,-1)
now2=(-1,-1)
for j,(val,i) in enumerate(c):
    if j%2==0:
        now1 = (val,i)
        if j==N-1:
            res[N//2] = now1
            # 最後
    else:
        now2 = (val,i)
        # swap?
        if now1[1] > now2[1]:
            res[j//2] = now1
            res[N-1-j//2] = now2
        else:
            res[j // 2] = now2
            res[N - 1 - j // 2] = now1
            
for j,(val,i) in enumerate(res):
    ans += val*abs(j-b[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
As = [int(s) for s in input().split()]

l = 0
r = N - 1

S = 0
for k in range(N):
    m, mp, il = 0, 0, False
    for p in range(N):
        v = As[p]

        tm = v * abs(l - p)
        if m < tm:
            m = tm
            mp = p
            il = True

        tm = v * abs(r - p)
        if m < tm:
            m = tm
            mp = p
            il = False

    S += m
    As[mp] = 0
    if il:
        l += 1
    else:
        r -= 1

print(S)

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
_rr = sorted(aa, reverse=True)
for i in range(1, N):
    ll = np.array(sorted(aa[:i]))
    _rr.remove(aa[i - 1])
    rr = np.array(_rr)
    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:
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))

place = [False] * N
child = [False] * N

ans = 0
for _ in range(N):
    MAXH = {"happy":-1, "place":0, "child":0}
    for i in range(N):
        if place[i]: continue
        if MAXH["happy"] < (-1) * info[i][0][0]:
            MAXH["happy"] = (-1) * info[i][0][0]
            MAXH["child"] = info[i][0][1]
            MAXH["place"] = i
    
    place[MAXH["place"]] = True
    child[MAXH["child"]] = True

    heappop(info[MAXH["place"]])

    ans += MAXH["happy"]

    for i in range(N):
        if place[i]: continue
        while info[i]:
            h, c = heappop(info[i])
            if not child[c]:
                heappush(info[i], (h, c))
                break
            
print(ans)

Submission status: Wrong Answer

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

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

B = [[A[i], i] for i in range(n)]
B.sort(reverse=True)

# S = [A[0]]
# for i in range(1, n):
#     S.append(A[i] + S[-1])
l = 0
r = n-1
ans = 0
for i in range(n):
    ind = B[i][1]
    # print(ind)
    if r > ind and B[i][0] * ((r-ind) - (ind-l)) + sum(A[(ind+1):]) - sum(A[:ind]) >= 0:
        # print(ind,"r")
        ans += B[i][0] * ((r-ind))
        r -= 1
        A[ind] = 0
    else:
        ans += B[i][0] * ((ind-l))
        # print(ind,"l")
        l += 1
        A[ind] = 0
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
activeness = np.array(input().split(), dtype=np.int64)

left = 0
right = N - 1
total = 0

while activeness.any():
    happiness_left = activeness * np.abs(np.arange(N) - left)
    left_argmax = happiness_left.argmax()
    left_max = happiness_left[left_argmax]

    happiness_right = activeness * np.abs(np.arange(N) - right)
    right_argmax = happiness_right.argmax()
    right_max = happiness_right[right_argmax]

    if left == right and left_max == right_max:
        total += left_max
        break

    if left_max > right_max:
        total += left_max
        left += 1
        activeness[left_argmax] = 0
    else:
        total += right_max
        right -= 1
        activeness[right_argmax] = 0

print(total)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=0
for k in range(N):
    if k%2==0:
        left=[]
        for j in range(N):
            left.append(A[j]*abs(j-k//2))
        ans+=max(left)
        max_index=left.index(max(left))
        A[max_index]=0
    
    if k%2==1:
        right=[]
        for j in range(N):
            right.append(A[j]*abs(N-1-j-k//2))
        ans+=max(right)
        max_index=right.index(max(right))
        A[max_index]=0
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
C=[False]*n

l,r=0,n-1
ans=0
for _ in range(n):
  score=0
  ii=0
  for i in range(n):
    if C[i]:
      continue
    else:
      a=A[i]
      if score<a*max(abs(l-i),abs(r-i)):
        score=a*max(abs(l-i),abs(r-i))
        ii=i
        if abs(l-i)>abs(r-i):
          dir=-1
        else:
          dir=1

  ans+=score
  if dir==-1:
    l+=1
  else:
    r-=1
  C[ii]=True
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
c = [True for i in range(n)]
#print(a)
#print(b)
m = 0
M = n-1
ans = 0
for i in range(n-1,-1,-1):
    now = b[i]
    for j in range(n):
        if now == a[j] and c[j]:
            idx = j
            c[j] = False
            break
    if M-idx > idx-m:
        ans += a[idx]*(M-idx)
        M -= 1
    else:
        ans += a[idx]*(idx-m)
        m += 1

print(ans)

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 * abs(i - l)
    r_sum += val * abs(r - i)
    if l_sum >= r_sum:
        ans += val * abs(i - l)
        l += 1
    else:
        ans += val * abs(r - i)
        r -= 1
    bit.add(i, -val)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1,n):
    left = [[a[i], i] for i in range(i)]
    right = [[a[i], i] for i in range(i, n)]
    left.sort()
    right.sort(reverse=True)
    tmp = []
    for _,i in right:
        tmp.append(i)
    for _,i in left:
        tmp.append(i)
    ans_tmp = 0
    for i in range(n):
        ans_tmp += a[tmp[i]]*abs(i-tmp[i])
    ans = max(ans, ans_tmp)
print(ans)

Submission status: Wrong Answer

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

fun = [[0]*n for _ in range(n)]
freq = dict()
el = set()
for i in range(n):
    for j in range(n):
        cost = a[i]*abs(i-j)
        fun[i][j]= cost
        el.add(cost)
        try:
            freq[cost].append((i,j))
        except:
            freq[cost] = [(i,j)]

el = list(el)
el.sort(reverse=True)
ans=0
usedi=set()
usedj=set()
for cost in el:
    for i,j in freq[cost]:
        if not (i in usedi or j in usedj):
            ans+=cost
            usedi.add(i)
            usedj.add(j)

print(ans)
# for i in range(n):
#     print(*fun[i])

Submission status: Wrong Answer

Solution code:
def cur(ans,l,r,p):
    for i in range(p,n):
        a=inf[i][0];x=inf[i][1]
        if x-l>=r-x: ans[l]=[a,x];l+=1
        elif x-l<r-x: ans[r]=[a,x];r-=1
        else:
            tmpansl=[[ans[i][0],ans[i][1]] for i in range(n)]
            tmpansr=[[ans[i][0],ans[i][1]] for i in range(n)]
            tmpansl[l]=[a,x]
            tmpansr[r]=[a,x]
            return max(cur(tmpansl,l+1,r,p+1),cur(tmpansr,l,r-1,p+1))

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



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

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

Submission status: Wrong Answer

Solution code:
import sys
n = int(sys.stdin.readline().strip())
A = map(int, sys.stdin.readline().split())
A = list(A)
Mhappy = -1
for mv in range(1, n):
    happy = 0
    for i, a in enumerate(A):
        happy += a * abs( (i+mv) % n - i)
    #print(mv, happy)
    Mhappy = max(happy, Mhappy)
print(Mhappy)

Submission status: Wrong Answer

Solution code:
NN = 202020
MOD = 10**9+7
# MOD = 998244353
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))

que.sort()
ans = [-1]*len(A)
seen = set()
for t in range(len(que)):
    val, _, i, j = que[t]
    if ans[j] == -1 and i not in seen:
        ans[j] = -val
        seen.add(i)
    if len(seen) >= len(A):
        break
    # print(val, j, ans)

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import heapq
n = int(input())
a = np.array(list(map(int, input().split())))

selected = [False]*n
left = 0
right = n-1
ans = 0
for _ in range(n):
    d = np.array([max(i-left, right - i) if not selected[i] else 0 for i in range(n)])
    r = a * d
    index = np.where(r == np.max(r))[0][0]
    selected[index] = True
    ans += r[index]
    if d[index] == index - left:
        left += 1
    else:
        right -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
l,r=0,n-1
ans=0
checked=[0]*n
for _ in range(n):
  pos,val=0,0
  for i in range(n):
    if checked[i]==1:
      continue
    tmp=arr[i]*max(i-l,r-i)
    if tmp>val:
      pos=i
      val=tmp
  checked[pos]=1
  ans+=val
  if pos-l>r-pos:
    l+=1
  else:
    r-=1
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    arr = [int(e) for e in input().split(' ')]

    ls = []
    for i in range(0, n):
        for j in range(0, n):
            ls.append((i, j, arr[i] * abs(i - j)))
    
    ls = list(sorted(ls, key=lambda x: x[2], reverse=True))
    ch = set()
    pos = set()

    s = 0
    for tp in ls:
        i, j, c = tp
        if i in ch or j in pos:
            continue
        s += c
        ch.add(i)
        pos.add(j)

    print(s)
    return 0

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def cur(ans,l,r,p):
    for i in range(p,n):
        a=inf[i][0];x=inf[i][1]
        if x-l>=r-x: ans[l]=[a,x];l+=1
        elif x-l<r-x: ans[r]=[a,x];r-=1
        else:
            tmpansl=[[ans[i][0],ans[i][1]] for i in range(n)]
            tmpansr=[[ans[i][0],ans[i][1]] for i in range(n)]
            tmpansl[l]=[a,x]
            tmpansr[r]=[a,x]
            return max(cur(tmpansl,l+1,r,p+1),cur(tmpansr,l,r-1,p+1))

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



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

print(cur(ans,0,n-1,0)+1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    ii=list(range(n))
    for i in range(n):
        mx=0
        mxj=-1
        for j in range(n):
            i0=ii[i]
            i1=ii[j]
            cur=(abs(j-i0)-abs(i-i0))*aa[i]+(abs(i-i1)-abs(j-i1))*aa[j]
            if cur>mx:
                mx=cur
                mxj=j
        if mx:
            aa[i],aa[mxj]=aa[mxj],aa[i]
            ii[i],ii[mxj]=ii[mxj],ii[i]
    ans=0
    for i in range(n):
        ans+=abs(i-ii[i])*aa[i]
    print(ans)

main()

Submission status: Wrong Answer

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

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    
    
    n = ii()
    a = lmi()
    left = 0
    right = n-1
    determined = [False] * n
    ans = 0
    for _ in range(n):
        memo = [[-1, 0] for _ in range(n)]
        for j in range(n):
            if not determined[j]:
                dest = left if abs(j-left) > abs(right-j) else right
                memo[j][0] = a[j] * max(abs(j-left), abs(right-j))
                memo[j][1] = dest
        max_ind = 0
        max_val = 0
        for i, elm in enumerate(memo):
            if elm[0] > max_val:
                max_val = elm[0]
                max_ind = i
        ans += max_val
        determined[max_ind] = True
        dest = memo[max_ind][1]
        if dest == left:
            left += 1
        else:
            right -= 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

l = 0
r = N-1
ans = 0
for i in range(N):
    c = -1
    cand = []
    for j in range(N):
        if A[j]==0:
            continue
        if j-l >= r-j:
            if c < A[j]*(j-l):
                c = A[j]*(j-l)
                cand = [j,l]
        else:
            if c < A[j]*(r-j):
                c = A[j]*(r-j)
                cand = [j,r]
    if cand[1]==l:
        l += 1
    if cand[1]==r:
        r -= 1
    A[cand[0]] = 0
    ans += c

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

que = []
for i in range(N):
    heapq.heappush(que, (-A[i], i))

l = 0; r = N-1
ans = 0
while que:
    e = heapq.heappop(que)
    x = e[1]
    if abs(r-x) >= abs(x-l):
        ans += abs(e[0]*(r-x))
        r -= 1
    else:
        ans += abs(e[0]*(x-l))
        l += 1
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 = -1
        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
        ans += maxValue
        used[toMove] = True            
        if abs(toMove - first) >= abs(toMove - back): first += 1
        else: back -= 1
        
        #print(toMove, ans)
    print(ans)

    return 0

if __name__ == "__main__":
    solve()