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:
N = int(input())
A = list(map(int,input().split()))
out = 0
l = 0
r = N-1
while True:
    maxP1 = 0
    for i in range(N):
        P = A[i]*abs(l-i)
        if P > maxP1:
            maxA1 = A[i]
            maxP1 = P
            maxi1 = i
        if (P!=0)and(P == maxP1):
            if A[i]>maxA1:
                maxA1 = A[i]
                maxP1 = P
                maxi1 = i
    maxP2 = 0
    for i in range(N):
        P = A[i]*abs(r-i)
        if P > maxP2:
            maxA2 = A[i]
            maxP2 = P
            maxi2 = i
        if (P!=0)and(P == maxP2):
            if A[i]>maxA2:
                maxA2 = A[i]
                maxP2 = P
                maxi2 = i
    if maxP1 > maxP2:
        l+=1
        out += maxP1
        A[maxi1] = 0
    elif maxP1 < maxP2:
        r+=-1
        out += maxP2
        A[maxi2] = 0
    elif maxP1 == maxP2:
        if maxA1>maxA2:
            l+=1
            out += maxP1
            A[maxi1] = 0
        else:
            r+=-1
            out += maxP2
            A[maxi2] = 0
    if l==r:
        break

maxP=0
for i in range(N):
    P = A[i]*abs(r-i)
    if P >= maxP:
        maxP3 = P
        maxi3 = i
A[maxi3] = 0
out += maxP

print(out)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from heapq import heappush, heappop
class MinCostFlow:
    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost):
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr])-1])

    def flow(self, s, t, f):
        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0]*N
        prv_v = [0]*N
        prv_e = [0]*N

        while f:
            dist = [INF]*N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w]:
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        prv_v[w] = v; prv_e[w] = i
                        heappush(que, (r, w))
            if dist[t] == INF:
                return -1

            for i in range(N):
                H[i] += dist[i]

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

def solve(N: int, A: "List[int]"):
    flow = MinCostFlow(2*N+2)

    for i in range(N):
        for j in range(N):
            if i == j: continue
            flow.add_edge(i,j+N,1,-A[i]*abs(i-j))
    
    for j in range(N):
        flow.add_edge(2*N,j,1,0)
        flow.add_edge(j+N,2*N+1,1,0)

    print(-flow.flow(2*N,2*N+1,N))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

num1 = A.count(1)
l = []
for a in reversed(sorted(A)):
    idx = A.index(a)
    A[idx] = -1
    l.append((a,idx))

head, tail = 0, N-1

ans = 0
for tup in l:
    v = tup[0]
    idx = tup[1]

    if abs(idx - head) >= abs(idx - tail):
        ans += v * abs(idx-head)
        head += 1
    else:
        ans += v * abs(idx-tail)
        tail -= 1

if num1 > 1:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

A = [0]+A
DP = [[0]*N for i in range(N+1)]
DPPath = [[[0]*N]*N for i in range(N+1)]

for i in range(1,N+1):
    Ax,x = A[i],i-1
    for y in range(N):
        for b in range(N):
            Path = DPPath[i-1][b][::]
            if Path[y]:continue
            Path[y] = 1
            if DP[i][y] < DP[i-1][b]+Ax*abs(x-y):
                DP[i][y]=DP[i-1][b]+Ax*abs(x-y)
                DPPath[i][y]=Path

print(max(DP[N]))

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))


def f(v):
    sorted_v = sorted(v)
    c = Counter(v)
    happy = 0
    for key in c.keys():
        v_idx = [n for n, i in enumerate(v) if i == key]
        sorted_v_idx = [n for n, i in enumerate(sorted_v) if i == key]
        move_idx = 0
        for i, j in zip(v_idx, sorted_v_idx):
            move_idx += j - i
        move_idx += (N - len(v)) * len(v_idx)
        happy += move_idx * key
    return happy


ans = 0
for i in range(N // 2 - 1, N // 2 + 1):
    l = A[:i]
    r = A[i:][::-1]
    # print('l, r', l, r, f(l), f(r))
    ans = max(ans, f(l) + f(r))
print(ans)

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,0]
    max_u2 = [0,0]
    max_i = [-1,-1]
    max_i2 = [-1,-1]
    for i in range(N):
        u0 = abs(top-i) * A[i]
        u1 = abs(bot-i) * A[i]

        if u0 > max_u[0] or u0 == max_u[0] and A[i] > A[max_i[0]]:
            max_u2[0] = max_u[0]
            max_i2[0] = max_i[0]
            max_u[0] = u0
            max_i[0] = i
        else:
            if u0 > max_u2[0] or u0 == max_u2[0] and A[i] > A[max_i2[0]]:
                max_u2[0] = u0
                max_i2[0] = i

        if u1 > max_u[1]  or u1 == max_u[1] and A[i] > A[max_i[1]]:
            max_u2[1] = max_u[1]
            max_i2[1] = max_i[1]
            max_u[1] = u1
            max_i[1] = i
        else:
            if u1 > max_u2[1]  or u1 == max_u2[1] and A[i] > A[max_i2[1]]:
                max_u2[1] = u1
                max_i2[1] = i

    up_i = 0
    max_tb = 0
    if max_u[0] > max_u[1]:
        ure += max_u[0]
        up_i = max_i[0]
    elif max_u[1] > max_u[0]:
        ure += max_u[1]
        up_i = max_i[1]
        max_tb = 1
    else:
        if max_u2[0] > max_u2[1]:
            ure += max_u2[0]
            up_i = max_i2[0]
        elif max_u2[1] > max_u2[0]:
            ure += max_u2[1]
            up_i = max_i2[1]
            max_tb = 1
        else:
            ure += max_u[0]
            up_i = max_i[0]

    A[up_i] = 0
    if max_tb == 0:
        top += 1
    else:
        bot -= 1
print (ure)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
check = [0]*n
flag1 = 0
flag2 = n-1
while check != [1]*n:
    if abs(a.index(max(a))-flag1) > abs(a.index(max(a))-flag2):
        ans += max(a)*abs(a.index(max(a))-flag1)
        a[a.index(max(a))] = 0
        check[flag1]=1
        flag1 += 1
    if abs(a.index(max(a))-flag1) <= abs(a.index(max(a))-flag2):
        ans += max(a)*abs(a.index(max(a))-flag2)
        a[a.index(max(a))] = 0
        check[flag2]=1
        flag2 -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())

ls = []
for i in range(n):
    ls.append( [i,a[i]] )
# print(ls)

ls = mysort(ls,1)
# print(ls)

pos = list(range(n))

h = 0
for i in range(n):
    x,A = ls.pop()
    l = min(pos)
    r = max(pos)
    c = abs(l-x) - abs(r-x)
    if c>=0:
        h += A*abs(l-x)
        pos.remove(l)
    else:
        h += A*abs(r-x)
        pos.remove(r)

print(h)

Submission status: Wrong Answer

Solution code:
#mod = 10**9 + 7
import heapq
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n = inp()
nums = inlt()
nums = [[nums[i],i] for i in range(n)]
ans = 0
left = 0
right = n - 1
while left < right:
    the_max = 0
    ri = left
    for i in range(left,right + 1):
        val,index = nums[i]
        if abs(right - index)*val > the_max:
            the_max = abs(right - index)*val
            ri = i
    the_m = 0
    for i in range(right,left - 1,-1):
        val,index = nums[i]
        if abs(index - left)*val > the_m:
            the_m = abs(index - left)*val
            li = i
    if the_max > the_m:
        nums[ri][0] = nums[right][0]
        nums[ri][1] = nums[right][1]
        right -= 1
        ans += the_max
    else:
        nums[li][0] = nums[left][0]
        nums[li][1] = nums[left][1]
        left += 1
        ans += the_m
    #print(ans)
val,i= nums[left]
print(ans + abs(left - i)*val)  
#print(n - s if s <= n else -1)
#print('No')
#print()

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
pos=[i for i in range(n)]
for _ in range(20):
  for i in range(n):
    for j in range(n):
      if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
        pos[i],pos[j]=pos[j],pos[i]
ans=0
for i in range(n):
  ans+=arr[i]*abs(i-pos[i])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ans = 0
det = np.ones((n))

if n % 2 == 0:
    p = []
    for i in range(int(n/2)):
        p.append(n-1 - i)
    for i in range(int(n/2)):
        p.append(int(n/2) + i)
else:
    p = [abs(i-int(n/2)) + int(n/2) for i in range(n)]
    
for i in range(n):
    ans += max(a * p)
    hoge = np.argmax(a * p)
    det[hoge] *= 0
    p *= det
    
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
from collections import deque

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

values = []
num_indcies = {}
for i, a in enumerate(A):
    if not a in num_indcies:
        num_indcies[a] = [i]
        values.append(a)
    else:
        num_indcies[a].append(i)

values = sorted(values, reverse=True)
ans = 0
L = 0
R = N-1

ans = 0
for i, val in enumerate(values):
    indices = deque(num_indcies[val])
    #print(i, val, ans, L , R)
    while len(indices) > 1:
        if abs(R - indices[0]) < abs(indices[-1] - L):
            ans += val *  abs(indices[-1]-L)
            indices.pop()
            L += 1
        else:
            ans += val *  abs(R-indices[0])
            indices.popleft()
            R -= 1
        #print("indices", indices)
        #print("内部", i, val, ans, L , R)
    if abs(R - indices[0]) < abs(indices[-1] - L):
        ans += val *  abs(indices[-1]-L)
        indices.pop()
        L += 1
    elif abs(R - indices[0]) > abs(indices[-1] - L):
        ans += val *  abs(R-indices[0])
        indices.popleft()
        R -= 1
    else:
        ans += val *  abs(indices[-1]-L)
        if i == len(values) -1:
            continue
        _indices = deque(num_indcies[values[i+1]])
        if abs(R - _indices[0]) < abs(_indices[-1] - L):
            L += 1
        else:
            R -= 1

print(ans)

Submission status: Wrong Answer

Solution code:

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]

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

left = [0]
right = [0]
ans = 0
for i in range(N):
    l, r = 0, 0
    for j in range(len(left)):
        if A[i] > left[j]:
            buff = i - len(left) + 1 if left[j] == 0 else 1
            l += (A[i] - left[j]) * buff
        else:
            break
    for j in range(len(right)):
        if A[i] > right[j]:
            buff = N-i-1 - len(right) + 1 if right[j] == 0 else 1
            r += (A[i] - right[j]) * buff
        else:
            break
    if r > l:
        right.append(A[i])
        right.sort()
        ans += r
    else:
        left.append(A[i])
        left.sort()
        ans += l
#    print(i,A[i],l,r,ans)
#print(ans)
ans1 = ans

A.reverse()

left = [0]
right = [0]
ans = 0
for i in range(N):
    l, r = 0, 0
    for j in range(len(left)):
        if A[i] > left[j]:
            buff = i - len(left) + 1 if left[j] == 0 else 1
            l += (A[i] - left[j]) * buff
        else:
            break
    for j in range(len(right)):
        if A[i] > right[j]:
            buff = N-i-1 - len(right) + 1 if right[j] == 0 else 1
            r += (A[i] - right[j]) * buff
        else:
            break
    if r > l:
        right.append(A[i])
        right.sort()
        ans += r
    else:
        left.append(A[i])
        left.sort()
        ans += l
#    print(i,A[i],l,r,ans)
print(max(ans, ans1))

Submission status: Wrong Answer

Solution code:
import numpy as np
if __name__ == "__main__":
    # 入力パターン．
    # 先に要素数Nが与えられて，その数読み込むパターン
    ### N
    ### a_1 a_2 a_3 ... a_N
    N = int(input())
    # int型のリスト
    line = list(map(int, input().rstrip().split(' ')))

    arr = [[line[i]*np.abs(i-j) for j in range(N)] for i in range(N)]
    arr = np.array(arr)
    cost = arr + arr.T
    #print(arr)
    #print(cost)
    ans = 0
    unused = np.array([True for i in range(N)])
    for i in range(N):
        c = cost[i]
        if unused.sum() > 0:
            add = c[unused].max()
            used = c == add
            used = unused * used
            used_idx = used.argmax()
            #print(used)
            unused[i] = False
            unused[used_idx] = False
            ans += add
            #print(c)
            #print(add)
            #print(unused)
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())

A_list = np.array(list(map(int, input().split())))
arg_list = np.argsort(-A_list)

r_fill = 0
l_fill = 0

max_all = 0
for i in range(N):
    max_value = 0
    max_idx = 0
    tmp_l_fill = 0
    tmp_r_fill = 0
    for idx, j in enumerate(arg_list):
        tmp_max = A_list[j] * max(j-l_fill, N-j-1-r_fill)

        if tmp_max > max_value:
            max_idx = idx
            max_value = tmp_max
            if j-l_fill > N-j-1-r_fill:
                tmp_l_fill = 1
                tmp_r_fill = 0
            else:
                tmp_r_fill = 1
                tmp_l_fill = 0

    r_fill += tmp_r_fill
    l_fill += tmp_l_fill

    max_all += max_value

    print(arg_list, max_value)

    arg_list = np.concatenate([arg_list[:max_idx], arg_list[max_idx+1:]])
    
print(max_all)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
flag = [1 for i in range(N)]
left = 0
right = N - 1
ans = 0
for i in range(N):
    index = 0
    MAX = 0
    for j in range(N):
        if flag[j] and MAX < A[j]:
            MAX = A[j]
            index = j
    if sum(A[:index]) < sum(A[index+1:]):
        ans += A[index] * abs(right - index)
        right -= 1
    elif sum(A[:index]) > sum(A[index+1:]):
        ans += A[index] * abs(left - index)
        left += 1
    elif abs(left - index) < abs(right - index):
        ans += A[index] * abs(right - index)
        right -= 1
    else:
        ans += A[index] * abs(left - index)
        left += 1
    A[index] = 0
    flag[index] = 0
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)


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 = a * abs(i - l)
    right = a * abs(r - i)
    for j in range(N):
        b = A[j]
        if a < b or (a == b and j < i):
            continue

        to_l = j - l
        to_r = r - j

        if to_l == to_r:
            left -= b
            right -= b
        elif to_l < to_r:
            right -= b
        elif to_r < to_l:
            left -= b

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


print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
import numpy as np


def read():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A


def rmq_init(n, INF=2**16+1):
    n0 = 2**(n-1).bit_length()
    rmq = [INF] * (2 * n0)
    return rmq


def rmq_update(rmq, k, x):
    n0 = len(rmq) // 2
    k += n0 - 1
    rmq[k] = x
    while k >= 0:
        k = (k-1) // 2
        if rmq[2*k+1] < rmq[2*k+2]:
            rmq[k] = rmq[2*k+1]
        else:
            rmq[k] = rmq[2*k+2]

def rmq_query(rmq, l, r, INF=2**16+1):
    n0 = len(rmq) // 2
    L = l + n0
    R = r + n0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, rmq[R-1])
        if L & 1:
            s = min(s, rmq[L-1])
            L += 1
        L >>= 1
        R >>= 1
    return s


def solve(N, A, INF=2**16+1):
    S = np.empty((N, N), dtype=np.int)
    rmqs = list()
    for i in range(N):
        rmq = rmq_init(N)
        for j in range(N):
            S[i][j] = A[i] * abs(i - j)
            rmq_update(rmq, j, -S[i][j])
        rmqs.append(rmq)
    ans = 0
    skip = [False for i in range(N)]
    for k in range(N):
        max_v = 0
        max_idx = -1
        for i in range(N):
            if not skip[i]:
                v = -rmq_query(rmqs[i], 0, N)
                if max_v < v:
                    max_v = v
                    max_idx = i
        ans += max_v
        for i in range(N):
            rmq_update(rmqs[i], max_idx, INF)
        skip[max_idx] = True
    return ans

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

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

sort_a = sorted(A, reverse = True)
L  = 0
R = N-1
ans = 0
for i in range(N):
    n = sort_a[i]
    inde = A.index(n)
    A[inde] = -1
    if inde - L > R - inde:
        ans +=(inde - L) * n
        L +=  1
    else:
        ans += (R - inde) * n
        R -= 1
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 =[""]*N
    upIndex = N-1
    downIndex = 0
    def checkNext(i):
        maxScore = -1
        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]
        return (maxScore,maxScoreIndex)
    while upIndex >= downIndex:
        fromDown,di = checkNext(downIndex)
        fromUp,ui = checkNext(upIndex)
        useFromDown = fromDown > fromUp
        if fromDown == fromUp and upIndex != downIndex:
            moved[di] = True
            downIndex+=1
            ifdownUsed,ni = checkNext(downIndex)
            moved[di] = False
            moved[ui] = True
            downIndex-=1
            upIndex -= 1
            ifUpUsed,ni = checkNext(upIndex)
            moved[ui] = False
            upIndex+=1
            if ifdownUsed < ifUpUsed:
                useFromDown = True
        if useFromDown:
            result+= fromDown
            actual[downIndex] = A[di]
            moved[di] = True
            # print(f"Down{downIndex}:{di} - {A[di]}")
            # print(moved)
            # print(f"down:{downIndex},up:{upIndex}")
            downIndex+=1
        else:
            result+=fromUp
            actual[upIndex] = A[ui]
            moved[ui] = True
            # print(f"Up{upIndex}:{ui} - {A[ui]}")
            # print(moved)
            # print(f"down:{downIndex},up:{upIndex}")
            upIndex-=1
    # 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 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:
        diff = []
        for i, a in enumerate(A):
            res = max(abs(i - MIN), abs(MAX - i))
            if i not in used:
                diff.append([res * a, i])
        diff.sort(reverse=True)
        ans += diff[0][0]
        used.add(diff[0][1])
        idx = 0
        while abs(diff[idx][1] - MIN) == abs(MAX - diff[idx][1]):
            idx += 1
            if idx == len(diff):
                idx -= 1
                break
        if abs(diff[idx][1] - MIN) < abs(MAX - diff[idx][1]):
            MAX -= 1
        else:
            MIN += 1

    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
N=int(input())
A=list(map(int,input().split()))
A=[[A[i],i] for i in range(N)]
A.sort(key=lambda x:x[0]*3000+round(abs(x[1]-(N//2))) )
c=0
for i in range(N//2):
    a1,i1=A.pop()
    a2,i2=A.pop()
    b=(N-1-i)
    c+=max(a1*round(abs(i-i1))+a2*round(abs(b-i2)),a1*round(abs(b-i1))+a2*round(abs(i-i2)))
if N%2:
    a1,i1=A.pop()
    b=(N-1)//2
    c+=a1*round(abs(b-i1))
print(c)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
pos=[i for i in range(n)]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
for i in range(n):
  for j in range(n):
    if arr[i]*abs(pos[j]-i)+arr[j]*abs(pos[i]-j)>arr[i]*abs(i-pos[i])+arr[j]*abs(j-pos[j]):
      pos[i],pos[j]=pos[j],pos[i]
ans=0
for i in range(n):
  ans+=arr[i]*abs(i-pos[i])
print(ans)

Submission status: Wrong Answer

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

ans = 0
minN = 0
maxN = N-1
flag = [1]*N
    
for i in range(N):
    maxpr = 0
    maxj = 0
    flagj = 0
    for j in range(N):
        if flag[j]:
            if maxN - j >= j - minN and A[j]*(maxN - j) > maxpr:
                maxpr = A[j]*(maxN - i)
                maxj = j
                flagj = 1
            elif  maxN - j <= j - minN and A[j]*(j - minN) > maxpr:
                maxpr = A[j]*(j - minN)
                maxj = j
                flagj = 0
    
    flag[maxj] = 0
    if flagj:
        maxN -= 1
    else:
        minN += 1
    ans += maxpr
    
print(ans)

Submission status: Wrong Answer

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

N = int(readline())
A = list(map(int, readline().rstrip().split()))
B = [-1] * N

def find_best():
    ma_sel = -1
    for i, a in enumerate(A):
        if a == -1:
            continue
        ma = -1
        for j in range(N):
            if B[j] != -1:
                continue
            get = a * abs(j-i)
            if get > ma:
                ma = get
                idx = j
        if ma > ma_sel:
            ma_sel = ma
            idx_from = i
            idx_to = idx

    return idx_from, idx_to, ma_sel

def main():
    global A, B
    for _ in range(N):
        idx_from, idx_to, ma_sel = find_best()
        A[idx_from] = -1
        B[idx_to] = ma_sel

    print(sum(B))


if __name__ == '__main__':
    main()

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)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [a for a in enumerate(list(map(int, input().split())))]
A.sort(key=lambda x: x[1], reverse=True)
ans = 0
start = 0
end = N - 1
for i in range(N):
    d_start = abs(A[i][0] - start)
    d_end = abs(A[i][0] - end)
    if d_start > d_end:
        ans += A[i][1] * d_start
        start += 1
    elif d_start < d_end:
        ans += A[i][1] * d_end
        end -= 1
    else:
        ans += A[i][1] * d_end
        if not i < N - 1:
            continue
        _d_start = abs(A[i + 1][0] - start)
        _d_end = abs(A[i + 1][0] - end)
        if _d_start > _d_end:
            end -= 1
        else:
            start += 1
print(ans + 1)

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,0]
    max_u2 = [0,0]
    max_i = [-1,-1]
    max_i2 = [-1,-1]
    for i in range(N):
        u0 = abs(top-i) * A[i]
        u1 = abs(bot-i) * A[i]

        if u0 > max_u[0] or u0 == max_u[0] and A[i] > A[max_i[0]]:
            max_u2[0] = max_u[0]
            max_i2[0] = max_i[0]
            max_u[0] = u0
            max_i[0] = i
        else:
            if u0 > max_u2[0] or u0 == max_u2[0] and A[i] > A[max_i2[0]]:
                max_u2[0] = u0
                max_i2[0] = i

        if u1 > max_u[1]  or u1 == max_u[1] and A[i] > A[max_i[1]]:
            max_u2[1] = max_u[1]
            max_i2[1] = max_i[1]
            max_u[1] = u1
            max_i[1] = i
        else:
            if u1 > max_u2[1]  or u0 == max_u2[1] and A[i] > A[max_i2[1]]:
                max_u2[1] = u1
                max_i2[1] = i

    up_i = 0
    max_tb = 0
    if max_u[0] > max_u[1]:
        ure += max_u[0]
        up_i = max_i[0]
    elif max_u[1] > max_u[0]:
        ure += max_u[1]
        up_i = max_i[1]
        max_tb = 1
    else:
        if max_u2[0] > max_u2[1]:
            ure += max_u2[0]
            up_i = max_i2[0]
        elif max_u2[1] > max_u2[0]:
            ure += max_u2[1]
            up_i = max_i2[1]
            max_tb = 1
        else:
            ure += max_u[0]
            up_i = max_i[0]

    A[up_i] = 0
    if max_tb == 0:
        top += 1
    else:
        bot -= 1
print (ure)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(c) for c in input().split()]
li = 0
ri = n-1
out = 0
tmp = [0] * n
tmp2 = [0]
diff = [0] * n
tmp[0] = a[0]
tmp2[0] = a[0]
for i in range(1, n):
    item = a[i]
    best_ind = 0
    best_val = -1
    for j in range(i+1):
        val = item * (i - j) + tmp[j]
        if val > best_val:
            best_val = val
            best_ind = j
    prev = diff[best_ind]
    diff[best_ind] = (best_ind - i)
    tmp2.insert(best_ind, item)
    out += best_val
    for ii in range(best_ind+1, i+1):
        prev2 = diff[ii]
        diff[ii] = prev+1
        prev = prev2
    vv = 0
    for ii in range(i, -1, -1):
        sign = 1 if diff[ii]>=0 else -1
        vv += (tmp2[ii] * sign)
        tmp[ii] = vv
print(out)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
dc = dict()
for i in range(n):
  for j in range(n):
    pt = A[i] * abs(i-j)
    if dc.get(pt) == None:
      dc[pt] = [(i,j)]
    else:
      dc[pt].append((i,j))
desc = sorted(dc.items(), key=lambda x: x[0], reverse=True)
import numpy as np
ans = 0
table = np.zeros((n,n))
for pt, xyarr in desc:
  for x,y in xyarr:
    if table[x,y] == 0:
      ans += pt
      table[x,:] = 1
      table[:,y] = 1
print(ans)