問題一覧 > 通常問題

No.1564 Sum of Products of Pairs

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : maguromaguro / テスター : PCTprobabilityPCTprobability
1 ProblemId : 6336 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-06-26 13:28:15

問題文

$2N$ 個の正整数からなる数列 $A = \{A_1,A_2, \cdots , A_{2N}\}$ が与えられます。

$A$ を $1$ 回だけ好きな順番に並び替えかえて数列 $B$ を構成するとき、 $\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k}$ の最大値を求めてください。

入力

$N$
$A_1\ A_2\ A_3\ \cdots\ A_{2N}$

  • 入力は全て整数である。
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^5$

出力

$\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k}$ の最大値を出力してください。最後に改行してください。

サンプル

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

例えば $B = \{A_1,\ A_3,\ A_2,\ A_4,\ A_5,\ A_6\}$ とすると、 $\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k} = 5 \times 4 + 3 \times 2 + 4 \times 3 = 38$ となります。これより値が大きくなるような $B$ の構成方法は存在しないことが示せるため、$38$ を出力します。

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

最大値は $2 \times 2 = 4$ となります。

サンプル3
入力
3
3 1 4 1 5 9
出力
58

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