F. Video Cards

Codeforces

IDCF731F

Time1000ms

Memory256MB

Difficulty—

brute forcedata structuresimplementationmathnumber theory

English · Original

Chinese · Translation

Formal · Original

Little Vlad is fond of popular computer game Bota-2. Recently, the developers announced the new add-on named Bota-3. Of course, Vlad immediately bought only to find out his computer is too old for the new game and needs to be updated. There are _n_ video cards in the shop, the power of the _i_\-th video card is equal to integer value _a__i_. As Vlad wants to be sure the new game will work he wants to buy not one, but several video cards and unite their powers using the cutting-edge technology. To use this technology one of the cards is chosen as the leading one and other video cards are attached to it as secondary. For this new technology to work it's required that the power of each of the secondary video cards is divisible by the power of the leading video card. In order to achieve that the power of any secondary video card can be reduced to any integer value less or equal than the current power. However, the power of the leading video card should remain unchanged, i.e. it **can't** be reduced. Vlad has an infinite amount of money so he can buy any set of video cards. Help him determine which video cards he should buy such that after picking the leading video card and may be reducing some powers of others to make them work together he will get the maximum total value of video power. ## Input The first line of the input contains a single integer _n_ (1 ≤ _n_ ≤ 200 000) — the number of video cards in the shop. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 200 000) — powers of video cards. ## Output The only line of the output should contain one integer value — the maximum possible total power of video cards working together. [samples] ## Note In the first sample, it would be optimal to buy video cards with powers 3, 15 and 9. The video card with power 3 should be chosen as the leading one and all other video cards will be compatible with it. Thus, the total power would be 3 + 15 + 9 = 27. If he buys all the video cards and pick the one with the power 2 as the leading, the powers of all other video cards should be reduced by 1, thus the total power would be 2 + 2 + 14 + 8 = 26, that is less than 27. Please note, that it's not allowed to reduce the power of the leading video card, i.e. one can't get the total power 3 + 1 + 15 + 9 = 28. In the second sample, the optimal answer is to buy all video cards and pick the one with the power 2 as the leading. The video card with the power 7 needs it power to be reduced down to 6. The total power would be 8 + 2 + 2 + 6 = 18.

小弗拉德喜欢流行的电脑游戏 Bota-2。最近，开发者宣布了名为 Bota-3 的新扩展包。当然，弗拉德立即购买了游戏，却发现他的电脑太旧，无法运行新游戏，需要升级。商店中有 #cf_span[n] 张显卡，第 #cf_span[i] 张显卡的性能为整数值 #cf_span[ai]。为了确保新游戏能正常运行，弗拉德希望购买不止一张显卡，并使用前沿技术将它们的性能整合在一起。使用这项技术时，需要选择一张显卡作为主卡，其余显卡作为从卡连接到它。为了使这项技术正常工作，每张从卡的性能必须能被主卡的性能整除。为实现这一点，任何从卡的性能可以被降低到不超过当前值的任意整数。然而，主卡的性能必须保持不变，即 *不能* 被降低。弗拉德拥有无限的资金，因此可以购买任意一组显卡。请帮助他确定应购买哪些显卡，使得在选定主卡并可能降低其他显卡的性能以使其兼容后，获得的显卡总性能最大。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 商店中显卡的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 200 000]) —— 显卡的性能。输出仅一行，包含一个整数 —— 显卡协同工作时可能达到的最大总性能。在第一个样例中，最优方案是购买性能为 #cf_span[3]、#cf_span[15] 和 #cf_span[9] 的显卡。选择性能为 #cf_span[3] 的显卡作为主卡，其余所有显卡均与之兼容。因此总性能为 #cf_span[3 + 15 + 9 = 27]。如果他购买所有显卡并选择性能为 #cf_span[2] 的显卡作为主卡，则其他所有显卡的性能需各减少 #cf_span[1]，此时总性能为 #cf_span[2 + 2 + 14 + 8 = 26]，小于 #cf_span[27]。请注意，不允许降低主卡的性能，因此无法得到总性能 #cf_span[3 + 1 + 15 + 9 = 28]。在第二个样例中，最优方案是购买所有显卡并选择性能为 #cf_span[2] 的显卡作为主卡。性能为 #cf_span[7] 的显卡需将其性能降低至 #cf_span[6]。总性能为 #cf_span[8 + 2 + 2 + 6 = 18]。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 商店中显卡的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[1 ≤ ai ≤ 200 000]) —— 显卡的性能。 ## Output 输出仅一行，包含一个整数 —— 显卡协同工作时可能达到的最大总性能。 [samples] ## Note 在第一个样例中，最优方案是购买性能为 #cf_span[3]、#cf_span[15] 和 #cf_span[9] 的显卡。选择性能为 #cf_span[3] 的显卡作为主卡，其余所有显卡均与之兼容。因此总性能为 #cf_span[3 + 15 + 9 = 27]。如果他购买所有显卡并选择性能为 #cf_span[2] 的显卡作为主卡，则其他所有显卡的性能需各减少 #cf_span[1]，此时总性能为 #cf_span[2 + 2 + 14 + 8 = 26]，小于 #cf_span[27]。请注意，不允许降低主卡的性能，因此无法得到总性能 #cf_span[3 + 1 + 15 + 9 = 28]。在第二个样例中，最优方案是购买所有显卡并选择性能为 #cf_span[2] 的显卡作为主卡。性能为 #cf_span[7] 的显卡需将其性能降低至 #cf_span[6]。总性能为 #cf_span[8 + 2 + 2 + 6 = 18]。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of video cards. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing the powers of the video cards. **Constraints** $ 1 \leq n \leq 200{,}000 $, $ 1 \leq a_i \leq 200{,}000 $ for all $ i \in \{1, \dots, n\} $. **Objective** Choose a non-empty subset $ S \subseteq A $ and a leading card $ l \in S $ such that for every $ x \in S \setminus \{l\} $, there exists an integer $ x' \leq x $ with $ l \mid x' $. Maximize the total power: $$ \max_{\substack{S \subseteq A \\ l \in S}} \left( l + \sum_{\substack{x \in S \\ x \ne l}} \max \{ x' \leq x : l \mid x' \} \right) $$ Equivalently, for a fixed leading card $ l $, the contribution of any card with power $ x $ is $ \left\lfloor \frac{x}{l} \right\rfloor \cdot l $, and the total power is: $$ \sum_{x \in S} \left\lfloor \frac{x}{l} \right\rfloor \cdot l $$ We seek: $$ \max_{l \in A} \left( \sum_{x \in A} \left\lfloor \frac{x}{l} \right\rfloor \cdot l \right) $$ (Note: Since we can choose any subset $ S \subseteq A $, and reducing powers is always beneficial, we include every card $ x \in A $, as $ \left\lfloor \frac{x}{l} \right\rfloor \cdot l \geq 0 $. Thus, the sum is over all $ x \in A $.) **Final Objective** $$ \max_{l \in A} \left( l \cdot \sum_{x \in A} \left\lfloor \frac{x}{l} \right\rfloor \right) $$

Samples

Input #1

4
3 2 15 9

Output #1

Input #2

4
8 2 2 7

Output #2

API Response (JSON)

{
  "problem": {
    "name": "F. Video Cards",
    "description": {
      "content": "Little Vlad is fond of popular computer game Bota-2. Recently, the developers announced the new add-on named Bota-3. Of course, Vlad immediately bought only to find out his computer is too old for the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF731F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Little Vlad is fond of popular computer game Bota-2. Recently, the developers announced the new add-on named Bota-3. Of course, Vlad immediately bought only to find out his computer is too old for the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "小弗拉德喜欢流行的电脑游戏 Bota-2。最近，开发者宣布了名为 Bota-3 的新扩展包。当然，弗拉德立即购买了游戏，却发现他的电脑太旧，无法运行新游戏，需要升级。\n\n商店中有 #cf_span[n] 张显卡，第 #cf_span[i] 张显卡的性能为整数值 #cf_span[ai]。为了确保新游戏能正常运行，弗拉德希望购买不止一张显卡，并使用前沿技术将它们的性能整合在一起。使用这项技术时，需要...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of video cards.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the powers of the video cards.\n\n**Constr...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments