← 返回题目列表

AtCoder · abc163_e

E. 活跃的婴儿

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

有 N 孩子们从左到右站成一排。的活跃度 i左边第一个孩子是 A_i.

您可以按照您喜欢的任何顺序重新排列这些子项一次。

当一个孩子最初占据 x行中从左边算起的第一个位置移动到 y从左边数第 - 个位置,该孩子获得 A_x \times |x-y| 幸福点。

找出孩子们可以获得的最大总幸福分。

约束

  • 2 \leq N \leq 2000
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 ... A_N

输出

打印孩子们可以获得的最大总幸福分。


示例输入 1

4
1 3 4 2

示例输出 1

20

如果我们移动 1-从左到右的第一个孩子 3- 从左边数第一个位置, 2- 第一个孩子 4- 第一个位置, 3-rd 孩子到 1-st 位置,以及 4第一个孩子 2-nd位置,孩子们赚到 1 \times |1-3|+3 \times |2-4|+4 \times |3-1|+2 \times |4-2|=20 幸福点数总计。


示例输入 2

6
5 5 6 1 1 1

示例输出 2

58

示例输入 3

6
8 6 9 1 2 1

示例输出 3

85