Problem:


Score : 500 points

Problem Statement

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

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

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

Find the maximum total happiness points the children can earn.

Constraints

2 \leq N \leq 2000

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum total happiness points the children can earn.

Sample Input 1

4
1 3 4 2

Sample Output 1

20

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

Sample Input 2

6
5 5 6 1 1 1

Sample Output 2

58

Sample Input 3

6
8 6 9 1 2 1

Sample Output 3

85



Sample input:
4
1 3 4 2


Sample output:
20

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys
sys.setrecursionlimit(10**5)

def f(x, po, h, t, ple):
    if po=='h':
        ple+=B[x][1]*abs(B[x][0]-h)
        h+=1
    else:
        ple+=B[x][1]*abs(B[x][0]-t)
        t-=1
    if x==N-1:
        return ple
    
    if abs(B[x+1][0]-h)==abs(B[x+1][0]-t):
        return max(f(x+1, 'h', h, t, ple), f(x+1, 't', h, t, ple))
    elif abs(B[x+1][0]-h)>abs(B[x+1][0]-t):
        return f(x+1, 'h', h, t, ple)
    else:
        return f(x+1, 't', h, t, ple)

N=int(input())
A=list(map(int, input().split()))
B=[[i, A[i]] for i in range(N)]
B=sorted(B, key=itemgetter(1), reverse=True)
h=0
t=N-1

if abs(h-B[0][0])==abs(t-B[0][0]):
    ans=max(f(0, 'h', h, t, 0), f(0, 't', h, t, 0))
elif abs(h-B[0][0])>abs(t-B[0][0]):
    ans=f(0, 'h', h, t, 0)
else:
    ans=f(0, 't', h, t, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

B = [-1]*N
sum = 0
for i in range(N):
    C = [0]*N
    
    bf = B.index(-1)
    bb = (N-1) - B[::-1].index(-1)
    
    for j in range(N):
        C[j] = A[j] * max(abs(j-bf), abs(j-bb))

    k = C.index(max(C))
    sum += max(C)
    
    if abs(k-bf) > abs(k-bb):
        B[bf] = k
    else:
        B[bb] = k

    A[k] = 0

print(sum)

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
flag = 0
i = 0
b_iti = -1
b_score = -1
while(i < n):
    i += 1
    mae_max_score = -1
    usi_max_score = -1
    mae_iti = -1
    usi_iti = -1
    for j in range(0, n):
        if mae_max_score < a_list[j] * abs(j - start):
            mae_max_score = a_list[j] * abs(j - start)
            mae_iti = j
        if usi_max_score < a_list[j] * abs(end - j):
            usi_max_score = a_list[j] * abs(end - j)
            usi_iti = j
    if flag == 0:
        if mae_max_score > usi_max_score:
            a_list[mae_iti] = 0
            ans += mae_max_score
            start += 1
        elif mae_max_score < usi_max_score:
            a_list[usi_iti] = 0
            ans += usi_max_score
            end -= 1
        else:
            if mae_iti != usi_iti:
                a_list[mae_iti] = 0
                ans += mae_max_score
                start += 1
                a_list[usi_iti] = 0
                ans += usi_max_score
                end -= 1
                i += 1
            elif start == end:
                a_list[mae_iti] = 0
                ans += mae_max_score
            else:
                a_list[mae_iti] = 0
                b_score = mae_max_score
                flag = 1
    else:
        flag = 0
        if mae_max_score > usi_max_score:
            a_list[mae_iti] = 0
            ans += mae_max_score
            start += 1
            ans += b_score
            end -= 1
        elif mae_max_score <= usi_max_score:
            a_list[usi_iti] = 0
            ans += usi_max_score
            end -= 1
            ans += b_score
            start += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

lis = []

for i in range(n):
  p = [a * abs(i - itr) for itr, a in enumerate(A)]
  lis.append(p)

selected = [False] * n

# print(lis)

ans = 0
for i in range(n // 2):
  u = np.array([-1 if selected[itr] else v for itr, v in enumerate(lis[i])])
  d = np.array([-1 if selected[itr] else v for itr, v in enumerate(lis[-(i+1)])])
  # print(u, d)
  ua = u.argsort()
  da = d.argsort()
  # print(ua, da)
  ufirst, usecond = ua[-1], ua[-2]
  dfirst, dsecond = da[-1], da[-2]

  if ufirst != dfirst:
    selected[ufirst] = True
    selected[dfirst] = True
    ans += u[ufirst]
    ans += d[dfirst]
  else:
    if u[usecond] > d[dsecond]:
      ans += u[usecond]
      ans += d[dfirst]
    else:
      ans += u[ufirst]
      ans += d[dsecond]

if n % 2 == 1:
  idx = selected.index(False)
  ans += lis[n//2][idx]

print(ans)
# print(ans)

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)
ans = 0
cnt = 0
x_used = [0]*n
y_used = [0]*n
for pt, xyarr in desc:
  for x,y in xyarr:
    if x_used[x] == 0 and y_used[y] == 0:
      ans += pt
      cnt += 1
      x_used[x] = 1
      y_used[y] = 1
      if cnt >= n: break
  if cnt >= n: break
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = sorted(A, reverse=True)
x = 0
S = []
for i in range(n):
  S.append(i+1)

  T = []
for i in range(n):
  for j in range(n):
    if B[i]==A[j]:
      T.append(j+1)
      A[j] = 0

for i in range(n-1):
  a = S[0]
  b = S[-1]
  if T[i] > (a+b)/2:
    x += B[i]*(T[i]-a)
    S.remove(a)
  elif T[i] < (a+b)/2:
    x += B[i]*(b-T[i])
    S.remove(b)
  else:
    if T[i+1] > T[i]:
      x += B[i]*(b-T[i])
      S.remove(b)
    else:
      x += B[i]*(T[i]-a)
      S.remove(a)
y = x + B[-1]*abs(S[0]-T[-1])
print(y)

Submission status: Wrong Answer

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

def solve():
    happy = [[0]*N for _ in range(N)]
    pref = [[] for _ in range(N)]
    for i, a in enumerate(A):
        for j in range(N):
            h = abs(j - i) * a
            happy[i][j] = h
            pref[i].append((h,j))
        pref[i].sort(reverse=True)
    det = set()
    res = {}
    for i in range(N):
        hbest = -1
        arg = None
        for j in range(N):
            if j in det:
                continue
            for h, pos in pref[j]:
                if pos in res:
                    continue
                if hbest < h:
                    hbest = h
                    arg = (j,pos)
        baby, pos = arg
        res[pos] = hbest
        det.add(baby)
    assert len(det) == N
    return sum(res.values())

print(solve())

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:
        res = []
        for i, a in enumerate(A):
            diff = max(abs(i - MIN), abs(MAX - i))
            if i not in used:
                res.append([diff * a, i])
        res.sort(reverse=True)
        ans += res[0][0]
        used.add(res[0][1])
        idx = 0
        while abs(res[idx][1] - MIN) == abs(MAX - res[idx][1]):
            idx += 1
            if idx == len(res):
                idx -= 1
                break
        if idx == 0:
            if abs(res[idx][1] - MIN) < abs(MAX - res[idx][1]):
                MAX -= 1
            else:
                MIN += 1
        else:
            if abs(res[idx][1] - MIN) < abs(MAX - res[idx][1]):
                MIN += 1
            else:
                MAX -= 1

    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = [[0,0]]
t = [0]
p = 0
m = max(a)
z = [0,n-1]
for i in range(n):
    p += a[i]
    l.append([p,0])
    if(t[-1] < a[i]):
        t.append(a[i])
    else:
        for j in range(len(t)):
            if(t[j] >= a[i]):
                if(t[j] > a[i]):
                    t.insert(j,a[i])
                break
for i in range(n):
    l[i][1] = p-l[i+1][0]
p = 0
for i in range(1,len(t)):
    temp = [x for x, val in enumerate(a) if val == t[-i]]
    for j in range(len(temp)):
        q = l[temp[j]] 
        if(q[0] > q[1]):
            for k in range(temp[j]):
                l[k][0] -= a[temp[j]]
            p += abs(temp[j]-z[0])*a[temp[j]]
            z[0] += 1
        else:
            for k in range(temp[j]+1,n):
                l[k][1] -= a[temp[j]]
            p += abs(temp[j]-z[1])*a[temp[j]]
            z[1] -= 1
print(p)

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)
    rmq_idx = [INF] * (2 * n0)
    return rmq, rmq_idx


def rmq_update(rmq, rmq_idx, k, x):
    n0 = len(rmq) // 2
    k += n0 - 1
    rmq[k] = x
    rmq_idx[k] = k-(n0-1)
    while k >= 0:
        k = (k-1) // 2
        if rmq[2*k+1] < rmq[2*k+2]:
            rmq[k] = rmq[2*k+1]
            rmq_idx[k] = rmq_idx[2*k+1]
        else:
            rmq[k] = rmq[2*k+2]
            rmq_idx[k] = rmq_idx[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 rmq_query_idx(rmq, rmq_idx, l, r, INF=2**16+1):
    n0 = len(rmq) // 2
    L = l + n0
    R = r + n0
    s = INF
    s_idx = -1
    while L < R:
        if R & 1:
            R -= 1
            if rmq[R-1] < s:
                s = rmq[R-1]
                s_idx = rmq_idx[R-1]
        if L & 1:
            if rmq[L-1] < s:
                s = rmq[L-1]
                s_idx = rmq_idx[L-1]
            L += 1
        L >>= 1
        R >>= 1
    return s_idx


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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

C = np.zeros([N, N], dtype=np.int32)

C[0] = np.arange(N)

for i in range(1, N):
    C[i] = C[i - 1] + 1
    C[i] -= 2

for i in range(N):
    C[i] *= A[i]
C = np.abs(C)

left = 0
right = N - 1

cnt = 0
while left < right:
    a = np.argmax(C[:, left])
    b = np.argmax(C[:, right])

    if C[a, left] > C[b, right]:
        cnt += C[a, left]
        C[a] = 0
        C[:, left] = 0
        left += 1
    elif C[a, left] < C[b, right]:
        cnt += C[b, right]
        C[b] = 0
        C[:, right] = 0
        right -= 1
    elif C[a, left] == C[b, right]:
        if A[a] > A[b]:
            cnt += C[b, right]
            C[b] = 0
            C[:, right] = 0
            right -= 1
        else:
            cnt += C[a, left]
            C[a] = 0
            C[:, left] = 0
            left += 1
            

cnt += np.max(C)

print(cnt)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
#show_flg=True

ans=0


n=I()
A=LI()
a=list(enumerate(A))
a.sort(key=lambda x:x[1])
show('a',a)

b=[[]for i in range(n)]
for i in range(n):
    for j in range(n):
        b[i].append(abs(i-j)*A[i])

for j in b:
    show('b',j)

l,r=0,n-1
rng=list(range(n))
skp=set()
for i in range(n):
    mx_l,mx_r=-1,-1
    for j in range(n):
        if j in skp:continue
        if b[j][l]>mx_l:
            mx_l=b[j][l]
            l_can=[(j,b[j][r])]
        elif b[j][l]==mx_l:
            l_can.append((j,b[j][r]))

        if b[j][r]>mx_r:
            mx_r=b[j][r]
            r_can=[(j,b[j][l])]
        elif b[j][r]==mx_r:
            r_can.append((j,b[j][l]))
    
    r_can.sort(key=lambda x:x[1])
    l_can.sort(key=lambda x:x[1])
    
    r_skp=r_can[0][0]
    l_skp=l_can[0][0]
    
    show('mx_l,mx_r',mx_l,mx_r,l_skp,r_skp,l_can,r_can)
    if mx_r>mx_l:
        ans+=b[r_skp][r]
        r-=1
        skp.add(r_skp)
        show('r')
    elif mx_r<mx_l:
        ans+=b[l_skp][l]
        l+=1
        skp.add(l_skp)
        show('l')
    else:
        if r_can[0][1]<l_can[0][1]:
            ans+=b[r_skp][r]
            r-=1
            skp.add(r_skp)
            show('r')
        else:
            ans+=b[l_skp][l]
            l+=1
            skp.add(l_skp)
            show('l')
        
        
        show('=')
    show(skp,(l,r),ans)

print(ans)

Submission status: Wrong Answer

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
done = [False]*n
ans = [-1]*n
l = 0
r = n-1
sm = 0
ldif = [a[i]*i for i in range(n)]
rdif = [a[i]*(n-1-i) for i in range(n)]
lmx = rmx = 0
for i in range(n):
    if ldif[i]>lmx:
        lmx = ldif[i]
        lmxi = i
    if rdif[i]>rmx:
        rmx = rdif[i]
        rmxi = i
while l<=r:
    ddprint(done)
    if lmx>rmx:
        ans[l] = lmxi
        ddprint(f"ans l {l} set to {lmxi}")
        done[lmxi] = True
        l += 1
        sm += lmx
        for i in range(n):
            ldif[i] -= a[i]
    else:
        ans[r] = rmxi
        ddprint(f"ans r {r} set to {rmxi}")
        done[rmxi] = True
        r -= 1
        sm += rmx
        for i in range(n):
            rdif[i] -= a[i]
    lmx = 0
    rmx = 0
    for i in range(n):
            if done[i]:
                continue
            if ldif[i]>lmx:
                lmx = ldif[i]
                lmxi = i
            if rdif[i]>rmx:
                rmx = rdif[i]
                rmxi = i
    ddprint(f"lmx {lmx} lmxi {lmxi} rmx {rmx} rmxi {rmxi}")
ddprint(ans)
print(sm)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
B = sorted(A, reverse=True)
x = 0
S = []
for i in range(n):
  S.append(i+1)

  T = []
for i in range(n):
  for j in range(n):
    if B[i]==A[j]:
      T.append(j+1)
      A[j] = 0

for i in range(n-1):
  a = S[0]
  b = S[-1]
  if T[i] > (a+b)/2:
    x += B[i]*(T[i]-a)
    S.remove(a)
  elif T[i] < (a+b)/2:
    x += B[i]*(b-T[i])
    S.remove(b)
  else:
    if T[i+1] > T[i]:
      x += B[i]*(b-T[i])
      S.remove(b)
    else:
      x += B[i]*(T[i]-a)
      S.remove(a)
y = x + B[-1]*S[0]
print(y+1)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from collections import deque

class MyNumber():
    def __init__(self, a, i, N):
        self.distance = (N-1)/2 - i

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

    dic = {}
    for i, a in enumerate(As):
        if not a in dic:
            dic[a] = []
        dic[a].append(i)

    keys = list(dic.keys())
    keys.sort(reverse=True)

    que = deque([i for i in range(0, N)])
    ans = 0
    for key in keys:
        cands = deque(dic[key])
        while len(cands) != 0:
            mni, mxi = cands[0], cands[-1]
            ret1_r, ret1_l = abs(que[-1]-mni), abs(que[0]-mni)
            ret2_r, ret2_l = abs(que[-1]-mxi), abs(que[0]-mxi)

            mx = max(ret1_r, ret1_l, ret2_r, ret2_l)
            ans += mx*key
            if mx == ret1_r:
                que.pop(), cands.popleft()
            elif mx == ret1_l:
                que.popleft(), cands.popleft()
            elif mx == ret2_r:
                que.pop(), cands.pop()
            else:
                que.popleft(), cands.pop()

    print(ans)





if __name__ == "__main__":
    solve()

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
        # print(idx)
        # print(N // 2)
        cnt += A[idx] * abs(idx - (N // 2))

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(_) for _ in input().split()]

d = {}
for i in range(n):
    d[i+1] = (A[i], i)
L = [i+1 for i in range(n)]
# print(L)
flag = 0
ans = 0
while flag == 0:
    flag = 1
    for i in range(n-1):
        res = 0
        if i >= d[L[i]][1]:
            res += d[L[i]][0]
        else:
            res -= d[L[i]][0]
        if i+1 <= d[L[i+1]][1]:
            res += d[L[i+1]][0]
        else:
            res -= d[L[i+1]][0]
        if res > 0:
            t = L[i]
            L[i] = L[i+1]
            L[i+1] = t
            ans += res
            flag = 0
            # print(L)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
dat = list(map(int, input().split()))
#dat = [[i, datSource[i]] for i in range(n)]
#dat.sort(key=lambda x: (-x[1], -x[0]))
indL = 0
indR = n - 1


loop = math.ceil(n / 2)
used = [False] * n # その数は使ったか？
filled = [False] * n # 埋まっているか？
res = 0
while indR >= indL:
    # まずL
    maxindL = -1
    maxvalL = -9999999999999999999999
    maxindR = -1
    maxvalR = -9999999999999999999999

    for ind in range(n):
        if used[ind]: # もう使っているならパス
            continue
        disL = abs(ind - indL)
        if (dat[ind] * disL) > maxvalL:
            maxvalL = dat[ind] * disL
            maxindL = ind
        disR = abs(ind - indR)
        if (dat[ind] * disR) > maxvalR:
            maxvalR = dat[ind] * disR
            maxindR = ind

    #print(maxvalL, maxvalR)
    if maxvalL >= maxvalR: # L > R
        filled[indL] = True
        used[maxindL] = True
        res += maxvalL
        #print("L:", indL, "maxind", maxindL, "maxval", maxvalL)
        indL += 1
    else:
        filled[indR] = True
        used[maxindR] = True
        res += maxvalR
        #print("R:", indR, "maxind",maxindR, "maxval",maxvalR)
        indR -= 1
print(res)

Submission status: Wrong Answer

Solution code:
# 最小費用流(minimum cost flow)
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())
alist=list(map(int,input().split()))

graph = MinCostFlow(2*N+2)
for i in range(1,N+1):
  graph.addEdge(0,i,1,0)
  #print(0,i,1,0)
  for j in range(1,N+1):
    graph.addEdge(i,N+j,1,-abs(alist[i-1]*(j-i)))
    #print(i,N+j,1,-abs(alist[i-1]*(j-i)))
  graph.addEdge(N+i,2*N+1,1,0)
  #print(N+i,2*N+1,1,0)

print(-graph.minCostFlow(0,2*N+1,N))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
y=n-1
x=0
s=0
for i in range(n):
    b=max(a)
    m=a.index(b)
    if abs(m-x)>abs(y-m):
        s+=b*abs(m-x)
        x+=1
    else:
        s+=b*abs(y-m)
        y-=1


    a[m]=0
    
print(s)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = [int(_) for _ in input().split()]

d = {}
for i in range(n):
    d[i+1] = (A[i], i)
L = [i+1 for i in range(n)]
print(L)
flag = 0
ans = 0
while flag == 0:
    flag = 1
    for i in range(n-1):
        res = 0
        if i >= d[L[i]][1]:
            res += d[L[i]][0]
        else:
            res -= d[L[i]][0]
        if i+1 <= d[L[i+1]][1]:
            res += d[L[i+1]][0]
        else:
            res -= d[L[i+1]][0]
        if res > 0:
            t = L[i]
            L[i] = L[i+1]
            L[i+1] = t
            ans += res
            flag = 0
            # print(L)
print(ans)

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
l, r = 0, N-1
ans = 0
used = set()
while l <= r:
    left = [(A[i] * abs(i - l), i) for i in range(N) if i not in used]
    right = [(A[i] * abs(r - i), i) for i in range(N) if i not in used]
    vl, il = max(left, key=lambda x: x[0])
    vr, ir = max(right, key=lambda x: x[0])
    if vl > vr:
        used.add(il)
        ans += vl
        l += 1
    else:
        used.add(ir)
        ans += vr
        r -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
def slove(n, k):
    a_list = sorted([(i, int(x)) for i,x in enumerate(k.split(), 1)],
                    key= lambda x:x[1], reverse=True)
    index_list = list(range(1, n+1))
    ans = 0
    for i, x in a_list:
        tmp = max([(j, x*abs(i-j)) for j in index_list], key=lambda x: x[1])
        ans += tmp[1]
        index_list.pop(index_list.index(tmp[0]))

    return ans

if __name__ == "__main__":
    n = int(input())
    k = input()
    print(slove(n, k))

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)
ans = 0
cnt = 0
xx = [0]*n
yy = [0]*n
for pt, xyarr in desc:
  for x,y in xyarr:
    if xx[x] == 0 and yy[y] == 0:
      ans += pt
      cnt += 1
      xx[x] = 1
      yy[y] = 1
      if cnt >= n: break
  if cnt >= n: break
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy
N = int( input())
a = list(map(int, input().split(' ')))
l = [0]*N
ain = list(set(a))
p = numpy.argsort(a)[::-1]
a = numpy.sort(a)[::-1]
j = []
for _, x in enumerate(ain):
    j = numpy.sort([p_x for i, p_x in enumerate(p) if a[p_x] == x])[::-1]
    i = numpy.sort([i for i, p_x in enumerate(p) if a[p_x] == x])[::-1]
    p[i] = j
    
    

maxmin = [1, N]
s = 0
for i, a_i in enumerate(a):
    if p[i] + 1 > N/2 :
        s += (p[i] + 1  - maxmin[0])*a_i
        maxmin[0] = maxmin[0] + 1
        
    else:
        s += (maxmin[1]-p[i]-1)*a_i
        maxmin[1] = maxmin[1] - 1
        
print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
AA = list(map(int,input().split()))
AAwIdx = [[0]*2 for _ in range(N)]
for i in range(N):
    AAwIdx[i][0] = i
    AAwIdx[i][1] = AA[i]
AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
#print(AA_sorted)

ans_all = 0
for i in range(2**(int(N/2))):
    AAs = format(i, 'b')
    Idx_i = 0
    Idx_f = N-1
    AnsIdx = [0]*N
    #print(Idx_f)
    answer = 0
    for i in range(N):
        if i>len(AAs)-1:
            if Idx_f - AA_sorted[i][0] > AA_sorted[i][0] - Idx_i:
                answer += abs(AA_sorted[i][0]-Idx_f)*AA_sorted[i][1]
                Idx_f -= 1
            else:
                answer += abs(AA_sorted[i][0]-Idx_i)*AA_sorted[i][1]
                Idx_i += 1

        elif AAs[i] == '1':
        #if Idx_f - AA_sorted[i][0] > AA_sorted[i][0] - Idx_i:
            answer += abs(AA_sorted[i][0]-Idx_f)*AA_sorted[i][1]
            Idx_f -= 1
        else:
            answer += abs(AA_sorted[i][0]-Idx_i)*AA_sorted[i][1]
            Idx_i += 1
    #print(answer)
    ans_all = max(answer, ans_all)
#    print(AAs)
#print(AnsIdx)
print((ans_all))

Submission status: Wrong Answer

Solution code:
N = int(input())
L, R = 0, N - 1
A = [[a, -1] for i, a in enumerate(list(map(int, input().split())))]
for _ in range(N):
    max_p, max_i = -1, -1
    for i in range(N):
        if A[i][1] == -1 and A[i][0] * max(abs(i - L), abs(i - R)) > max_p:
            max_p, max_i = A[i][0] * max(abs(i - L), abs(i - R)), i
    if abs(max_i - L) > abs(max_i - R):
        A[max_i][1], L = L, L + 1
    else:
        A[max_i][1], R = R, R - 1
print(sum([A[i][0] * abs(i - A[i][1]) for i in range(N)]))

Submission status: Wrong Answer

Solution code:
n=int(input(''))
a=input('')
a=a.split(' ')
q=[]
for i in range(n):
    a[i]=int(a[i])
    q.append(0)

s=0
u=-1
if len(a)%2==0 or len(a)%2==1:
    for i in range(int(len(a)/2)):
        o=0
        oj=0
        for j in range(len(a)):
            if q[j]==0:
                m=a[j]*(i-j)
                if m<0:
                    m=m*(-1)
                if o<m:
                    o=m
                    oj=j
        q[oj]=1
        s=s+o

        o=0
        oj=0
        for j in range(len(a)):
            if q[j]==0:
                m=a[j]*(len(a)+u-j)
                if m<0:
                    m=m*(-1)
                if o<m:
                    o=m
                    oj=j
            
        u=u-1
        q[oj]=1
        s=s+o
    
    print(s)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
active = list(map(int,input().split()))
list = [0 for i in range(n)]
counter = 0
sum = 0
for i in list:
    if i == 1:
        continue
    max = [0,0,0]
    for j in range(n):
        if j == counter or list[j] == 1:
            continue
        temp = (active[counter]+active[j])*abs(counter - j)
        if temp > max[0]:
            max = [temp,j,counter]
    sum += max[0]
    print(sum)
    list[max[1]] = 1
    list[max[2]] = 1
    counter += 1
    print(list)

print(sum)