問題一覧 > 通常問題

No.1564 Sum of Products of Pairs

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

問題文

2N 個の正整数からなる数列 A={A1,A2,,A2N} が与えられます。

A1 回だけ好きな順番に並び替えかえて数列 B を構成するとき、 k=1NB2k1B2k の最大値を求めてください。

入力

N
A1 A2 A3  A2N

  • 入力は全て整数である。
  • 1N105
  • 1Ai105

出力

k=1NB2k1B2k の最大値を出力してください。最後に改行してください。

サンプル

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

例えば B={A1, A3, A2, A4, A5, A6} とすると、 k=1NB2k1B2k=5×4+3×2+4×3=38 となります。これより値が大きくなるような B の構成方法は存在しないことが示せるため、38 を出力します。

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

最大値は 2×2=4 となります。

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

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