問題一覧 > 通常問題

No.2458 Line Up Charged Balls

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 30
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 NachiaNachia
0 ProblemId : 9992 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-01 22:04:55

問題文

直線上に NN 個のボールが並べられています。左から ii 番目のボールは電荷 QiQ_i を帯びています。

隣り合うボール (i,i+1)(i, i+1) 間には相互作用エネルギー QiQi+1Q_iQ_{i+1} が働きます。

あなたは直線上から好きなボールを 11 つ選んで取り除く操作を N2N-2 回まで行うことができます。

これにより、直線上のボールが KK 個、各ボールの電荷が左から順に (q1,,qK)(q_1, \cdots, q_K) となるとき、 全体のエネルギーは相互作用エネルギーの総和として E=i=1K1qiqi+1 E=\sum_{i=1}^{K-1} q_i q_{i+1} のように与えられます。

適切にボールを取り除いたときの全体のエネルギー EE の最大値を求めてください。

入力

NN
Q1  QNQ_1\ \cdots\ Q_N

入力は全て整数で以下の制約を満たす。

  • 3N3×1053 \leq N \leq 3\times10^5
  • Qi105|Q_i| \leq 10^5

出力

適切にボールを取り除いたときの全体のエネルギー EE の最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
6
3 2 -2 5 -1 -6
出力
17

33 番目のボールを直線上から取り除きます。すると、ボールの電荷は左から順に (3,2,5,1,6)(3,2,5,-1,-6) となるので、E=3×2+2×5+5×(1)+(1)×(6)=17E=3\times 2 + 2\times 5 + 5 \times (-1) + (-1) \times (-6) = 17となります。 EE1717 以上にすることはできないので、 1717 が答えです。

サンプル2
入力
6
3 2 -2 5 -4 -6
出力
34

44 番目のボールを取り除くのが最適です。

サンプル3
入力
3
100000 100000 100000
出力
20000000000

11 つもボールを取り除かないのが最適です。

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