問題一覧 > 通常問題

No.1564 Sum of Products of Pairs

レベル : / AI推定難易度 : 235 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 155
作問者 : maguro / テスター : PCTprobability
お気に入りにしたユーザー ProblemId : 6336 / 自分の提出
問題文最終更新日: 2021-06-26 13:28:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘校文化祭コンテスト 2021 day1 (順位表) の他の問題:

Problem Statement

You are given a sequence $A = \{A_1,A_2, \cdots , A_{2N}\}$ consisting of $2N$ positive integers.

You construct a sequence $B$ by rearranging $A$ in any order you like, exactly $1$ time. Find the maximum value of $\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k}$.

Input

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

  • All inputs are integers.
  • $1 \leq N \leq 10^5$
  • $1 \leq A_i \leq 10^5$

Output

Output the maximum value of $\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k}$. Print a newline at the end.

Sample

Sample 1
Input
3
5 3 4 2 4 3
Output
38

For example, if $B = \{A_1,\ A_3,\ A_2,\ A_4,\ A_5,\ A_6\}$, then $\displaystyle \sum_{k = 1}^{N} B_{2k - 1}B_{2k} = 5 \times 4 + 3 \times 2 + 4 \times 3 = 38$. It can be shown that there is no way to construct $B$ that gives a larger value, so output $38$.

Sample 2
Input
1
2 2
Output
4

The maximum value is $2 \times 2 = 4$.

Sample 3
Input
3
3 1 4 1 5 9
Output
58

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