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: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
sys.setrecursionlimit(10**8)
INF = float("inf")
MOD = 10**9+7

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


AA = [(a, i) for i, a in enumerate(A, start=1)]
AA.sort(reverse=True)
# print(AA)

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

for wa in range(1, N+1):
    # AA[:wa]までを考える
    for x in range(wa+1):
        y = wa - x
        a, i = AA[wa-1]
        if x - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x-1][y]+a*(i-x))
        if y - 1 >= 0:
            DP[x][y] = max(DP[x][y], DP[x][y-1]+a*(N-y-i+1))
        # print(wa, (x, y), (a, i), DP[x][y])

M = -INF
for x in range(N):
    y = N-x
    M = max(DP[x][y], M)
print(M)

Submission status: Accepted

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

# 添字のリスト
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] = 位置jから幅iの区間に小さい方からi個を配置したときの最大うれしさ
dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),
                    dp[j + 1] + a[p[i]] * abs(p[i] - j))

print(dp[0])

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
A = sorted([(a,i) for i,a in enumerate(A)],reverse=True)
dp=[[0]*(n+1) for i in range(n+1)]

# i+j=n
for i in range(n):
    for j in range(n-i):
        a,k=A[i+j]
        dp[i+1][j]=max(dp[i+1][j], dp[i][j]+abs(k-i)*a)
        dp[i][j+1]=max(dp[i][j+1], dp[i][j]+abs((n-j-1)-k)*a)

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

Submission status: Accepted

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

A = sorted([(val, pos) for pos, val in enumerate(A)], reverse=True)

dp = [0]
for i, (val, pos) in enumerate(A):
    ldp = [e + val * abs(pos - (i - r)) for r, e in enumerate(dp)]
    rdp = [e + val * abs(N - 1 - r - pos) for r, e in enumerate(dp)]
    dp = [max(L, R) for L, R in zip(ldp + [0], [0] + rdp)]

print(max(dp))

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
iA = [(i, A[i]) for i in range(N)]
iA.sort(key=lambda t: t[1], reverse=True)
dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):
    for j in range(N):
        if i+j<N:
            idx, v = iA[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]+v*abs(idx-i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]+v*abs(N-1-j-idx))

ans = 0

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

print(ans)

Submission status: Accepted

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(n+1):
        for y in range(n+1-x):
            if x == y == 0:
                continue
            ai, i = aii[n-x-y]
            dp[x][y] = max(dp[x-1][y] + ai * (i-x+1) if x > 0 else 0,
                           dp[x][y-1] + ai * (n-y-i) if y > 0 else 0)

    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: Accepted

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] = dp[x-1][0] + ai * (i-x+1)
        dp[0][x] = dp[0][x-1] + 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: Accepted

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

B = sorted(A, reverse=True)

C = [0] * N

i = 0
while(1):
    if i >= N:
        break
    for j in range(N):
        if A[j] == B[i]:
            C[i] = j
            if i != N-1 and B[i] == B[i+1]:
                i += 1
    i += 1

dp = [[0] * (N+1) for i in range(N+1)]
for i in range(N+1):
    for j in range(i+1):
        if j > 0 and i-j > 0:
            dp[j][i-j] = max([dp[j-1][i-j] + B[i-1] * abs(C[i-1] - (j-1)), dp[j][i-j-1] + B[i-1] * abs(C[i-1] - (N-1-(i-j-1)))])
        elif j == 0 and i-j > 0:
            dp[j][i-j] = dp[j][i-j-1] + B[i-1] * abs(C[i-1] - (N-1-(i-j-1)))
        elif i-j == 0 and j > 0:
            dp[j][i-j] = dp[j-1][i-j] + B[i-1] * abs(C[i-1] - (j-1))


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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

babies = sorted([(activity, index) for index, activity in enumerate(A, 1)], reverse=True)

DP = np.zeros(n+1, dtype=np.int64)
position = np.arange(1, n+1, dtype=np.int64)

for filled, (activity, index) in enumerate(babies, 1):
    to_left = DP[:filled] + abs((position[:filled]-index)*activity)
    to_right = DP[:filled] + abs((position[-filled:]-index)*activity)
    DP[1:filled+1] = np.maximum(DP[1:filled+1], to_left)
    DP[:filled] = np.maximum(DP[:filled], to_right)

print(DP.max())

Submission status: Accepted

Solution code:
#python3ではTLE
#input
N = int(input())
A = list(map(int, input().split()))

#output
B = [(i, a) for i, a in enumerate(A)]
B = sorted(B, key = lambda x:x[1], reverse = True)

dp = [[0] * (N+1) for i in range(N+1)]
#dp[i, j]を左i, 右jまで場所が決まった状態の最大値とする。
#i+j = Nとなる場合の最大値が答えとなる。

answer = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + B[i][1]*(abs(B[i][0]-i))
    for j in range(N):
        dp[0][j+1] = dp[0][j] + B[j][1]*(abs(N-1-B[j][0]-j))
        if i+j+1 < N:
            dp[i+1][j+1] = max(dp[i][j+1]+B[i+j+1][1]*(abs(B[i+j+1][0]-i)), dp[i+1][j] + B[i+j+1][1]*(abs(N-1-B[i+j+1][0]-j)))
    answer = max(answer, dp[i][N-i])

print(answer)

Submission status: Accepted

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

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

li = []
for i in range(n):
    li.append((a[i],i))

li.sort(reverse = True)

for i in range(1,n+1):
    tmp = li[i-1]
    for ii in range(i+1):
        jj = i - ii
        if ii == 0:
            dp[ii][jj] = dp[ii][jj-1] + tmp[0] * abs((n - jj) - tmp[1])
        elif jj == 0:
            dp[ii][jj] = dp[ii-1][jj] + tmp[0] * abs((ii - 1) - tmp[1])
        else:
            dp[ii][jj] = max(dp[ii][jj-1] + tmp[0] * abs((n - jj) - tmp[1]), dp[ii-1][jj] + tmp[0] * abs((ii - 1)- tmp[1]))


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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [(int(j), i) for i, j in enumerate(input().split())]
a.sort(reverse=1)
dp = [[0] * (n+1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(i + 1):
        k = i - j
        if j != 0:
            dp[i][j] = dp[i - 1][j - 1] + a[i-1][0] * (abs(j - 1 - a[i-1][1]))
        if k != 0:
            dp[i][j] = max(dp[i][j],
                           dp[i - 1][j] + a[i-1][0] * (abs(n-k - a[i-1][1])))
print(max(dp[-1]))

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x,out=dp[time+1][:-1])
    print(np.max(dp[n]))
main()

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n=int(input())
    a=list(enumerate(map(int,input().split())))
    a.sort(key=lambda x: -x[1])
    dp=[np.zeros(i+1,dtype=np.int64) for i in range(n+1)]
    dp[0]=np.zeros(1,dtype=np.int64)
    r=np.arange(n+1,dtype=np.int64)
    for time,ix in enumerate(a):
        i,x=ix
        dp[time+1][1:]=dp[time][:time+1]+(i-r[:time+1])*x
        dp[time+1][:-1]=np.maximum(dp[time+1][:-1],dp[time]+((n-1-(time-r[:time+1]))-i)*x)
    print(np.max(dp[n]))
main()

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
_A = sorted(enumerate(map(int, input().split()), 1), key=lambda x:x[1], reverse=True)
dp = [[0] * (N+1) for i in range(N+1)]

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (N-i-k) < 0:break
    dp[0][i] = dp[0][i-1] + (N-i+1-k) * Ak

for i in range(1,N+1):
    k, Ak = _A[i-1]
    if (k-i) < 0:break
    dp[i][0] = dp[i-1][0] + (k-i) * Ak

for x in range(1, N+1):
    for y in range(1, N-x+1):
        k, val = _A[x+y-1]
        dp[x][y]= max(dp[x-1][y] + abs(k-x)*val,
                      dp[x][y-1] + abs(N-y-k+1) * val)

print(int(max(dp[i][N-i] for i in range(N+1))))

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    A=list(map(int,input().split()))
    AA=[(v,i) for i,v in enumerate(A)]
    AA.sort(reverse=True)
    dp=[[0]*(N+1) for _ in range(N+1)]
    for len in range(1,N+1):
        val,index=AA[len-1]
        for x in range(0,len+1):
            y=len-x
            if x==0:
                dp[x][y]=dp[x][y-1]+val*abs(N-y-index)
            elif y==0:
                dp[x][y]=dp[x-1][y]+val*abs(index-x+1)
            else:
                dp[x][y]=max(dp[x][y-1]+val*abs(N-y-index),dp[x-1][y]+val*abs(index-x+1))
    maxes=[]
    for i in dp:
        maxes.append(max(i))
    return max(maxes)
print(main())

Submission status: Accepted

Solution code:
n=int(input())
a=map(int,input().split())
p=[(x,i) for i,x in enumerate(a)]
p.sort(reverse=True)

ans=0
dp=[[0]*(n+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(n+1):
    if i+j==n:
      ans=max(ans,dp[i][j])
      break
    act,ind=p[i+j]
    dp[i+1][j]=max(dp[i+1][j],
                   dp[i][j]+act*abs(ind-i))
    dp[i][j+1]=max(dp[i][j+1],
                   dp[i][j]+act*abs(n-1-j-ind))

print(ans)

Submission status: Accepted

Solution code:
'''
着想：大きいaほど左右の端に移動したい、小さいaを先に端にやるより必ず大きくなるから
問題：単純に貪欲に大きいaから左端(x-1)と右端(N-x)の大きい方に移動すると、
      残りのaの組み合わせ的に最適でない場合がある
      アイテムの左右端の単純な割り振りはO(2^N)
解決策の着想：大きい順のk個を(k=L+R)となる
    　　左L個右R個にどのように割り振っても(k+1)個目の最適な割り振り方は変わらない
解決策：アイテムk個左右に割り振る状態をdp[L][R]で保存O(N^2)
'''

def solve():
  N = int(input())
  A = [[a, i] for a,i in zip(map(int, input().split()), range(N))]
  A.sort(key=lambda a: a[0], reverse=True)

  dp = [[0]*(N+1) for _ in range(N+1)] # 左からxマス右からyマス埋める
  for i in range(0,N):
    a, l = A[i]
    for x in range(0,i+1):
      y = i - x # 合計x+y=iマス既に埋まっている、次にi+1マス目を考える
      dp[x+1][y] = max(dp[x+1][y], dp[x][y] + a * abs(l - x))
      dp[x][y+1] = max(dp[x][y+1], dp[x][y] + a * abs(l - (N-y-1)))

  print(max(dp[N-i][i] for i in range(N+1)))
  
solve()

Submission status: Accepted

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

N = I()
a = IL()
b = []
for i in range(N):
  b.append((a[i], i))
b.sort(reverse=True)

dp = [[0]*(N+1) for i in range(N+1)] # dp[i番目まで][左からj番目]

for i in range(N):
  happy, ID = b[i]
  #print(b[i])
  for l in range(i+1):
    lcnt = l
    rcnt = i - lcnt
    r = N-1 - rcnt
    if i > l-1:
      dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + happy*abs(ID - l))
      dp[i+1][l] = max(dp[i+1][l], dp[i][l] + happy*abs(ID - r))
    else:
      break
    #print(l,r)
    #print(dp)
  #print("---")
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from collections import defaultdict

#dpa[(0,0)] = 0

n = int(input())

a = list(map(int, input().split()))

d = {}
for i in range(n):
	d[i] = a[i]

dp = defaultdict(lambda: 0)

i = 0
x = 0
y = 0
maxr = 0
for k,v in sorted(d.items(), key=lambda x: -x[1]):
	i+=1
#	print(k,": ",v)
	for j in range(i+1):
		if j == 0:
			migi = 0
		else:
			migi = abs(n - j - k)*v
		
		if i - j == 0:
			hida = 0
		else:
			hida = abs(k - (i - j)+1)*v
		dp[(j,i-j)] = max(dp[(j-1,i-j)]+migi,dp[(j,i-j-1)]+hida)
		
		if i == n:
			maxr = max(maxr,dp[(j,i-j)])
#		print(j,i-j,k,hida,migi,dp[(j,i-j)])

print(maxr)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int], nb: int) -> int:
    s_values = sorted(((v, i) for i, v in enumerate(values)), reverse=True)
    dp = [[0 for _ in range(nb + 1)] for _ in range(nb + 1)]
    for i, (v, p) in enumerate(s_values, start=1):
        for x in range(i + 1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x - 1][0] + abs(p - x + 1) * v
                continue
            if x == 0:
                dp[x][y] = dp[x][y - 1] + abs(nb - y - p) * v
                continue
            dp[x][y] = max(
                dp[x - 1][y] + abs(p - x + 1) * v, dp[x][y - 1] + abs(nb - y - p) * v
            )
    return max(dp[i][nb - i] for i in range(nb + 1))


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(int, input().split()))
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values, N)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log(log_file: Optional[str] = None) -> None:
    "Configure the log output"
    log_formatter = logging.Formatter(
        "%(asctime)s - %(filename)s:%(lineno)d - " "%(levelname)s - %(message)s"
    )
    if log_file:
        handler = logging.FileHandler(filename=log_file)
    else:
        handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

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

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]#左、右から何人いるか dpはl,r埋まってるときの最大スコア 家庭菜園
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[l+1][r],dp[l][r]+abs(ind-l)*activeness)#左を埋める
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)#右を埋める

print(ans)

Submission status: Accepted

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

babies=[(a,i) for i,a in enumerate(a)]
babies.sort(reverse=True)

dp=[[0]*(n+1) for i in range(n+1)]#左、右から何人いるか? 家庭菜園
ans=0
for l in range(n):
    for r in range(n):
        if l+r==n:
            ans=max(ans,dp[l][r])
            break
        activeness,ind=babies[r+l]
        dp[l+1][r]=max(dp[r+1][r],dp[l][r]+abs(ind-l)*activeness)
        dp[l][r+1]=max(dp[l][r+1],dp[l][r]+abs(ind-(n-1-r))*activeness)

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(v, i) for i, v in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i, (a, b) in enumerate(AA, start=1):
        for x in range(i+1):
            y = i - x
            if y == 0:
                dp[x][y] = dp[x-1][y] + abs(b - x+1) * a
            elif x == 0:
                dp[x][y] = dp[x][y-1] + abs(N-y-b) * a
            else:
                dp[x][y] = max(dp[x-1][y] + abs(b - x + 1) * a, dp[x][y-1] + abs(N-y-b) * a)
    r = 0
    for i in range(N+1):
        r = max(r, dp[i][N-i])
    return r
print(main())

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
place = [0]*n
active = sorted(a,reverse=True)
for i in range(n):
    place[i] = a.index(active[i])
    a[a.index(active[i])] = -1

#dp[x][y] x,y:0~n+1 (x[-1]=x[n+1]=0にすることで端の処理を楽にする)
dp = [[0 for i in range(n+2)]for j in range(n+2)]

for i in range(n):
    dp[0][i+1] = dp[0][i]+active[i]*abs(n-i-1-place[i])
    dp[i+1][0] = dp[i][0]+active[i]*abs(place[i]-i)



def check(mat):
    for i in range(len(mat)):
        print(mat[i])
    print("\n")


for i in range(n):
    for x in range(i+2):
        y = i+1 - x
        if x != 0 and y != 0:
            dp[x][y] = max(dp[x-1][y]+active[i]*abs(place[i]-x+1),dp[x][y-1]+active[i]*abs(n-y-place[i]))
            if i == n-1:
                ans = max(ans,dp[x][y])

print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    AA = [(a, i) for i, a in enumerate(A)]
    AA.sort(reverse=True)
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        a, t = AA[i]
        for x in range(i + 2):
            y = i + 1 - x
            dp[x][y] = max((dp[x - 1][y] + abs(t - (x - 1)) * a) if x > 0 else 0,
                           (dp[x][y - 1] + abs(t - (N - y)) * a) if y > 0 else 0)
    return max(dp[i][N - i] for i in range(N + 1))

print(main())

Submission status: Accepted

Solution code:

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = sorted([(j, i) for i, j in enumerate(a)])[::-1]
    dp = [0]
    for i in range(n):
        dp2 = [0]*(i+2)
        A, p = a[i]
        for j in range(i+1):
            right = n-i-1+j
            dp2[j] = max(dp2[j], dp[j]+abs(p-right)*A)
            dp2[j+1] = max(dp2[j+1], dp[j]+abs(p-j)*A)
        dp = dp2
    print(max(dp2))


main()

Submission status: Accepted

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

infants = []
for i,a in enumerate(A):
    infants.append((a, i))
infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
#  from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in range(n)]
ab = [(x,y) for x,y in zip(a,b)]
from operator import itemgetter
ab = tuple(sorted(ab,key=itemgetter(0),reverse=True))
dp = [[-10**14]*(n+1) for i in range(n+1)]
dp[0][0] = 0
for i in range(n):
  for j in range(i+2):
    dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
print(max(dp[n]))

Submission status: Accepted

Solution code:
def main():  
  import sys
  input = sys.stdin.readline
  n = int(input())
  a = [int(i) for i in input().split()]
  b = [int(i) for i in range(n)]
  ab = [(x,y) for x,y in zip(a,b)]
  from operator import itemgetter
  ab = sorted(ab,key=itemgetter(0),reverse=True)
  dp = [[-10**14]*(n+1) for i in range(n+1)]
  dp[0][0] = 0
  for i in range(n):
    for j in range(i+2):
      if j >= 1:
        dp[i+1][j] = max(dp[i][j]+ab[i][0]*abs(ab[i][1]-(n-1-(i-j))),dp[i][j-1]+ab[i][0]*abs(ab[i][1]+1-j))
      if j == 0:
        dp[i+1][0] = dp[i][0] + ab[i][0]*abs(ab[i][1]-(n-1-i))
  print(max(dp[n]))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,*a = map(int,open(0).read().split())
a = sorted([(j,i) for i,j in enumerate(a)],reverse=True)
dp = [0]
for i,(j,k) in enumerate(a):
  ldp =  [abs(k-i+a)*j+b for a,b in enumerate(dp)]
  rdp =  [abs(n-1-k-a)*j+b for a,b in enumerate(dp)]
  dp = [max(a,b) for a,b in zip(ldp+[0],[0]+rdp)]
print(max(dp))

Submission status: Accepted

Solution code:
#!python3

# input
N = int(input())
A = list(map(int, input().split()))
# N = 2000
# A = [i for i in range(1, N + 1)]


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        x, y = p
        for i in range(n):
            j = n - 1 - i
            left = dp[i][j] + x * abs(y - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            right = dp[i][j] + x * abs(y - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
N = int(input())
As = [(x, i) for i, x in enumerate(map(int, input().split()))]

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

for i, (u, idx) in enumerate(up[::-1], 1):
    for j in range(i):
        left = j
        right = N-(i-j)
        dp[i][j] = max(dp[i][j], dp[i-1][j]+u*abs(right-idx))
        dp[i][j+1] = max(dp[i][j+1], dp[i-1][j]+u*abs(left-idx))

print(max(dp[-1]))

Submission status: Accepted

Solution code:
"""
AtCoder Beginner Contest 163  E

・大きいものほど移動距離を増やしたいので、端にもっていく
を真っ先に思いつくので、大きいものから移動距離が大きくなるように配置すると、例２が答えと一致しない。
手を動かしてみると、
・大きいものから端にもっていく
は正しいそうだが、
・移動距離が最も大きくなるように
が当てはまらないことが見えてくる。

大きいものからi人目まで並べるときに、左側にx人配置されているなら、残りのi-x人が右側に配置されている。
・一人目は左右の端のいずれかに配置されうる
・二人目は、左端、その右隣、右端、その左隣、に配置されうる
・n人目は、左端からn番目まで、右端からn番目までの場所に配置されうる
このような感じで、左にx人、右にy人配置されている場合のうれしさの最大値を求めていって、最終的にx+y=Nになるようなdp[x][y]の最大値を求めるとよい

# ~~ 以下考察時 ~~
・大きいものから
・左右の端のどっちかに持っていく

のがいいっぽい


556111の例について、

大きい順から6を左右に振った場合
次に大きい5について、↑でできた2パターンかにおいて左右のどっちかに振った場合、
次に大きい5について、↑でできた4パターンかにおいて左右のどっちかに振った場合、
・・・

みたいな形でやるのがいいか？
2*2*2*2*... みたいな形で増えていかないか？
→NO。最初の6は左右の端のどちらか。次の5が左右から二つ分のいずれか。...。最後の1が左端〜右端で全ての場所に当てうるので、計算量的にはN**2ですむ
 N <= 2000 なので、十分間に合う

 ・例えば上の例で6について左右の端のいずれかにせず、全ての場所を試してもいいのでは？
 →恥に持っていくのが一番点が増えるので意味なし。のちの操作も煩雑になる＆分岐がややこしいのよろしくない。
"""



N = int(input())
A = list(map(int, input().split()))
infants = []
for i,a in enumerate(A):
    infants.append((a, i))

infants.sort(reverse=True)
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]


# i番目の幼児まで見るとき
for i in range(N):
    """
    i番目の幼児を配置する方法として、
    ・左側の１～i番目として配置
    ・右側の１～i番目として配置
    の方法がある
    
    左のj人目として配置した場合、右にはi-j人配置されていることになる（右も同じ）
    例：５番目を左の二人目として配置したら、右には残りの３人がいる計算になる

    """
    for j in range(i+1):

        # 左側に配置したとき
        dp[j+1][i-j] =    max(dp[j+1][i-j], dp[j][i-j] + infants[i][0] * abs(infants[i][1] - j))
            
        # 右側に配置したとき
        dp[i-j][j+1] = max(dp[i-j][j+1], dp[i-j][j] + infants[i][0] * abs(infants[i][1] - (N-1 - j)))


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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
infants = []
for i in range(n):
    infants.append((a[i],i))
infants.sort()
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
    score,initial = infants.pop()
    for right in dp[i].keys():
        dp[i+1][right] = max(dp[i][right]+abs(initial-(i-right))*score,dp[i+1][right])
        dp[i+1][right+1] = max(dp[i][right]+abs((n-1-right)-initial)*score,dp[i+1][right+1])
print(max(dp[n].values()))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from math import inf

import numpy as np


n = int(input())
A = []
[heappush(A, (-v, i)) for i, v in enumerate(map(int, input().split()), 1)]
dp = np.full((n + 1, n + 1), -inf, dtype=int)
dp[0, 0] = 0

for i in range(n):
    v, j = heappop(A)
    v = -v
    dp[i + 1, 1:] = dp[i, :-1] + v * np.abs(j - np.arange(1, n + 1))
    dp[i + 1, :-1] = np.maximum(dp[i, :-1] + v * np.abs(j - np.arange(n - i, n + n - i)), dp[i + 1, :-1])

print(dp[-1,].max())

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
l=[]
for i,x in enumerate(a):
    l.append([x,i])
l.sort(reverse=True)
cnt=1
dp=[[0]*(n+1) for _ in range(n+1)]
for i,j in l:
    for x in range(cnt+1):
        if x==0:
            dp[x][cnt-x]=dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j)
        elif x==cnt:
            dp[x][cnt-x]=dp[x-1][cnt-x]+i*(j-x+1)
        else:
            dp[x][cnt-x]=max(dp[x-1][cnt-x]+i*(j-x+1),dp[x][cnt-x-1]+i*(n-1-(cnt-x-1)-j))
    cnt+=1
ans=0
for i in range(n+1):
    ans=max(ans,dp[i][n-i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 9
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353

n = I()
A = LI()
S = sorted([(A[k], k + 1) for k in range(n)], reverse=True)
ans = 0
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(n):
        if i and i <= S[i + j - 1][1]:
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + S[i + j - 1][0] * abs(i - S[i + j - 1][1]))
        if j and S[i + j - 1][1] <= n - j + 1:
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + S[i + j - 1][0] * abs(n - j + 1 - S[i + j - 1][1]))
        if i + j == n:
            ans = max(ans, dp[i][j])
            break

print(ans)