No.1564 Sum of Products of Pairs
タグ : / 解いたユーザー数 155
作問者 :
maguro
/ テスター :
PCTprobability
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もしくは右上の雲マークをクリックしてアカウントを作成してください。