No.2488 Mod Sum Maximization
タグ : / 解いたユーザー数 21
作問者 :
shiomusubi496
/ テスター :
Problem Statement
You are given a sequence of positive integers $A=(A_1, A_2, \ldots, A_N)$ of length $N$. Here, it is guaranteed that all elements are distinct.
You may freely rearrange $A$ to form a sequence $B=(B_1, B_2, \ldots, B_N)$. Here, the score of the sequence $B$ is defined as follows.
$\displaystyle\sum_{i=1}^N \left(B_i \bmod B_{i+1}\right)$
Here, $x \bmod y$ denotes the remainder when $x$ is divided by $y$, and $B_{N+1}$ denotes $B_1$.
Find the maximum possible score when $B$ is rearranged appropriately.
Input
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
- $2 \leq N \leq 3 \times 10^5$
- $1 \leq A_1 < A_2 < \cdots < A_N \leq 10^6$
- All inputs are integers.
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
3
For example, when $B=(1, 2, 3)$, the score is as follows.
$(B_1 \bmod B_2) + (B_2 \bmod B_3) + (B_3 \bmod B_1) = (1 \bmod 2) + (2 \bmod 3) + (3 \bmod 1) = 1 + 2 + 0 = 3$
The score cannot be made $4$ or greater, so print $3$.
Sample 2
Input
3 3 5 9
Output
9
For example, when $B=(9, 5, 3)$, the score is as follows.
$(B_1 \bmod B_2) + (B_2 \bmod B_3) + (B_3 \bmod B_1) = (9 \bmod 5) + (5 \bmod 3) + (3 \bmod 9) = 4 + 2 + 3 = 9$
The score cannot be made $10$ or greater, so print $9$.
Sample 3
Input
10 12985 24371 98519 119747 180021 188891 211609 241216 248205 263054
Output
1331923
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。