問題はこちら。

しばらくわからなかったけどグッと眉間に皺を寄せて考えたら解けた。活発度が高い順から両端に詰めていくんだろうな～と思ってたんだけどその通りだった。N <= 2000なので区間DPが使えた。

import sys
readline = sys.stdin.readline


def main():
 N = int(readline())
 A = list(map(int, readline().split()))
 AI = [(a, i) for i, a in enumerate(A)]
 AI.sort(reverse=True)
 
 dp = [[0] * (N + 1) for _ in range(N + 1)]
 for l in range(N):
   for r in range(N, l, -1):
     a, i = AI[N - r + l]
     dp[l + 1][r] = max(dp[l + 1][r], dp[l][r] + abs(i - l) * a)
     dp[l][r - 1] = max(dp[l][r - 1], dp[l][r] + abs(i - r + 1) * a)
 print(max(dp[i][i] for i in range(N)))


if __name__ == '__main__':
 main()