問題一覧 > 通常問題

No.2488 Mod Sum Maximization

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : shiomusubi496 / テスター : Cyanmond ytqm3
5 ProblemId : 10198 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-09-29 20:57:37

問題文

長さ NN の正整数列 A=(A1,A2,…,AN)A=(A_1, A_2, \ldots, A_N) が与えられます。ここで、全ての要素が相異なることが保証されます。

あなたは AA を自由に並び替え、数列 B=(B1,B2,…,BN)B=(B_1, B_2, \ldots, B_N) を作ることができます。ここで、数列 BB のスコアを以下のように定めます。

∑i=1N(Bi mod Bi+1)\displaystyle\sum_{i=1}^N \left(B_i \bmod B_{i+1}\right)

ただしここで、 x mod yx \bmod y は xx を yy で割った余りを表し、 BN+1B_{N+1} は B1B_1 のことを表すものとします。

このとき、適切に BB を並び替えたときのスコアの最大値を求めて下さい。

入力

NN
A1A_1 A2A_2 …\ldots ANA_N
  • 2≤N≤3×1052 \leq N \leq 3 \times 10^5
  • 1≤A1<A2<⋯<AN≤1061 \leq A_1 < A_2 < \cdots < A_N \leq 10^6
  • 入力は全て整数

出力

最後に改行してください。

サンプル

サンプル1
入力
3
1 2 3
出力
3

例えば B=(1,2,3)B=(1, 2, 3) としたとき、スコアは以下のようになります。

(B1 mod B2)+(B2 mod B3)+(B3 mod B1)=(1 mod 2)+(2 mod 3)+(3 mod 1)=1+2+0=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

スコアを 44 以上にすることはできないため、 33 を出力します。

サンプル2
入力
3
3 5 9
出力
9

例えば B=(9,5,3)B=(9, 5, 3) としたとき、スコアは以下のようになります。

(B1 mod B2)+(B2 mod B3)+(B3 mod B1)=(9 mod 5)+(5 mod 3)+(3 mod 9)=4+2+3=9(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

スコアを 1010 以上にすることはできないため、 99 を出力します。

サンプル3
入力
10
12985 24371 98519 119747 180021 188891 211609 241216 248205 263054
出力
1331923

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