No.2458 Line Up Charged Balls
タグ : / 解いたユーザー数 32
作問者 :
srjywrdnprkt
/ テスター :
👑
Nachia
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もしくは右上の雲マークをクリックしてアカウントを作成してください。