No.2458 Line Up Charged Balls
タグ : / 解いたユーザー数 30
作問者 :
srjywrdnprkt
/ テスター :
👑 
Nachia
問題文
直線上に $N$ 個のボールが並べられています。左から $i$ 番目のボールは電荷 $Q_i$ を帯びています。
隣り合うボール $(i, i+1)$ 間には相互作用エネルギー $Q_iQ_{i+1}$ が働きます。
あなたは直線上から好きなボールを $1$ つ選んで取り除く操作を $N-2$ 回まで行うことができます。
これにより、直線上のボールが $K$ 個、各ボールの電荷が左から順に $(q_1, \cdots, q_K)$ となるとき、 全体のエネルギーは相互作用エネルギーの総和として $$ E=\sum_{i=1}^{K-1} q_i q_{i+1} $$ のように与えられます。適切にボールを取り除いたときの全体のエネルギー $E$ の最大値を求めてください。
入力
$N$ $Q_1\ \cdots\ Q_N$
入力は全て整数で以下の制約を満たす。
- $3 \leq N \leq 3\times10^5$
- $|Q_i| \leq 10^5$
出力
適切にボールを取り除いたときの全体のエネルギー $E$ の最大値を出力してください。最後に改行してください。
サンプル
サンプル1
入力
6 3 2 -2 5 -1 -6
出力
17
$3$ 番目のボールを直線上から取り除きます。すると、ボールの電荷は左から順に $(3,2,5,-1,-6)$ となるので、$E=3\times 2 + 2\times 5 + 5 \times (-1) + (-1) \times (-6) = 17$となります。 $E$ を $17$ 以上にすることはできないので、 $17$ が答えです。
サンプル2
入力
6 3 2 -2 5 -4 -6
出力
34
$4$ 番目のボールを取り除くのが最適です。
サンプル3
入力
3 100000 100000 100000
出力
20000000000
$1$ つもボールを取り除かないのが最適です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。