G - Game with Division
解説
/
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
やむなく君は 1 枚の紙と長さ N の整数列 A_1, A_2, \ldots, A_N を使った次のようなゲームを考えました。
まず紙に好きな正の整数を 1 つ書きます。その後 N 回の操作をします。 i 回目 (1\le i\le N) の操作では以下のどちらか 1 つを行います。
- その時点で紙に書かれている数字を X として、Y = \left \lfloor\frac{A_i}{X}\right \rfloor とする (\lfloor x \rfloor で x の整数部分を表します)。紙に書かれている数字を Y に書き換えて、Y 点を獲得する。 なおこの操作は X > A_i のときには行うことができない。
- 何もしない。得点も獲得できない。
やむなく君は N 回の操作で獲得する点数の合計を最大化したいです。
やむなく君が最初に紙に書く数字と N 回の操作を最適に行ったときに獲得できる点数を求めてください。
制約
- 1\le N\le 1000
- 1\le A_i\le 10^6
- 入力はすべて整数
部分点
この問題には部分点が設定されています。
- すべての i\ (1\le i\le N) について A_i\le 1000 を満たす入力に正解すると、300 点が与えられます。
入力
入力は以下の形式で標準入力から与えられます。
N A_1\ A_2\ \ldots\ A_N
出力
やむなく君の獲得できる点数の最大値を 1 行に出力してください。
入力例 1
3 3 6 9
出力例 1
10
- まず紙に 2 と書く。
- 1 回目の操作では紙の数字を \left \lfloor\frac{3}{2}\right \rfloor = 1 に書き換えて 1 点を獲得する。
- 2 回目の操作では何もしない。
- 3 回目の操作では紙の数字を \left \lfloor\frac{9}{1}\right \rfloor = 9 に書き換えて 9 点を獲得する。
このとき合計 10 点を獲得できて、これが最大です。なお、10 点を獲得する方法は他にもあります。
入力例 2
3 10 3 4
出力例 2
10
入力例 3
1 1000
出力例 3
1000
入力例 4
10 87 72 55 81 12 59 1 10 18 53
出力例 4
166