No.1564 Sum of Products of Pairs
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 140
作問者 :
maguro
/ テスター :
👑 
PCTprobability
タグ : / 解いたユーザー数 140
作問者 :
maguro
/ テスター :
👑 PCTprobability
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。