No.919 You Are A Project Manager

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 33
作問者 : ningenMeningenMe / テスター : aajisakaaajisaka
0 ProblemId : 3227 / 出題時の順位表

問題文

一列に並んだ$N$人のプログラマーがいます。左から$i$番目のプログラマーのやる気は$A_i$です。
まず正の数$K$を決めます。
次の操作を任意の回数繰り返して$K$人ずつのチームをいくつか作ります。

・プログラマーが$K$人以上残っているとき、左あるいは右の端から連続する$K$人のプログラマーを取り除く。この取り除いた$K$人を1つのチームとする。

ここで$K$は一度操作を始めた後変えることはできません。
1つのチームの行動力は$K$×(チーム内におけるプログラマーのやる気の中央値)となります。
やる気の中央値とは、チームのプログラマーのやる気を昇順にソートした列を$B_1,B_2, \dots\ B_K$とすると、$K$が偶数の時$B_{K/2}$、$K$が奇数の時$B_{(K+1)/2}$のことです。

適切に$K$を選び最適にチームを作った時の、行動力の総和の最大値を求めてください。
ただしチームを全く作らなかった時の行動力は$0$とします。

入力

$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$

入力は全て整数である
$1 \le N \le 10^4$
$-10^9 \le A_i \le 10^9 (1 \le i \le N)$

出力

最後に改行してください。

サンプル

サンプル1
入力
3
1 -1 2
出力
3

$K=1$のときに、左端のプログラマー$1$を選んだあと、右端のプログラマー$3$を選ぶことで最大値$\ 1×1+1×2=3\ $を達成します。

サンプル2
入力
10
-1 2 -3 4 -5 6 -7 8 -9 10
出力
33

$K=3$のときに、左端から3人、右端から3人、左端から3人選ぶことで最大値を達成します。

サンプル3
入力
20
2 3 4 5 -120 -6 7 8 9 11 38 -21 34 22 2 11 10 -90 -20 -10
出力
165

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。