← 返回题目列表

AtCoder · cpsco2019_s1_g

G. 除法游戏

中文机器翻译题面 查看原题

配点 : 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