No.2488 Mod Sum Maximization
タグ : / 解いたユーザー数 23
作問者 :
shiomusubi496
/ テスター :
Cyanmond
ytqm3
問題文
長さ $N$ の正整数列 $A=(A_1, A_2, \ldots, A_N)$ が与えられます。ここで、全ての要素が相異なることが保証されます。
あなたは $A$ を自由に並び替え、数列 $B=(B_1, B_2, \ldots, B_N)$ を作ることができます。ここで、数列 $B$ のスコアを以下のように定めます。
$\displaystyle\sum_{i=1}^N \left(B_i \bmod B_{i+1}\right)$
ただしここで、 $x \bmod y$ は $x$ を $y$ で割った余りを表し、 $B_{N+1}$ は $B_1$ のことを表すものとします。
このとき、適切に $B$ を並び替えたときのスコアの最大値を求めて下さい。
入力
$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$
- 入力は全て整数
出力
最後に改行してください。
サンプル
サンプル1
入力
3 1 2 3
出力
3
例えば $B=(1, 2, 3)$ としたとき、スコアは以下のようになります。
$(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$
スコアを $4$ 以上にすることはできないため、 $3$ を出力します。
サンプル2
入力
3 3 5 9
出力
9
例えば $B=(9, 5, 3)$ としたとき、スコアは以下のようになります。
$(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$
スコアを $10$ 以上にすることはできないため、 $9$ を出力します。
サンプル3
入力
10 12985 24371 98519 119747 180021 188891 211609 241216 248205 263054
出力
1331923
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。