問題一覧 > 通常問題

No.2458 Line Up Charged Balls

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 32
作問者 : srjywrdnprkt / テスター : 👑 Nachia
お気に入りにしたユーザー ProblemId : 9992 / 自分の提出
問題文最終更新日: 2023-09-01 22:04:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 403 (順位表) の他の問題:

Problem Statement

$N$ balls are arranged on a line. The $i$-th ball from the left carries a charge $Q_i$.

Between each pair of adjacent balls $(i, i+1)$, there is an interaction energy $Q_iQ_{i+1}$.

You may perform the operation of choosing any $1$ ball and removing it from the line up to $N-2$ times.

When, as a result, there are $K$ balls on the line and their charges are $(q_1, \cdots, q_K)$ in order from the left, the total energy is given as the sum of the interaction energies: $$ E=\sum_{i=1}^{K-1} q_i q_{i+1} $$

Find the maximum value of the total energy $E$ when the balls are removed appropriately.

Input

$N$
$Q_1\ \cdots\ Q_N$

All inputs are integers and satisfy the following constraints.

  • $3 \leq N \leq 3\times10^5$
  • $|Q_i| \leq 10^5$

Output

Output the maximum value of the total energy $E$ when the balls are removed appropriately. Print a newline at the end.

Sample

Sample 1
Input
6
3 2 -2 5 -1 -6
Output
17

Remove the $3$-rd ball from the line. The charges of the balls are then $(3,2,5,-1,-6)$ in order from the left, so $E=3\times 2 + 2\times 5 + 5 \times (-1) + (-1) \times (-6) = 17$. Since $E$ cannot be made $17$ or greater, $17$ is the answer.

Sample 2
Input
6
3 2 -2 5 -4 -6
Output
34

It is optimal to remove the $4$-th ball.

Sample 3
Input
3
100000 100000 100000
Output
20000000000

It is optimal not to remove even $1$ ball.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。