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

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

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

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

n = onem()

a = l()

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

aa.sort(reverse = True)

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

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

Submission status: Wrong Answer

Solution code:
N,A=open(0);N=int(N);A=sorted((int(x),i)for i,x in enumerate(A.split()));t=[0]*N**2
for w in range(1,N):
 a,j=A[w]
 for l in range(N-w):
  r=l+w;t[l*N+r]=max(a*abs(j-l)+t[(l+1)*N+r],a*abs(j-r)+t[l*N+r-1])
print(t[N-1])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    q = []
    for i in range(n):
        l = i
        r = n-i-1
        heappush(q,(-a[i]*max(l,r),l,r,a[i]))
    ans = 0
    while q:
        d,l,r,ai = heappop(q)
        d *= -1
        ans += d
        nq = []
        if l*ai == d:
            while q:
                d,l,r,ai = heappop(q)
                l -= 1
                d = -ai*max(l,r)
                heappush(nq,(d,l,r,ai))
        else:
            while q:
                d,l,r,ai = heappop(q)
                r -= 1
                d = -ai*max(l,r)
                heappush(nq,(d,l,r,ai))
        q = [i for i in nq]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

ans = 0
right, left = len(a) - 1, 0
big = 0
num = 0

for i in range(len(a)):
    r, l = False, False
    big, num = 0, 0
    for j in range(len(a)):
        if a[j] * max(abs(right - j), abs(j - left)) >= a[num] * max(abs(right - num), abs(num - left)):
            big = a[j] * max(abs(right - j), abs(j - left))
            num = j
            if abs(right - j) > abs(j - left):
                r = True
                l = False
            else:
                r = False
                l = True       
    
    ans += big
    a[num] = -1
    
    if r:
        right -= 1
    if l:
        left += 1
        
print(ans)

Submission status: Wrong Answer

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

SUM = sum(A)
back = len(A) -1

c = 0
MAX = 0
f = -1
for i,a in enumerate(A):
    c += a
    r = SUM - c
    tmp = c * (back -i) + r * (i+1)
    if tmp >= MAX:
        MAX = tmp
        f = i

L_d,R_d = [],[]
for i, a in enumerate(A[0:f+1]):
    L_d.append(tuple([a,i]))

for i, a in enumerate(A[f+1::]):
    R_d.append(tuple([a,i+f+1]))
L_d, R_d = sorted(L_d, reverse=True), sorted(R_d, reverse=True)

ans = 0
count = 0
for k,v in L_d:
    ans += k * (back-v-count)
    count += 1
count =0
for k,v in R_d:
    ans += k * (v -count)
    count += 1

print(ans)

Submission status: Wrong Answer

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

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

for i in range(len(a)):
    r, l = False, False
    big, num = 0, 0
    for j in range(len(a)):
        if a[num] <= a[j]:
            big = a[j] * max(abs(right - j), abs(j - left))
            num = j
            if abs(right - j) > abs(j - left):
                r = True
                l = False
            else:
                r = False
                l = True       
    
    ans += big
    a[num] = -1
    
    if r:
        right -= 1
    if l:
        left += 1
        
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())*400
A = list(map(int,input().split()))*400
A = [[a,i] for a,i in zip(A,range(1,N+1))]
A = sorted(A,reverse=True)
INF = float('inf')
dp = [[-INF] * (N+1) for _ in range(N+1)]
dp[0][0] = 0
ans = 0
for x_y in range(1,N+1):
  a = A[x_y-1]
  for x in range(x_y+1):
    y = x_y-x
    if x==0:
      dp[x][y] = dp[x][y-1] + a[0]*(N-y+1-a[1])
    elif y==0:
      dp[x][y] = dp[x-1][y] + a[0]*(a[1]-x)
    else:
      dp[x][y] = max(dp[x-1][y]+a[0]*(a[1]-x),dp[x][y-1] + a[0]*(N-y+1-a[1]))
    
    ans = max(ans,dp[x][y])
print(ans)

Submission status: Wrong Answer

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

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

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

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

n = onem()

a = l()

se = [1 for i in range(n)]
mo = [1 for i in range(n)]


po = []

for i in range(n):
    for j in range(n):
        if i != j:
            po.append(([-(a[j]) * abs(j-i),i,j]))
co = 0
po.sort()
for i in range(len(po)):
    on = po[i]
    if mo[on[1]] and se[on[2]]:
        co -= on[0]
        mo[on[1]] = 0
        se[on[2]] = 0

print(co)

Submission status: Wrong Answer

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

SUM = sum(A)

c = 0
MIN = 10 ** 13
f = -1
for i,a in enumerate(A):
    c += a
    dif = abs(SUM/2 - c)
    if MIN > dif:
        MIN = dif
        f = i 

L_d,R_d = [],[]
for i, a in enumerate(A[0:f+1]):
    L_d.append(tuple([a,i]))

for i, a in enumerate(A[f+1::]):
    R_d.append(tuple([a,i+f+1]))
L_d, R_d = sorted(L_d, reverse=True), sorted(R_d, reverse=True)

ans = 0
back = len(A) -1
count = 0
for k,v in L_d:
    ans += k * (back-v-count)
    count += 1
count =0
for k,v in R_d:
    ans += k * (v -count)
    count += 1

print(ans)

Submission status: Wrong Answer

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

N = int(input())
#A = list(map(int, input().split()))
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A = sorted(A, reverse=True)

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
# indexの配列
dp_indices = []
for v in values:
    dp_indices.extend(num_indcies[v])


dp = [[0] * (N+1) for _ in range(N+1)]
for no, (a, pos) in enumerate(A):
    for i in range(no+1):
        j = no - i
        #k = dp_indices[i+j-2]
        #a = A[k]
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * (pos -i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a * abs(pos - (N-1-j)))
        print(i, j, dp[i][j])

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [(i, a[i]) for i in range(n)]
left, right = 0, n-1

ans = 0
while True:
    happiness = [max(abs(c[0]-left), abs(right-c[0])) * c[1] for c in b]
    # max/argmax
    tmp, argmax = 0, 0
    for i in range(len(b)):
        if happiness[i] > tmp:
            tmp, argmax = happiness[i], i
    if abs(b[argmax][0]-left) > abs(right-b[argmax][0]):
        left += 1
    else:
        right -= 1
    ans += tmp
    del b[argmax]
    if left == right:
        break

ans += max(abs(b[0][0]-left), abs(right-b[0][0])) * b[0][1]
print(ans)

Submission status: Wrong Answer

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

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

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

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

n = onem()

a = l()

se = [1 for i in range(n)]
mo = [1 for i in range(n)]


po = []

for i in range(n):
    for j in range(n):
        if i != j:
            heapq.heappush(po,[-(a[j]) * abs(j-i),i,j])
co = 0

for i in range(len(po)):
    on = heapq.heappop(po)
    if mo[on[1]] and se[on[2]]:
        
        co -= on[0]
        mo[on[1]] = 0
        se[on[2]] = 0

print(co)

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)

if len(set(a))==n:
    print(h)
else:
    print(h+1)

Submission status: Wrong Answer

Solution code:
def score(v,mn,mx):
    ind,val = v
    r = mx -ind
    l = ind -mn
    
    return (l!=r,max(l,r)*val,val)        

def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    X = list(enumerate(A))
    mn = 0
    mx = N-1
    #print(sorted(X,key= lambda x:score(x,mn,mx)))
    ans = 0
    while X:
        X.sort(key= lambda x:score(x,mn,mx))
        ind,val = X[-1]
        r = mx -ind
        l = ind -mn

        if r > l:
            ans += r * val
            mx -=1            
        elif r < l:
            ans += l * val
            mn +=1

        del X[-1]      
        #print(ans,mn,mx,X)  
    print(ans)

resolve()

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(reverse=True)
dp=[[0 for i in range(N+1)] for _ in range(N+1)]
for n in range(N):
    a,p=A[n]
    for x in range(1,n+2):
        y=n+1-x
        dp[x][y]=dp[x-1][y]+round(abs(x-1 - p))*a
    for y in range(1,n+2):
        x=n+1-y
        dp[x][y]=dp[x][y-1]+round(abs(N-y - p))*a
#print(dp)
print(max([dp[x][y] for x in range(N+1) for y in range(N+1) if x+y==N]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int,input().split()))
A = [[a,i] for a,i in zip(A,range(N))]
now = 0
ans = 0
while now!=N:
  score = A[now][0] * abs(A[now][1]-now)
  move_l = np.array([0]*N)
  for i in range(now+1,N):
    move_l[i] = A[now][0] * abs(A[now][1]-i) - score
  
  for i,a in enumerate(A[now+1:],now+1):
    score = (a[0] * abs(a[1] - (i - 1))) - (a[0] * abs(a[1] - i)) 
    move_l[i:] += score
  ma = np.argmax(move_l)
  if ma<=0:
    now+=1
  else:
    ans += move_l[ma]
    tmp = A.pop(now)
    A.insert(ma,tmp)
    
          
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

selected = []
selectedA = []


left_pos = 0
right_pos = N-1

happy_sum = 0
for i in range(N):

    max_val = 0 
    max_pos = 0
    left_sum = 0
    right_sum = 0
    move_val = 0

    for j in range(N):
        if j in selected:
            continue
        if max_val < As[j]:
            max_val = As[j]
            max_pos = j
            left_sum = sum(As[:j])
            right_sum = sum(As[j+1:])
#            move_val = max(left_sum, right_sum)
#        elif max_val == As[j]:
#            if max(move_val, )
    selected.append(max_pos)
    if left_sum >= right_sum:
        happy_sum += abs(left_pos - max_pos)*max_val
        left_pos+=1
    else:
        happy_sum += abs(right_pos - max_pos)*max_val
        right_pos-=1



       
#    selected.append(max_pos)
#    selectedA.append(max_val)
#    if abs(left_pos-max_pos) >= abs(right_pos -max_pos):
#        happy_sum += abs(left_pos-max_pos)*max_val
#        left_pos += 1
#    else:
#        happy_sum += abs(right_pos-max_pos)*max_val
#        right_pos -= 1
#    
#    if len(selected) == N:
#        break

print(happy_sum)

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):
    #     for j in range(i, n):
    for i in range(n-1, -1, -1):
        for j in range(i, -1, -1):
            # print(i,j)
            v_i = d[L[i]][0]
            idx_i = d[L[i]][1]
            v_j = d[L[j]][0]
            idx_j = d[L[j]][1]
            res = (abs(j - idx_i) * v_i + abs(i - idx_j) * v_j) - (abs(i - idx_i) * v_i + abs(j - idx_j) * v_j)
            if res > 0:
                t = L[i]
                L[i] = L[j]
                L[j] = t
                ans += res
                flag = 0
                # print('i', i)
                # print('res', res)
                # print(L)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
As = [int(x) for x in stdin.readline().rstrip().split()]

print(As)
selected = []
selectedA = []


left_pos = 0
right_pos = N-1

happy_sum = 0
for i in range(N):

    max_val = 0 
    max_pos = 0
    left_sum = 0
    right_sum = 0
    move_val = 0

    for j in range(N):
        if j in selected:
            continue
        if max_val < As[j]:
            max_val = As[j]
            max_pos = j
            left_sum = sum(As[:j])
            right_sum = sum(As[j+1:])
#            move_val = max(left_sum, right_sum)
#        elif max_val == As[j]:
#            if max(move_val, )
    selected.append(max_pos)
    if left_sum >= right_sum:
        happy_sum += abs(left_pos - max_pos)*max_val
        left_pos+=1
    else:
        happy_sum += abs(right_pos - max_pos)*max_val
        right_pos-=1



       
#    selected.append(max_pos)
#    selectedA.append(max_val)
#    if abs(left_pos-max_pos) >= abs(right_pos -max_pos):
#        happy_sum += abs(left_pos-max_pos)*max_val
#        left_pos += 1
#    else:
#        happy_sum += abs(right_pos-max_pos)*max_val
#        right_pos -= 1
#    
#    if len(selected) == N:
#        break

print(happy_sum)

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):
    #     for j in range(i, n):
    for i in range(n-2, -1, -1):
        for j in range(n-1, i-1, -1):
            # print(i,j)
            v_i = d[L[i]][0]
            idx_i = d[L[i]][1]
            v_j = d[L[j]][0]
            idx_j = d[L[j]][1]
            res = (abs(j - idx_i) * v_i + abs(i - idx_j) * v_j) - (abs(i - idx_i) * v_i + abs(j - idx_j) * v_j)
            if res > 0:
                t = L[i]
                L[i] = L[j]
                L[j] = t
                ans += res
                flag = 0
                # print('i', i)
                # print('res', res)
                # print(L)
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#print("N",N)
#print("A_list",A_list)
#-----

A2_list = [None]*len(A_list)
A_val_dic = {}

for i,v in enumerate(A_list):
    A_val_dic.setdefault(v, [])
    A_val_dic[v].append(i)

#print("A_val_dic",A_val_dic)

sum = 0
for k in sorted(A_val_dic.keys(), reverse=True):
    
    for idx_A in A_val_dic[k]:
        L = A2_list.index(None)
        
        for i_A2 in range(len(A2_list)-1,0,-1):
            if A2_list[i_A2] == None:
                R = i_A2
                break
        
        if abs(L - idx_A) >= abs(R - idx_A):
            A2_list[L] = A_list[idx_A]
            sum += A_list[idx_A] * abs(L - idx_A)
        else:
            A2_list[R] = A_list[idx_A]
            sum += A_list[idx_A] * abs(R - idx_A)
    
    #print("sum",sum,"A2_list",A2_list)
    
#print("END sum",sum,"A2_list",A2_list)
print(sum)

Submission status: Wrong Answer

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

max_num = 0
for i in range(1, N):
  suma = sum(A[:i])*(N-i) + sum(A[i:])*i
  if max_num < suma:
    max_num = suma
print(max_num)

Submission status: Wrong Answer

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

dp = {}
dp[(0, N-1)] = 0
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        a = As[i]
        lsc = rsc = 0
        if l > 0:
            # l-1, r から
            lsc = dp[(l-1, r)] + a
        if r < N-1:
            # l, r+1 から
            rsc = dp[(l, r+1)] + a
        ndp[(l, r)] = max(lsc, rsc)
    dp = ndp
print(max(dp.values()))

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
arridx = [(i, a) for i, a in enumerate(As)]
arridx.sort(key=lambda x: -x[1])

scores = []
for i in range(N):
    arr = [(As[j] * abs(i-j), j) for j in range(N)]
    arr.sort()
    scores.append(arr)

dp = {}
dp[(0, N-1)] = [0, set()]
for i in range(N-1, -1, -1):
    ndp = {}
    for l in range(N-i+1):
        r = l + i - 1
        tmpl = tmplidx = lsc = tmpr = tmpridx = rsc = 0
        if l > 0:
            # l-1, r から
            lsc, lst = dp[(l-1, r)]
            il = -1
            while True:
                tmpl, tmplidx = scores[l-1][il]
                if tmplidx in lst:
                    il -= 1
                else:
                    break
        if r < N-1:
            # l, r+1 から
            rsc, rst = dp[(l, r+1)]
            ir = -1
            while True:
                tmpr, tmpridx = scores[r+1][ir]
                if tmpridx in rst:
                    ir -= 1
                else:
                    break
        if lsc + tmpl > rsc + tmpr:
            ndp[(l, r)] = [lsc+tmpl, lst|{tmplidx}]
        else:
            ndp[(l, r)] = [rsc+tmpr, rst|{tmpridx}]
    dp = ndp
print(max([s for s, st in dp.values()]))

Submission status: Wrong Answer

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

max = n - 1
min = 0
li = [0] * n
cnt = 0
ans = 0
while cnt < n:
    maxa = None
    for i in range(0, n):
        if a[i] == None: continue
        l = False
        if a[i] * abs(i - min) > a[i] * abs(i - max):
            l = True
            t = a[i] * abs(i - min)
        else :
            t = a[i] * abs(i - max)
        if maxa == None or t > maxa:
            maxa = t
            maxid = i
            l2 = l
    if l2 == True :
        li[min] = a[maxid]
        min += 1
    else :
        li[max] = a[maxid]
        max -= 1
    ans += maxa
    a[maxid] = None
    #print(li, a, maxa)
    cnt += 1
print(ans)

Submission status: Wrong Answer

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

happiness = 0

exist_index = list(range(N))
exist_visited = [0] * N
empty_index = list(range(N))
for k in range(N):
    largest_gain = -1
    # print(exist_index, exist_visited, empty_index)
    for i in range(N):
        if exist_visited[i] == 1:
            continue

        place = 0 if abs(exist_index[i] - empty_index[0]) > abs(exist_index[i] - empty_index[-1]) else -1

        gain = A[exist_index[i]] * abs(exist_index[i] - empty_index[place])

        # print(place, gain)
        if gain > largest_gain:
            largest_gain = gain
            best_child = exist_index[i]
            best_place = place
    # print("--")
    # print(largest_gain, best_child)
    # print("--")
    happiness += largest_gain
    exist_visited[best_child] = 1
    if best_place == 0:
        empty_index = empty_index[1:]
    else:
        empty_index = empty_index[:-1]
    # empty_index = empty_index[0:place] + empty_index[place + 1:]

print(happiness)

Submission status: Wrong Answer

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

ans = []
sorts = []
for i in range(n):
    temp = [a[i] * abs(i - j) for j in range(n)]
    ans.append(temp)
    sorts.append(max(temp))

sorts = np.argsort(sorts)
ans = np.array(ans)[sorts][::-1]

mem = np.array([True for i in range(n)])
total = 0
for ai in ans:
    ai[np.logical_not(mem)] = 0
    total += ai.max()    
    mem[ai.argmax()] = False
print(total)

Submission status: Wrong Answer

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

happiness = 0

exist_index = list(range(N))
exist_visited = [0] * N
empty_index = list(range(N))
for k in range(N):
    largest_gain = -1
    # print(exist_index, exist_visited, empty_index)
    for i in range(N):
        if exist_visited[i] == 1:
            continue

        place = 0 if abs(exist_index[i] - empty_index[0]) > abs(exist_index[i] - empty_index[-1]) else -1

        gain = max(A[exist_index[i]] * abs(exist_index[i] - empty_index[0]),
                   A[exist_index[i]] * abs(exist_index[i] - empty_index[-1]))
        # print(place, gain)
        if gain > largest_gain:
            largest_gain = gain
            best_child = exist_index[i]
            best_place = place
    # print("--")
    # print(largest_gain, best_child)
    # print("--")
    happiness += largest_gain
    exist_visited[best_child] = 1
    if best_place == 0:
        empty_index = empty_index[1:]
    else:
        empty_index = empty_index[:-1]
    # empty_index = empty_index[0:place] + empty_index[place + 1:]

print(happiness)

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 - j)
                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:
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:
# 最小費用流(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:
import collections
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()
    rem = set(range(N))
    res = {}
    for i in range(N):
        hbest = -1
        arg = None
        for j in rem:
            pj = pref[j]
            for k in range(len(pj)-1, -1, -1):
                h, pos = pj[k]
                if pos in res:
                    del pj[k]
                    continue
                if hbest < h:
                    hbest = h
                    arg = (j,pos)
        baby, pos = arg
        res[pos] = hbest
        rem.remove(baby)
    assert len(rem) == 0
    return sum(res.values())

print(solve())