No.972 選び方のスコア

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 84
作問者 : 沙耶花沙耶花 / テスター : shibh308shibh308
23 ProblemId : 3635 / 出題時の順位表
問題文最終更新日: 2020-01-18 00:11:19

問題文

$N$個の要素からなる正整数列 $a_1,...,a_N$ から $k$ 個( $k \ge 1$ )の要素を選び $b_1,...,b_k$ としたとき,
あなたが得られるスコア $S$ は $k$ 個の要素の中央値 $m$ (後述)を用いて次のように表されます.
\[ S = \sum_{i=1}^{k} (b_i - m) \] $S$の最大値を求めてください.
なお,答えは必ず整数となることが示せます.整数として出力してください.

※ $k$ 個の数の中央値 $m$ は,これを昇順に並べた数列を $x_1,...,x_k$ としたとき,次のように表されます. \[ m = \begin{cases} \ x_{\frac{k+1}{2}} \ (kが奇数) \\ \ \frac{1}{2} \times (x_{\frac{k}{2}} + x_{\frac{k}{2} +1 }) \ (kが偶数) \end{cases} \]

入力

$N$
$a_1\ a_2\ ...\ a_N$

  • $1 \le N \le 2\times 10^5$
  • $1 \le a_i \le 10^9 $
  • 入力はすべて整数

出力

答えを出力してください.
最後に改行してください.

サンプル

サンプル1
入力
5
1 2 3 4 5
出力
2

$b=\{1,2,5\}$のとき,スコアは$(1-2)+(2-2)+(5-2)=2$となります.これが最大値です.

サンプル2
入力
4
7 7 7 9
出力
2

すべての要素を選んだ場合,最大値を達成できます.

サンプル3
入力
10
3 8 9 7 2 2 10 10 35 5
出力
37

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