問題一覧 > 通常問題

No.2488 Mod Sum Maximization

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 21
作問者 : shiomusubi496 / テスター : Cyanmond ytqm3
お気に入りにしたユーザー ProblemId : 10198 / 自分の提出
問題文最終更新日: 2023-09-29 20:57:37
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
yukicoder contest 406 技術室奥プログラミングコンテスト#7 Day2 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。