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 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 _ in range(2):
        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:
import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
a = [(a_i, i+1) for i, a_i in enumerate(a)]
a.sort(reverse=True)


l, r = 1, n
cnt = 0
for p in range(n):
    a_i, i = a[p]
    if p == n-1:
        cnt += abs(l - i)
        continue
    if abs(l - i) == abs(r - i):
        cnt += a_i * abs(l - i)
        a_i2, i2 = a[p + 1]
        if abs(l - i2) < abs(r - i2):
            l += 1
        else:
            r -= 1

    elif abs(l - i) > abs(r - i):
        cnt += a_i * abs(l - i)
        l += 1

    elif abs(l - i) < abs(r - i):
        cnt += a_i * abs(r - i)
        r -= 1

print(cnt+1)

Submission status: Wrong Answer

Solution code:
def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines
    from heapq import heappush, heappop
    N = int(input())
    A = list(map(int, input().split()))

    done = [0] * N
    cnt = 0

    for i in range(N // 2):
        l = i
        r = N - 1 - i
        q = []

        for j in range(N):
            if done[j]:
                continue
            heappush(q, (-A[j] * abs(l - j), j, 'l'))
            heappush(q, (-A[j] * abs(r - j), j, 'r'))

        rflag = 0
        lflag = 0
        while not (lflag & rflag):
            c, j, pos = heappop(q)
            if done[j] != 1 and ((rflag == 0 and pos == 'r') or (lflag == 0 and pos == 'l')):
                cnt += -c
                done[j] = 1
                if pos == 'r':
                    rflag = 1
                else:
                    lflag = 1

    if N % 2 == 1:
        for idx, flag in enumerate(done):
            if flag == 0:
                break
        cnt += A[idx] * abs(idx - (N // 2 + 1))

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
start = 0
end = n - 1
ans = 0
for i in range(0, n):
    max_score = -1
    iti = -1
    flag = 0
    for j in range(0, n):
        if max_score < a_list[j] * abs(j - start):
            max_score = a_list[j] * abs(j - start)
            iti = j
            flag = -1
        if max_score < a_list[j] * abs(end - j):
            max_score = a_list[j] * abs(end - j)
            iti = j
            flag = 1
    a_list[iti] = 0
    if flag == -1:
        # print(iti+1, start+1, max_score)
        ans += max_score
        start += 1
        
    elif flag == 1:
        # print(iti+1, end+1, max_score)
        ans += max_score
        end -= 1
print(ans)

Submission status: Wrong Answer

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

AA=[]
for i in range(N):
    AA.append([A[i],i])
AA.sort(reverse=True)

f=0
l=N-1
ans=0

for j in range(N):
    if abs(AA[j][1]-f)>abs(l-AA[j][1]):
        ans+=AA[j][0]*abs(AA[j][1]-f)
        f+=1
    else:
        ans+=AA[j][0]*abs(l-AA[j][1])
        l-=1
print(ans+1)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import heapq
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

start = [False]*(N+1)
visited = [False]*(N+1)

heappop = heapq.heappop
heappush = heapq.heappush
d = []

for i in range(N):
  for j in range(N):
    heappush(d, (-a[i]*abs(i-j), i, j)) # (score, st, ed)

ans = 0
while d:
  num,st,ed = heappop(d)
  if start[st] == False and visited[ed] == False:
    ans += num
    start[st] = True
    visited[ed] = True
print(-ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 最小費用流(minimum cost flow)
import time
start = time.time()
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.G = [[] for i in range(n)]

    def addEdge(self, f, t, cap, cost):
        # [to, cap, cost, rev]
        self.G[f].append([t, cap, cost, len(self.G[t])])
        self.G[t].append([f, 0, -cost, len(self.G[f])-1])

    def minCostFlow(self, s, t, f):
        n = self.n
        G = self.G
        prevv = [0]*n; preve = [0]*n
        INF = 10**9+7

        res = 0
        while f:
            dist = [INF]*n
            dist[s] = 0
            update = 1
            while update:
                update = 0
                for v in range(n):
                    if dist[v] == INF:
                        continue
                    gv = G[v]
                    for i in range(len(gv)):
                        to, cap, cost, rev = gv[i]
                        if cap > 0 and dist[v] + cost < dist[to]:
                            dist[to] = dist[v] + cost
                            prevv[to] = v; preve[to] = i
                            update = 1
            if dist[t] == INF:
                return -1

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

n = int(input())
a = list(map(int, input().split()))
flow = MinCostFlow(2*n+2)
for i in range(n):
    for j in range(n):
        flow.addEdge(i+1,n+j+1,1,-a[i]*abs(i-j))
for i in range(n):
    flow.addEdge(0,i+1,1,0)
    flow.addEdge(n+i+1,2*n+1,1,0)

ans = flow.minCostFlow(0,2*n+1,n)
print(-ans)

Submission status: Wrong Answer

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

import heapq

ans = 0
doneX = [False]*N
doneY = [False]*N
hq = [(-a*abs(x-y),-a,x,y) for x,a in enumerate(A) for y in range(N)]
hq.sort()
heapq.heapify(hq)

hpop = heapq.heappop

while hq:
    a,_,x,y = hpop(hq)
    if doneX[x] or doneY[y]:continue
    ans -= a
    doneX[x] = True
    doneY[y] = True
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from math import pi
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    left = 0
    right = N-1
    ans = 0
    used = [False]*N
    while right - left >0:
        l_max = -1
        l_index = 0
        l_n_max = -2
        l_n_index = 0
        r_max = -1
        r_index = 0
        r_n_max = -2
        r_n_index = 0
        for i in range(N):
            if used[i] == False:
                l = A[i] * abs(left-i)
                r = A[i] * abs(right - i)
                if l_max<l:
                    l_n_index = l_index
                    l_n_max = l_max
                    l_index = i
                    l_max = l
                elif l_n_max<l:
                    l_n_index = i
                    l_n_max = l
                if r_max<r:
                    r_n_index = r_index
                    r_n_max = r_max
                    r_index = i
                    r_max = r
                elif r_n_max<r:
                    r_n_index = i
                    r_n_max = r
        if l_index == r_index:
            if right-left==1:
                ans += l_max
                break
            if l_n_max>r_n_max:
                ans += l_n_max + r_max
                used[l_n_index]=True
                used[r_index]=True
                left += 1
                right -=1
            else:
                ans += r_n_max + l_max
                used[l_index] = True
                used[r_n_index]=True
                left+=1
                right-=1
        else:
            ans += l_max + r_max
            used[r_index]=True
            used[l_index]=True
            left += 1
            right -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n = int(input())
a = list(map(int, input().split()))
a = [(a_i, i+1) for i, a_i in enumerate(a)]
a.sort(reverse=True)


l, r = 1, n
cnt = 0
for p in range(n):
    a_i, i = a[p]
    if p == n-1:
        cnt += abs(l - i)
        continue
    if abs(l - i) == abs(r - i):
        cnt += a_i * abs(l - i)
        a_i2, i2 = a[p + 1]
        if abs(l - i2) < abs(r - i2):
            l += 1
        else:
            r -= 1

    elif abs(l - i) > abs(r - i):
        cnt += a_i * abs(l - i)
        l += 1

    elif abs(l - i) < abs(r - i):
        cnt += a_i * abs(r - i)
        r -= 1

print(cnt)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=[0]
ure=0
s=[]
for i in range(2,N+1):#i人使う
  loc=0
  ure=A[i-1]*(i-1)#ok
  #print()
  for j in range(i-1):#ok
    ure+=A[l[j]]*abs(l[j]-(j+1))#
  #print(ure)
  for j in range(i-1):#i+1個の入る場所
    if(ure<=ure-A[i-1]*(j+1)-A[l[j]]*abs(l[j]-(j+1))+A[l[j]]*abs(l[j]-j)):
      loc=j+1
      ure=ure-A[i-1]*(j+1)-A[l[j]]*abs(l[j]-(j+1))+A[l[j]]*abs(l[j]-j)
  ss=l[:]
  l=l[:loc]
  l.append(i-1)
  l.extend(ss[loc:])
  #print(l)
  #print("owari")
print(ure)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_2 = []
for i in range(n):
    a_2.append([i, a[i]])
a_2.sort(key=lambda x: x[1], reverse= True)
x = 0
y = n-1
ans = 0
for i in range(n):
    abs_x = abs(x-a_2[i][0])
    abs_y = abs(y-a_2[i][0])
    if i == n-1:
        ans += a_2[i][1] * abs_x
        continue
    if abs_x > abs_y:
        x += 1
        ans += a_2[i][1] * abs_x
    elif abs_x < abs_y:
        y -= 1
        ans += a_2[i][1] * abs_y
    else:
        if abs(x-a_2[i+1][0]) > abs(y-a_2[i+1][0]):
            y -= 1
            ans += a_2[i][1] * abs_y
        else:
            x += 1
            ans += a_2[i][1] * abs_x
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    left = 0
    right = n - 1

    ans = 0
    used = [False] * n
    pos = [0] * n

    for _ in range(n):
        xmax = [0] * n

        for i in range(n):
            if used[i]:
                continue

            if i >= left:
                l = abs(i - left) * a[i]
            else:
                l = 0

            if i <= right:
                r = abs(i - right) * a[i]
            else:
                r = 0

            if l > r:
                xmax[i] = l
                pos[i] = True
            else:
                xmax[i] = r
                pos[i] = False

        m = max(xmax)
        ans += m
        idx = xmax.index(m)
        used[idx] = True

        if pos[idx]:
            left += 1
        else:
            right -= 1

    print(ans)


if __name__ == '__main__':
    main()

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
  ss=0
  for i in range(n):
    if C[i]:
      continue
    else:
      a=A[i]
      if score<a*max(abs(l-i),abs(r-i)) or (score==a*max(abs(l-i),abs(r-i)) and ss>a):
        score=a*max(abs(l-i),abs(r-i))
        ii=i
        ss=a
        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:
def solve(n, aaa):
    aaa_with_idx = list(zip(aaa, range(n)))
    n2 = n // 2
    ans = 0
    for i in range(n2 + 1 + n % 2):
        srt = sorted(aaa_with_idx[i:], reverse=True)
        left = srt[:n2]
        right = sorted(srt[n2:] + aaa_with_idx[:i])
        tmp = sum(a * abs(j - k) for j, (a, k) in enumerate(left + right))
        ans = max(ans, tmp)
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(max(solve(n, aaa), solve(n, reversed(aaa))))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
newA=[]
for i,a in enumerate(A):
    newA.append((a,i))
newA=sorted(newA, key=lambda x:x[1], reverse=True)
newA=sorted(newA, reverse=True)
#print(newA)
l1=1
r1=n-1
l2=0
r2=n-2
ans1=0
ans2=0
for i in range(len(newA)):
    if i==0:
        ans1+=newA[i][0]*abs(newA[i][1])
    else:
        if abs(newA[i][1]-l1)>abs(newA[i][1]-r1):
            ans1+=newA[i][0]*abs(newA[i][1]-l1)
            l1+=1
        else:
            ans1+=newA[i][0]*abs(newA[i][1]-r1)
            r1-=1

for i in range(len(newA)):
    if i==0:
        ans2+=newA[i][0]*abs(newA[i][1]-(n-1))
    else:
        if abs(newA[i][1]-l2)>abs(newA[i][1]-r2):
            ans2+=newA[i][0]*abs(newA[i][1]-l2)
            l2+=1
        else:
            ans2+=newA[i][0]*abs(newA[i][1]-r2)
            r2-=1

print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
import sys 
try:
	sys.stdin = open('input.txt', 'r') 
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
for tt in range(1):
	n = int(input())
	# a,b = map(int,input().split())
	arr = list(map(int,input().split()))
	i = 0
	j = 1
	right = n-1
	left = 0
	arr = list(enumerate(arr))
	arr.sort(reverse = True, key = lambda x:(x[1],x[0]))
	# print(arr)
	ans = 0 
	while i<n and j<n:
		first = max(arr[i][1] * (abs(arr[i][0] - right)), arr[i][1] * (abs(arr[i][0] - left)))
		second = max(arr[j][1] * (abs(arr[j][0] - right)), arr[j][1] * (abs(arr[j][0] - left)))
		# print(first,second)
		if first > second:
			if abs(arr[i][0] - right) > abs(arr[i][0] - left):
				right -= 1
			else:
				left += 1
			ans += first
			i=j
			j+=1
		else:
			if abs(arr[j][0] - right) > abs(arr[j][0] - left):
				right -= 1
			else:
				left += 1
			j+=1
			ans += second
		# print("i and j", i,j)
		# print("Right Left", right, left)
		# print()
	# print(ans,i,j,right,left)
	if i<n:
		ans += max(arr[i][1] * (abs(arr[i][0] - right)), arr[i][1] * (abs(arr[i][0] - left)))
	if j<n:
		ans += max(arr[j][1] * (abs(arr[j][0] - right)), arr[j][1] * (abs(arr[j][0] - left)))
	# print(i,j,right,left)
	print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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


# A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)


# A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx & (-idx)
    return res_sum


# Ai += x O(logN)
def BIT_update(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx & (-idx)
    return


i_to_a = [[a, -i] for i, a in enumerate(A)]
i_to_a.sort(reverse=True)

ans = 0
l = 0
r = N-1

for a, i in i_to_a:
    i = -i
    left = ACM[i] - a
    left -= BIT_query(i+1)
    left += a * abs(i - l)

    right = ACM[N - 1] - ACM[i]
    right -= BIT_query(N) - BIT_query(i + 1)
    right += a * abs(r - i)

    if right < left:
        ans += a * abs(i - l)
        BIT_update(l+1, a)
        l += 1
    else:
        ans += a * abs(r - i)
        BIT_update(r+1, a)
        r -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,*a=map(int,open(0).read().split())
b=list(range(n))
def f():
	for i, x in enumerate(a):
		for j in range(n):
			if abs(b[i]-i)*a[i]+abs(b[j]-j)*a[j]<abs(b[j]-i)*a[i]+abs(b[i]-j)*a[j]:
				b[i],b[j]=b[j],b[i]
exec("f();"*15)
print(sum(x*abs(i-b[i]) for i,x in enumerate(a)))

Submission status: Wrong Answer

Solution code:
import math
import fractions
import collections
import itertools
import pprint

N=int(input())
A=list(map(int,input().split()))
table=[[-1 for _ in range(N)] for _ in range(N)]
st=[-1]*N
en=[-1]*N
s=[]
for i in range(N):
    for j in range(N):
        table[i][j]=A[i]*abs(i-j)
        s.append([table[i][j],[i,j]])
s.sort(key=lambda x:x[0],reverse=True)
cnt=0
for i in range(len(s)):
    if (st[s[i][1][0]]==-1)and(en[s[i][1][1]]==-1):
        cnt=cnt+s[i][0]
        st[s[i][1][0]]=0
        en[s[i][1][1]]=0
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
aa = list(map(int, input().split()))
ag = list(reversed(np.argsort(aa)))
st = list(reversed(sorted(aa)))
n_min = 0
n_max = n-1
score = 0
for k, v, i in zip(range(len(st)), st, ag):
    if abs(i - n_min) > abs(n_max - i):
        score += v*abs(i - n_min)
        n_min += 1
    elif abs(n_max - i) > abs(i - n_min):
        score += v*abs(n_max - i)
        n_max -= 1
    else:
        if n_min == n_max:
            score += v*abs(n_max - i)
        elif abs(ag[k+1] - n_min) > abs(n_max - ag[k+1]):
            score += v*(n_max - i)
            n_max -= 1
        elif abs(n_max - ag[k+1]) > abs(ag[k+1] - n_min):
            score += v*abs(i - n_min)
            n_min += 1
print(score)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[]
for i,a in enumerate(map(int,input().split())):
  A.append([a,i])
A=sorted(A,key=lambda x:x[0], reverse=True)
r,l=0,N-1
ans=0
i=0
while r<=l:
  _=[A[i]]
  i+=1
  while i<N and A[i][0]==_[0][0]:
    _.append(A[i])
    i+=1
  _=sorted(_,key=lambda x:abs((l+r)//2-x[1]),reverse=True)
  for a,j in _:
    if (l+r)//2<=j:
      ans+=a*(j-r)
      r+=1
    else:
      ans+=a*(l-j)
      l-=1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
used = [False] * N
fixed = [False] * N
ans = 0
for _ in range(N):
    h = (-float('inf'), -1, -1)
    for i in range(N):
        if used[i]:
            continue
        valj = max([(A[i] * (abs(i-j)), j)
                    for j in range(N) if not fixed[j]])
        val, j = valj
        h = (val, i, j) if val > h[0] else h
    val, index, j = h
    ans += val
    used[index] = True
    fixed[j] = True
    # print(val, index, used)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
newA=[]
for i,a in enumerate(A):
    newA.append((a,i))
newA=sorted(newA, key=lambda x:x[1])
newA=sorted(newA, reverse=True)
#print(newA)
l1=1
r1=n-1
l2=0
r2=n-2
ans1=0
ans2=0
for i in range(len(newA)):
    if i==0:
        ans1+=newA[i][0]*abs(newA[i][1])
    else:
        if abs(newA[i][1]-l1)>abs(newA[i][1]-r1):
            ans1+=newA[i][0]*abs(newA[i][1]-l1)
            l1+=1
        else:
            ans1+=newA[i][0]*abs(newA[i][1]-r1)
            r1-=1

for i in range(len(newA)):
    if i==0:
        ans2+=newA[i][0]*abs(newA[i][1]-(n-1))
    else:
        if abs(newA[i][1]-l2)>abs(newA[i][1]-r2):
            ans2+=newA[i][0]*abs(newA[i][1]-l2)
            l2+=1
        else:
            ans2+=newA[i][0]*abs(newA[i][1]-r2)
            r2-=1

print(max(ans1,ans2))

Submission status: Wrong Answer

Solution code:
def maximumIndices(liste):
  maxi = liste[0]
  indice = 0
  longueur=len(liste)
  for i in range(longueur):
    if liste[i] >= maxi:
      maxi = liste[i]
      indice = i
  return indice

N = int(input())
activity = input().split(" ")
for i in range(N):
  activity[i]=int(activity[i])
bornesup = N-1
borneinf = 0
total = 0
while borneinf<bornesup:
  indice = maximumIndices(activity)
  distsup = bornesup-indice
  if indice<=distsup:
    total+=activity[indice]*distsup
    bornesup-=1
  else:
    total+=activity[indice]*indice
    borneinf+=1
  activity[indice]=0
print(total+1)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
L=[]
for i in range(N):
    L.append([A[i],i])

def counter(l):
    c=0
    for i in range(N):
        c+=L[i][0]*abs(L[i][1]-i)
    return c

point=0
for i in range(N):
    for j in range(N)[::-1]:
        
        L[i][0],L[j][0]=L[j][0],L[i][0]
        L[i][1],L[j][1]=L[j][1],L[i][1]
        
        p=counter(L)
        if p>point:
            point=p
        else:
            L[i][0],L[j][0]=L[j][0],L[i][0]
            L[i][1],L[j][1]=L[j][1],L[i][1]

print(point)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
l=[0]
ure=0
s=[]
for i in range(2,N+1):#i人使う
  loc=0
  ure=A[i-1]*(i-1)#ok
  #print()
  for j in range(i-1):#ok
    ure+=A[l[j]]*abs(l[j]-(j+1))#
  print(ure)
  for j in range(i-1):#i+1個の入る場所
    if(ure<=ure-A[i-1]*(j+1)-A[l[j]]*abs(l[j]-(j+1))+A[l[j]]*abs(l[j]-j)):
      loc=j+1
      ure=ure-A[i-1]*(j+1)-A[l[j]]*abs(l[j]-(j+1))+A[l[j]]*abs(l[j]-j)
  ss=l[:]
  l=l[:loc]
  l.append(i-1)
  l.extend(ss[loc:])
  print(l)
  print("owari")
print(ure)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
honke = 0
for border in range(n):
  ans = 0
  L = []
  for i in range(border):
    L.append((A[i],i))
  L.sort(reverse = True)
  for i in range(border):
    ans += (n-i-1-L[i][1])*L[i][0]


  R = []
  for i in range(border,n):
    R.append((A[i],i))
  R.sort(reverse = True)
  for i in range(n-border):
    ans += (R[i][1]-i)*R[i][0]
  honke = max(honke,ans)
print(honke)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
newA=[]
for i,a in enumerate(A):
    newA.append((a,i))
newA=sorted(newA, key=lambda x:x[1])
newA=sorted(newA, reverse=True)
#print(newA)
l1=1
r1=n-1
l2=0
r2=n-2
ans1=0
ans2=0
for i in range(len(newA)):
    if i==0:
        ans1+=newA[i][0]*abs(newA[i][1])
    else:
        if abs(newA[i][1]-l1)>abs(newA[i][1]-r1):
            ans1+=newA[i][0]*abs(newA[i][1]-l1)
            l1+=1
        else:
            ans1+=newA[i][0]*abs(newA[i][1]-r1)
            r1-=1

for i in range(len(newA)):
    if i==0:
        ans2+=newA[i][0]*abs(newA[i][1]-(n-1))
    else:
        if abs(newA[i][1]-l2)>=abs(newA[i][1]-r2):
            ans2+=newA[i][0]*abs(newA[i][1]-l2)
            l2+=1
        else:
            ans2+=newA[i][0]*abs(newA[i][1]-r2)
            r2-=1

print(max(ans1,ans2))

Submission status: Wrong Answer

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

y = [i for i in range(n)]
ans = 0

for i in range(n):
    h = [0, 0]
    x = [0, 0]
    for j in range(n):
        ht = A[j] * abs(j - y[0])
        hl = A[j] * abs(j - y[-1])
        if ht > h[0]:
            h[0] = ht
            x[0] = j
        if hl >= h[1]:
            h[1] = hl
            x[1] = j
    if h[0] >= h[1]:
        ans += h[0]
        A[x[0]] = -1
        y.pop(0)
    else:
        ans += h[1]
        A[x[1]] = -1
        y.pop(-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[i] = v
l = 0
r = n - 1
ans = 0
while len(b) > 0:
    mi = 0
    mv = 0
    mov = 10 ** 9 + 1
    ml = False
    for i, v in b.items():
        if abs(i - l) > abs(i - r):
            tv = v * abs(i - l)
            tl = True
        else:
            tv = v * abs(i - r)
            tl = False
        if tv > mv or (tv == mv and v < mov):
            mi = i
            mv = tv
            ml = tl
            mov = v
    if ml:
        l += 1
    else:
        r -= 1
    ans += mv
    b.pop(mi)
print(ans)

Submission status: Wrong Answer

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

left = 0
right = len(a) - 1
ans = 0

for i in range(n):
    # print(right, left)
    tmp = 0
    num = 0
    l, r = False, False
    for j in range(len(a)):
        if abs(j - right) > abs(j - left):
            if tmp < abs(j - right) * a[j]:
                tmp = abs(j - right) * a[j]
                num = j    
                l, r = False, True

        elif abs(j - right) < abs(j - left):
            if tmp < abs(j - left) * a[j]:
                tmp = abs(j - left) * a[j]
                num = j    
                l, r = True, False

        else:
            if tmp < abs(j - left) * a[j]:
                for k in range(len(a)):
                    tl, tr = False, False
                    te = 0
                    if k != j:
                        if abs(k - right) > abs(j - left):
                            if te < abs(k - right) * a[k]:
                                te = abs(k - right) * a[k]
                                tl, tr = False, True
                        else:
                            if te < abs(k - left) * a[k]:
                                te = abs(k - left) * a[k]
                                tl, tr = True, False
                num = j
                if tl:
                    l, r = False, True
                    tmp += abs(j - right) * a[j]
                else:
                    l, r = True, False
                    tmp += abs(j - left) * a[j]
                
    ans += tmp    
    a[num] = 0
   
    if l:
        left += 1
    if r:
        right -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

S = [[] for _ in range(N)]
for i, a in enumerate(A):
    for j in range(N):
        S[i].append(abs(j-i)*a)

left = 0
right = N - 1
is_used = [False] * N
ans = 0
for i in range(N):
    temp = []
    for j in range(N):
        if is_used[j]:
            continue
        heapq.heappush(temp, [-S[j][left], 'l', j])
        heapq.heappush(temp, [-S[j][right], 'r', j])
    
    s, pos, j = heapq.heappop(temp)
    ans -= s
    is_used[j] = True
    if pos == 'l':
        left += 1
        if left > right:
            left = right
    else:
        right -= 1
        if right < left:
            right = left

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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


r_max = 0

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

test(0,0,N,1)

print(r_max)

Submission status: Wrong Answer

Solution code:
import math  # noqa
import bisect  # noqa
import queue  # noqa


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    MAX = N - 1
    MIN = 0
    used = set()

    ans = 0
    while len(used) < N:
        best = 0
        best_idx = -1
        for i, a in enumerate(A):
            diff = max(abs(i - MIN), abs(MAX - i))
            if (best < diff * a) and (i not in used):
                best = diff * a
                best_idx = i
        ans += best
        used.add(best_idx)
        if abs(best_idx - MIN) < abs(MAX - best_idx):
            MAX -= 1
        else:
            MIN += 1

    print(ans)