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

a = [(i, ai) for i, ai in enumerate(A)]
a.sort(key=lambda x: x[1], reverse=True)

import numpy as np
dp = np.zeros((N+1, N+1), np.int8)

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
B = [[] for _ in range(N)]
for i, A in enumerate(input().split()):
    for j in range(N):
        B[j].append(int(A)*abs(i-j))
# print(B)
S = 0
while B != []:
    for i in range(len(B)):
        n = np.argmax(B[i])
        if np.argmax(np.array(B).T.tolist()[n]) == i:
            S += B[i][n]
            for j in range(len(B)):
                del B[j][n]
            del B[i]
            break
print(S)

Submission status: Wrong Answer

Solution code:
import sys



def main():
    N = int(input())

    A = []
    for i, a in enumerate(map(int, input().split(' '))):
        A.append((a, i))
    A.sort(reverse=True)

    i = 0
    L = 0
    R = N - 1
    S = 0
    while i < len(A):
        a0, p0 = A[i]
        dL = abs(L - p0)
        dR = abs(R - p0)
        if dL < dR:
            if i + 3 <= len(A):
                a1, p1 = A[i + 1]
                a2, p2 = A[i + 2]
                if a1 + a2 > a0 and p1 < p0 and p2 < p0:
                    S += a0 * dL + a1 * abs(R - p1) + a2 * abs(R - 1 - p2)
                    L += 1
                    R -= 2
                    i += 3
                    continue
            S += a0 * dR
            R -= 1
        else:
            if i + 3 <= len(A):
                a1, p1 = A[i + 1]
                a2, p2 = A[i + 2]
                if a1 + a2 > a0 and p1 > p0 and p2 > p0:
                    S += a0 * dL + a1 * abs(L - p1) + a2 * abs(L + 1 - p2)
                    L += 2
                    R -= 1
                    i += 3
                    continue
            S += a0 * dL
            L += 1
        i += 1
    print(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())

    A = {}
    for i, a in enumerate(map(int, input().split(' '))):
        if a in A:
            A[a].append(i)
        else:
            A[a] = [i]

    B = list(A.keys())
    B.sort(reverse=True)
    L = 0
    R = N - 1
    S = 0
    for i in range(len(B)):
        a = B[i]
        J = A[a]
        for j in range(len(J)):
            p = J[j]
            d = abs(L - p)
            e = abs(R - p)
            if d < e:
                S += e * a
                R -= 1
            else:
                S += d * a
                L += 1
    print(S)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    a_idx = [(a, -idx) for idx, a in enumerate(A)]
    a_idx.sort(reverse=True)
    a_idx = [(a, -idx) for a, idx in a_idx]

    dp = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
    for i in range(N + 2):
        dp[-1][i] = -100
        dp[i][-1] = -100
    for num_go_left in range(0, N + 1):
        for num_go_right in range(0, N + 1 - num_go_left):
            if num_go_left == 0 and num_go_right == 0:
                continue
            current_baby_idx = num_go_right + num_go_left - 1
            active_vale, position = a_idx[current_baby_idx]
            left_idx = num_go_left - 1
            right_idx = N - num_go_right

            dp[num_go_left][num_go_right] = max(
                dp[num_go_left - 1][num_go_right] + active_vale * (position - left_idx),
                dp[num_go_left][num_go_right - 1] + active_vale * (right_idx - position)
            )

    return max([dp[num_go_left][N - num_go_left] for num_go_left in range(0, N + 1)])


if __name__ == '__main__':
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    a_idx = [(a, -idx) for idx, a in enumerate(A)]
    a_idx.sort(reverse=True)
    a_idx = [(a, -idx) for a, idx in a_idx]

    dp = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
    for i in range(N + 2):
        dp[-1][i] = -100
        dp[i][-1] = -100
    for num_go_left in range(0, N + 1):
        for num_go_right in range(0, N + 1 - num_go_left):
            if num_go_left == 0 and num_go_right == 0:
                continue
            current_baby_idx = num_go_right + num_go_left - 1
            active_vale, position = a_idx[current_baby_idx]
            left_idx = num_go_left - 1
            right_idx = N - num_go_right

            dp[num_go_left][num_go_right] = max(
                dp[num_go_left - 1][num_go_right] + active_vale * abs(position - left_idx),
                dp[num_go_left][num_go_right - 1] + active_vale * abs(right_idx - position)
            )

    return max([dp[num_go_left][N - num_go_left] for num_go_left in range(0, N + 1)])


if __name__ == '__main__':
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def solve():
    N = int(input())
    A = list(map(int, input().split()))
    a_idx = [(a, idx) for idx, a in enumerate(A)]
    a_idx.sort(reverse=True)

    dp = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
    for i in range(N + 2):
        dp[-1][i] = -100
        dp[i][-1] = -100
    for num_go_left in range(0, N + 1):
        for num_go_right in range(0, N + 1 - num_go_left):
            if num_go_left == 0 and num_go_right == 0:
                continue
            current_baby_idx = num_go_right + num_go_left - 1
            active_vale, position = a_idx[current_baby_idx]
            left_idx = num_go_left - 1
            right_idx = N - num_go_right

            dp[num_go_left][num_go_right] = max(
                dp[num_go_left - 1][num_go_right] + active_vale * abs(position - left_idx),
                dp[num_go_left][num_go_right - 1] + active_vale * abs(right_idx - position)
            )
    return max([dp[num_go_left][N - num_go_left] for num_go_left in range(0, N + 1)])


if __name__ == '__main__':
    answer = solve()
    print(answer)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
ans=0
f_max=0
b_max=0
f_box=[0 for i in range(N)]
b_box=[0 for i in range(N)]
count=N
for i in range(N):
    f_box[i]=a[i]*i
    b_box[i]=a[i]*(N-i-1)

while count>0:
    f_max=max(f_box)
    b_max=max(b_box)
    count-=1
    if f_max>b_max:
        ans+=f_max
        k=f_box[::-1].index(f_max)
        a.pop(count-k)
        f_box.pop(count-k)
        b_box.pop(count-k)
        for i in range(count):
            f_box[i]-=a[i]
    elif b_max>f_max:
        ans+=b_max
        k=b_box.index(b_max)
        a.pop(k)
        f_box.pop(k)
        b_box.pop(k)
        for i in range(count):
            b_box[i]-=a[i]
    else:
        ans+=f_max
        kf=f_box[::-1].index(f_max)
        kb=b_box.index(b_max)
        if count-kf<kb:
            k=kb
            a.pop(k)
            f_box.pop(k)
            b_box.pop(k)
            for i in range(count):
                b_box[i]-=a[i]
        else:
            k=count-kf
            a.pop(k)
            f_box.pop(k)
            b_box.pop(k)
            for i in range(count):
                f_box[i]-=a[i]
print(ans)

Submission status: Wrong Answer

Solution code:


# coding: utf-8
DATA = """
5
1 2 9 3 4
""".split("\n")

##
# 

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = int(get_line().strip())

Memo = [0] * (N)
A = [int(i) for i in get_line().strip().split(" ")]

for i in range(len(A)):
    Memo[i] = (A[i], i)

def VV (s, e):
    def V(l):
        v, index = l
        if index - s < e - index:
            return v * (e - index)
        else:
            return v * (index - s)
    return V

s = 0
e = N-1

ret = 0
while(len(Memo) > 0):
    Memo.sort(key = VV(s, e))
    pop = Memo.pop()
    #print (pop, s, e)
    if pop[1] - s == e - pop[1]:
        if len(Memo) > 0:
            pop2 = Memo[-1]
            if pop2[1] - s > e - pop2[1]:
                ret += pop[0] * (e - pop[1])
                e -= 1
            else:
                ret += pop[0] * (pop[1] - s)
                s += 1
    elif pop[1] - s < e - pop[1]:
        ret += pop[0] * (e - pop[1])
        e -= 1
    else:
        ret += pop[0] * (pop[1] - s)
        s += 1
print (ret)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split(" ")))
d={}
lis=[]
sum=0
for i in range(len(a)):
    d[i+1]=a[i]
for t in sorted(d.items(),key=lambda x:(x[1],x[0]),reverse=True):
    lis.append(t)
start=1
for l in lis :
    if l[0]-start>n-l[0]:
        sum+=(l[0]-start)*l[1]
        start+=1
    else:
        sum+=(n-l[0])*l[1]
        n-=1


print(sum+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
#n=int(input())
#a_=list(map(int,input().split()))
import numpy as np
n=2000
a_=range(1,n+1)
a=[]
for i,ai in enumerate(a_):
      a.append([1+i,ai])
a.sort(key=lambda x:x[1],reverse=True)
dp=np.zeros((n+1,n+1),np.int64) #dp[i,j]:i人目までを配置し終えていて、そのうちj人を右に置いた時の最大値。j<=i
dp[1,1]=a[0][1]*(n-a[0][0])
dp[1,0]=a[0][1]*(a[0][0]-1)
for i in range(2,n+1):#i人目の幼児。a[i-1]
      dp[i,0]=dp[i-1,0]+a[i-1][1]*abs((a[i-1][0]-1-(i-1))) #i人目を左にする。その時左に溜まっているのはi-1人
      dp[i,i]=dp[i-1,i-1]+a[i-1][1]*abs((n-a[i-1][0]-(i-1))) #i人目を右にする。その時右に溜まっているのはi-1人
      #i人目を左に
      l=dp[i-1,1:i]+[a[i-1][1]*abs((a[i-1][0]-1-j))for j in range(i-2,-1,-1)] #j:左に溜まっている人数
      #i人目を右に
      r=dp[i-1,:i-1]+[a[i-1][1]*abs((n-a[i-1][0]-j)) for j in range(i-1)] #j:右に溜まっている人数
      dp[i,1:i]=np.maximum(l,r)
print(max(dp[n]))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

max_happiness = [a * max(N-i-1, i) for i, a in enumerate(A)]
left_right = [(N-i-1)-i for i in range(N)]
args = np.flip(np.argsort(max_happiness))

res = 0


while(True) :
  if(len(max_happiness)==0) :
    break
  else :
    ## 最大の嬉しさを抜き出す
    temp_max = max_happiness[args[0]]
    ## 最大の嬉しさになる子供をすべて見つける
    index = [i for i, x in enumerate(max_happiness) if x == temp_max]
    
    ## indexの中で、活発度が最大の子供を選ぶ
    max_index = 0
    v_ind = 0
    for i in index :
      if(v_ind < A[i]) :
        max_index = i
        v_ind = A[i]
    
    res += temp_max
    ## 左右の選択
    if(left_right[max_index] > 0) :
      ## 右のほうが近い場合は嬉しさが下がる
      max_happiness = list(map(lambda x : x[1]-A[x[0]]*int((np.sign(left_right[x[0]])+1)/2), enumerate(max_happiness)))
      left_right_flag = -1
    if(left_right[max_index] < 0) :
      ## 左のほうが近い場合は嬉しさが下がる
      max_happiness = list(map(lambda x : x[1]+A[x[0]]*int((np.sign(left_right[x[0]])-1)/2), enumerate(max_happiness)))
      left_right_flag = 1
    ## 等しければ、2番目に嬉しさが大きい子供を参照
    if(left_right[max_index] == 0) :
      if(len(args) == 1) :
        break
      temp_max_second = max_happiness[args[1]]
      index_second = [i for i, x in enumerate(max_happiness) if x == temp_max_second]
      second_index = 0
      v_second = 0
      for i in index_second :
        if((v_second < A[i]) and (i != max_index)) :
          second_index = i
          v_second = A[i]
      if(left_right[second_index] > 0) :
        ## 左のほうが近い場合は嬉しさが下がる
        max_happiness = list(map(lambda x : x[1]+A[x[0]]*int((np.sign(left_right[x[0]])-1)/2), enumerate(max_happiness)))
        left_right_flag = 1
      else :
        ## 右のほうが近い場合は嬉しさが下がる
        max_happiness = list(map(lambda x : x[1]-A[x[0]]*int((np.sign(left_right[x[0]])+1)/2), enumerate(max_happiness)))
        left_right_flag = -1
    ##繰り返しの処理
    max_happiness.pop(max_index)
    left_right.pop(max_index)
    left_right = list(map(lambda x : x+left_right_flag, left_right))
    A.pop(max_index)
    args = args[1:]
    args = np.array(list(map(lambda x : x-1 if (x>max_index) else x, args)))
    

print(res)

Submission status: Wrong Answer

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

ans = 0
j = 0
k = n-1

for i in range(n):
    l = 0
    for id, v in enumerate(a):
        if (max(id-j, k-id))*v > l:
            l = (max(id-j, k-id)) * v
            mid = id
            mv = v
    ans = ans + l
    a[mid] = 0
    if  mid-j >= k-mid:
        j = j + 1
    else:
        k = k - 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
j = 0
k = n-1

for i in range(n):
    l = 0
    for id, v in enumerate(a):
        if (max(id-j, k-id))*v > l:
            l = (max(id-j, k-id)) * v
            mid = id
            mv = v
    ans = ans + l
    a[mid] = 0
    if  mid-j > k-mid:
        j = j + 1
    else:
        k = k - 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
j = 0
k = n-1

for i in range(n):
    l = 0
    for id, v in enumerate(a):
        if (max(id+j, k-id))*v > l:
            l = (max(id-j, k-id)) * v
            mid = id
            mv = v
    ans = ans + l
    a[mid] = 0
    if  mid-j > k-mid:
        j = j + 1
    else:
        k = k - 1

print(ans)

Submission status: Wrong Answer

Solution code:
tmp = input().split()
NChild = int(tmp[0])

tmp = input().split()
Active_List = [int(s) for s in tmp]

ArrayD = [0] * NChild

for i in range(NChild):
    ArrayD[i] = [i+1, Active_List[i], max(abs(i),abs(NChild-i-1)), Active_List[i]*max(abs(i),abs(NChild-i-1))]

ArrayC = sorted(ArrayD, key=lambda x: (x[3], x[2], x[1]), reverse=True)

NArray = [0] * NChild
EndP = NChild - 1
StartP = 0

for i in range(NChild):
    P = ArrayC[i][0]
    if abs(P - StartP - 1) < abs(P - EndP - 1):
        NArray[EndP] = P
        EndP = EndP - 1
    else:
        NArray[StartP] = P
        StartP = StartP + 1
        
TotalResult = 0

for i in range(NChild):
    KeyA = ArrayC.index(ArrayD[NArray[i]-1])
    TotalResult = TotalResult + ArrayC[KeyA][1]*abs(NArray[i]-i-1)

print(TotalResult)

Submission status: Wrong Answer

Solution code:
tmp = input().split()
NChild = int(tmp[0])

tmp = input().split()
Active_List = [int(s) for s in tmp]

ArrayD = [0] * NChild

for i in range(NChild):
    ArrayD[i] = [i+1, Active_List[i], max(abs(i),abs(NChild-i-1)), Active_List[i]*max(abs(i),abs(NChild-i-1))]

ArrayC = sorted(ArrayD, key=lambda x: (x[3], x[1],x[2]), reverse=True)

NArray = [0] * NChild
EndP = NChild - 1
StartP = 0

for i in range(NChild):
    P = ArrayC[i][0]
    if abs(P - StartP - 1) < abs(P - EndP - 1):
        NArray[EndP] = P
        EndP = EndP - 1
    else:
        NArray[StartP] = P
        StartP = StartP + 1
        
TotalResult = 0

for i in range(NChild):
    KeyA = ArrayC.index(ArrayD[NArray[i]-1])
    TotalResult = TotalResult + ArrayC[KeyA][1]*abs(NArray[i]-i-1)

print(TotalResult)

Submission status: Wrong Answer

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

B=[(j,i) for i,j in enumerate(A)]
B.sort(reverse=True)

dp=[[0]*(N+1) for _ in range(N+1)]

c=0
for k,v in B:
    for i in range(c+1):
        dp[i+1][c-i]=max(dp[i+1][c-i],dp[i][c-i]+abs(v*(k-i)))
        dp[i][c-i+1]=max(dp[i][c-i+1],dp[i][c-i]+abs(v*(N-(c-i)-k-1)))
    c+=1

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

print(ans)

Submission status: Wrong Answer

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

for i, a in enumerate(A):
    table.append([a,i])
table.sort()

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][0] = DP[x-1][0] + baby * abs(pos-x+1)
        DP[0][y] = DP[x][y-1] + baby * abs(pos-(N-y))
        if x & y:
            DP[x][y] = max(DP[x-1][y] + baby * abs(pos-x+1),\
                     DP[x][y-1] + baby * abs(pos-(N-y)))

ans = 0
for i in range(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()))
table = []

for i, a in enumerate(A):
    table.append([a,i])
table.sort(reverse=True)

# DP[i][j] 左端に i 個, 右端に j 個貪欲に詰めたときのうれしさ
DP = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
    # i 人目 table[i-1] の幼児を移動させる
    baby, pos = table.pop()
    for x in range(i+1):
        y = i - x

        #左端に置く場合と右端に置く場合でmax
        DP[x][y] = max((DP[x-1][y] + baby * abs(pos-x+1)) * (x>0),\
                     (DP[x][y-1] + baby * abs(pos-(N-y)) * (y>0)))

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

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h,w): return [[i for j in range(w)] for k in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N = I()
l = LI()
array = [i for i in range(N)]
happy = 0
while True:
    for i in range(N-1):
        left = array[i]
        right = array[i+1]
        left_p = 1 if i-left>=0 else -1
        right_p = 1 if i+1-right<=0 else -1
        if left_p*l[left]+right_p*l[right]>0:
            happy += left_p*l[left]+right_p*l[right]
            array[i],array[i+1] = array[i+1],array[i]
            break
    else:
        break
print(happy)

Submission status: Wrong Answer

Solution code:
import heapq

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

ans = 0
que = []
for i in range(N):
    for j in range(N):
        # Ai -> j
        heapq.heappush(que, (- abs(i - j) * A[i] , i,  j))

occupied = set()
used = set()

while len(que):
    activiness, use, pos = heapq.heappop(que)
    if pos in occupied or use in used:
        continue
    ans += -activiness
    occupied.add(pos)
    used.add(use)

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq

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

ans = 0
que = []
for i in range(N):
    for j in range(N):
        # Ai -> j
        heapq.heappush(que, (- abs(i - j) * A[i] , i,  j))

occupied = set()
used = set()

while len(occupied) < N and len(used) < N:
    activiness, use, pos = heapq.heappop(que)
    if pos in occupied or use in used:
        continue
    ans += -activiness
    occupied.add(pos)
    used.add(use)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def slove(n, k):
    a_list = sorted([(int(x),i) for i,x in enumerate(k.split())], reverse=True)
    dp = [[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n-i):
            dp[i+1][j] = max(dp[i+1][j],
                         dp[i][j]+a_list[i+j][0]*abs(a_list[i+j][1]-i))
            dp[i][j+1] = max(dp[i][j+1],
                         dp[i][j]+a_list[i+j][0]*abs((n-1-j)-a_list[i+j][1]))

    return  max([max(i[:n-1]) for i in dp])

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    k = input()
    print(slove(n, k))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
pt = [0] * n

st = 0
ed = n - 1

ans = 0

for i in range(n):
    ax = max(a)
    p = a.index(ax)
    a[p] = 0
    if (abs(p - st) > abs(p - ed)):
        ans += ax * abs(p - st)
        st += 1
    else:
        ans += ax * abs(p-ed)
        ed -= 1
    #print("{} {} {}".format(ans,st,ed))
print(ans)

Submission status: Wrong Answer

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

sorted_list=sorted(l,reverse=True)

ans=0
x=0

for i in sorted_list:
  a=l.index(i)
  l[a]=0
  if (a-x)>=((n-1)-a):
    ans+=i*(a-x)
    x+=1
  else:
    ans+=i*((n-1)-a)
    n-=1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
dp = [[-1 for _ in range(n)] for __ in range(n)]
print("ready")
dp[0][n-1] = 0
l = list(map(int, input().split()))

m = []
for x, c in enumerate(l):
    m.append((c, x))
m.sort(reverse=True)



result = 0
for i, (c, x) in enumerate(m):
    s = n-i-2
    for j in range(i+2):
        if j + s + 1 < n:
            dp[j][j + s] = max(dp[j][j + s], dp[j][j + s + 1] + c * abs(x - (j + s + 1)))
        if j > 0 and j < n:
            # print(j, s)

            dp[j][j+s] = max(dp[j][j+s], dp[j-1][j+s] + c * abs(x - (j-1)))
        if j < n:
            result = max(result, dp[j][j+s])
        # print("res: ", result)
print(result)

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]] 
        s = abs(temp[j]-z[0])*a[temp[j]]
        u = abs(temp[j]-z[1])*a[temp[j]]
        if(q[0]+s > q[1]+u):
            for k in range(temp[j]):
                l[k][0] -= a[temp[j]]
            p += s
            z[0] += 1
        else:
            for k in range(temp[j]+1,n):
                l[k][1] -= a[temp[j]]
            p += u
            z[1] -= 1
print(p)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
lst = [i for i in range(n)]
start = 0
end = n-1
max_happy = 0
for _ in range(n):
  m = -1
  for j in lst:
    if abs(j - start) > abs(j - end):
      happy = a[j] * abs(j - start)
      idx = 0
    else:
      happy = a[j] * abs(j - end)
      idx = 1
    if happy > m:
      m = happy
      m_idx = idx
      m_point = j
  max_happy += m
  lst.remove(m_point)
  if m_idx == 0:
    start += 1
  else:
    end -= 1
print(max_happy)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [(int(v), i) for i, v in enumerate(input().split())]
A = sorted(A, key=lambda x: x[1])
dp = [[0 for j in range(2005)] for i in range(2005)]
for i in range(N):
    pi = A[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi - l) * A[pi][0])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((N-r-1) - pi) * A[pi][0])

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

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

Submission status: Wrong Answer

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

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

l = 0
r = n-1
ans = 0
f = 0

for ai, i in a:
    pl = abs(l - i)
    pr = abs(r - i)
    if pl > pr:
        ans += pl * ai
        l += 1
        if f:
            r -= 1
            f = 0
    elif pl < pr:
        ans += pr * ai
        r -= 1
        if f:
            l += 1
            f = 0
    else:
        ans += pr * ai
        f = 1
print(ans)

Submission status: Wrong Answer

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

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

l = 0
r = n-1
ans = 0
f = 0

for i, ai in a:
    pl = abs(l - i)
    pr = abs(r - i)
    if pl > pr:
        ans += pl * ai
        l += 1
        if f:
            r -= 1
            f = 0
    elif pl < pr:
        ans += pr * ai
        r -= 1
        if f:
            l += 1
            f = 0
    else:
        ans += pr * ai
        f = 1
print(ans)

Submission status: Wrong Answer

Solution code:
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = ai * abs(i-x+1)
        dp[0][x] = ai * abs(n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai * abs(i-x+1),
                           dp[x][y-1] + ai * abs(n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]

    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))

Submission status: Wrong Answer

Solution code:
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[x-1]
        dp[x][0] = ai * (i-x+1)
        dp[0][x] = ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[s-1]
            dp[x][y] = max(dp[x-1][y] + ai*(i-x+1), dp[x][y-1] + ai*(n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]

    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted([(a[i], i)for i in range(n)], reverse=True)
    print(solve(n, aii))

Submission status: Wrong Answer

Solution code:
def i1str():
    return input()


def istrs(n=None):
    if n is None:
        return input().split()
    a = []
    for _ in range(n):
        a.append(istrs())
    return a


def i1num():
    return int(input())


def inums(n=None):
    if n is None:
        return list(map(int, input().split()))
    a = []
    for _ in range(n):
        a.append(inums())
    return a


def ostrs(l, sp=" "):
    print(sp.join(l))


def onums(l, sp=" "):
    print(sp.join(map(str, l)))


def solve(n, aii):
    dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

    for x in range(1, n+1):
        ai, i = aii[n-x]
        dp[x][0] = ai * (i-x+1)
        dp[0][x] = ai * (n-x-i)

    for s in range(1, n+1):
        for x in range(1, s):
            y = s - x
            ai, i = aii[n-s]
            dp[x][y] = max(dp[x-1][y] + ai*(i-x+1), dp[x][y-1] + ai*(n-y-i))

    res = 0
    for x in range(n+1):
        if dp[x][n-x] > res:
            res = dp[x][n-x]

    return res


if __name__ == "__main__":
    n = i1num()
    a = inums()
    aii = sorted((a[i], i)for i in range(n))
    print(solve(n, aii))

Submission status: Wrong Answer

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

index = list(range(N))
sorted_index = sorted(index,key = lambda i: -a_list[i])
sorted_a = [a_list[i] for i in sorted_index]
start = 0
end = N-1
sum = 0
for i in range(N):
    if abs(end - sorted_index[i]) > abs(sorted_index[i] -start):
        sum += sorted_a[i]*abs(end-sorted_index[i])
        end -=1
    else:
        sum += sorted_a[i]*abs(sorted_index[i]-start)
        start +=1
print(sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#print(a)
'''
b=sorted(a,reverse=True)#降順ソート
'''
b=[]#sorting
c=[]#移動前
for i in range(n):
  b.append(max(a))
  c.append(a.index(max(a)))
  a[a.index(max(a))]=0
#print(b)
#print(c)



'''
for i in range(n):
  c.append(b.index(a[i]))
'''
dp=[[0]*n for i in range(n)]
dp[0][0]=0
x=0
y=0
for i in range(n):
  if dp[x][y]+((n-1-x)-c[i])*b[i]>dp[x][y]+(c[i]-y)*b[i]:
    #print('  from',c[i],'to',n-1-x,'の',b[i],'を足した値を')
    dp[x+1][y]=dp[x][y]+((n-1-x)-c[i])*b[i]
    x+=1
    #print('x:when dp',x,y,':',dp[x][y],'に入れる。')
  else:
    #print('  from',c[i],'to',y,'の',b[i],'を足した値を')
    dp[x][y+1]=dp[x][y]+(c[i]-y)*b[i]
    y+=1
    #print('y:when dp',x,y,':',dp[x][y],'に入れる。')
ans=[]
for i in range(n):
  #print(dp[i])
  for j in range(n):
    if i+j==n:
      ans.append(dp[i][j])
print(max(ans))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10000)

@lru_cache(maxsize = None)
def rec(i, j):
    flag = False
    flag_ = False
    tmp = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - i)
    if tmp > dp[i+1][j]:
        dp[i+1][j] = tmp
        flag = True
    tmp_ = dp[i][j] + A[i+j][0] * abs(A[i+j][1] - N + j + 1)
    if tmp_ > dp[i][j+1]:
        dp[i][j+1] = tmp_ if tmp_ > dp[i][j+1] else dp[i][j+1]
        flag_ = True
    if i + j == N - 1:
        return
    if flag:
        rec(i + 1, j)
    if flag_:
        rec(i, j + 1)
    
N = int(input())
A = sorted([(int(j),i) for i, j in enumerate(input().split())])[::-1]

dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
rec(0, 0)
ans = -1
for i in range(N):
    for j in range(N):
        if dp[i][j] > ans:
            ans = dp[i][j]
print(ans)