B. Marvolo Gaunt's Ring

Codeforces

IDCF855B

Time2000ms

Memory256MB

Difficulty—

brute forcedata structuresdp

English · Original

Chinese · Translation

Formal · Original

Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although he destroyed it, he is still affected by its curse. Professor Snape is helping Dumbledore remove the curse. For this, he wants to give Dumbledore exactly _x_ drops of the potion he made. Value of _x_ is calculated as maximum of _p_·_a__i_ + _q_·_a__j_ + _r_·_a__k_ for given _p_, _q_, _r_ and array _a_1, _a_2, ... _a__n_ such that 1 ≤ _i_ ≤ _j_ ≤ _k_ ≤ _n_. Help Snape find the value of _x_. Do note that the value of _x_ may be negative. ## Input First line of input contains 4 integers _n_, _p_, _q_, _r_ ( - 109 ≤ _p_, _q_, _r_ ≤ 109, 1 ≤ _n_ ≤ 105). Next line of input contains _n_ space separated integers _a_1, _a_2, ... _a__n_ ( - 109 ≤ _a__i_ ≤ 109). ## Output Output a single integer the maximum value of _p_·_a__i_ + _q_·_a__j_ + _r_·_a__k_ that can be obtained provided 1 ≤ _i_ ≤ _j_ ≤ _k_ ≤ _n_. [samples] ## Note In the first sample case, we can take _i_ = _j_ = _k_ = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30. In second sample case, selecting _i_ = _j_ = 1 and _k_ = 5 gives the answer 12.

邓布利多教授正在帮助哈利摧毁魂器。他前往冈特小屋，怀疑那里藏有一个魂器。他看到了马沃洛·冈特的戒指，并确认其为魂器。尽管他摧毁了它，但仍受到其诅咒的影响。斯内普教授正帮助邓布利多消除诅咒。为此，他需要给邓布利多恰好 #cf_span[x] 滴他配制的药水。 #cf_span[x] 的值定义为：在给定 #cf_span[p, q, r] 和数组 #cf_span[a1, a2, ... an] 的条件下，满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 时，#cf_span[p·ai + q·aj + r·ak] 的最大值。请帮助斯内普求出 #cf_span[x] 的值。注意，#cf_span[x] 的值可能为负数。输入的第一行包含 #cf_span[4] 个整数 #cf_span[n, p, q, r]（#cf_span[ - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ... an]（#cf_span[ - 109 ≤ ai ≤ 109]）。请输出一个整数，表示在满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 的条件下，#cf_span[p·ai + q·aj + r·ak] 能取得的最大值。在第一个样例中，我们可以取 #cf_span[i = j = k = 5]，因此答案为 #cf_span[1·5 + 2·5 + 3·5 = 30]。在第二个样例中，选择 #cf_span[i = j = 1] 和 #cf_span[k = 5] 可得答案 #cf_span[12]。 ## Input 输入的第一行包含 #cf_span[4] 个整数 #cf_span[n, p, q, r]（#cf_span[ - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105]）。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ... an]（#cf_span[ - 109 ≤ ai ≤ 109]）。 ## Output 输出一个整数，表示在满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 的条件下，#cf_span[p·ai + q·aj + r·ak] 能取得的最大值。 [samples] ## Note 在第一个样例中，我们可以取 #cf_span[i = j = k = 5]，因此答案为 #cf_span[1·5 + 2·5 + 3·5 = 30]。在第二个样例中，选择 #cf_span[i = j = 1] 和 #cf_span[k = 5] 可得答案 #cf_span[12]。

**Definitions** Let $ n, p, q, r \in \mathbb{Z} $, with $ 1 \leq n \leq 10^5 $, and $ p, q, r \in [-10^9, 10^9] $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ a_i \in [-10^9, 10^9] $. **Constraints** $ 1 \leq i \leq j \leq k \leq n $ **Objective** Compute: $$ \max_{1 \leq i \leq j \leq k \leq n} \left( p \cdot a_i + q \cdot a_j + r \cdot a_k \right) $$

Samples

Input #1

5 1 2 3
1 2 3 4 5

Output #1

Input #2

5 1 2 -3
-1 -2 -3 -4 -5

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Marvolo Gaunt's Ring",
    "description": {
      "content": "Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF855B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Professor Dumbledore is helping Harry destroy the Horcruxes. He went to Gaunt Shack as he suspected a Horcrux to be present there. He saw Marvolo Gaunt's Ring and identified it as a Horcrux. Although ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "邓布利多教授正在帮助哈利摧毁魂器。他前往冈特小屋，怀疑那里藏有一个魂器。他看到了马沃洛·冈特的戒指，并确认其为魂器。尽管他摧毁了它，但仍受到其诅咒的影响。斯内普教授正帮助邓布利多消除诅咒。为此，他需要给邓布利多恰好 #cf_span[x] 滴他配制的药水。\n\n#cf_span[x] 的值定义为：在给定 #cf_span[p, q, r] 和数组 #cf_span[a1, a2, ... an] 的...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, p, q, r \\in \\mathbb{Z} $, with $ 1 \\leq n \\leq 10^5 $, and $ p, q, r \\in [-10^9, 10^9] $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in [-10^...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments