{"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 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.\n\nValue 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.\n\n## Input\n\nFirst line of input contains 4 integers _n_, _p_, _q_, _r_ ( - 109 ≤ _p_, _q_, _r_ ≤ 109, 1 ≤ _n_ ≤ 105).\n\nNext line of input contains _n_ space separated integers _a_1, _a_2, ... _a__n_ ( - 109 ≤ _a__i_ ≤ 109).\n\n## Output\n\nOutput 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_.\n\n[samples]\n\n## Note\n\nIn the first sample case, we can take _i_ = _j_ = _k_ = 5, thus making the answer as 1·5 + 2·5 + 3·5 = 30.\n\nIn second sample case, selecting _i_ = _j_ = 1 and _k_ = 5 gives the answer 12.","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] 的条件下，满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 时，#cf_span[p·ai + q·aj + r·ak] 的最大值。请帮助斯内普求出 #cf_span[x] 的值。注意，#cf_span[x] 的值可能为负数。\n\n输入的第一行包含 #cf_span[4] 个整数 #cf_span[n, p, q, r]（#cf_span[ - 109 ≤ p, q, r ≤ 109, 1 ≤ n ≤ 105]）。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ... an]（#cf_span[ - 109 ≤ ai ≤ 109]）。\n\n请输出一个整数，表示在满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 的条件下，#cf_span[p·ai + q·aj + r·ak] 能取得的最大值。\n\n在第一个样例中，我们可以取 #cf_span[i = j = k = 5]，因此答案为 #cf_span[1·5 + 2·5 + 3·5 = 30]。\n\n在第二个样例中，选择 #cf_span[i = j = 1] 和 #cf_span[k = 5] 可得答案 #cf_span[12]。\n\n## Input\n\n输入的第一行包含 #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]）。\n\n## Output\n\n输出一个整数，表示在满足 #cf_span[1 ≤ i ≤ j ≤ k ≤ n] 的条件下，#cf_span[p·ai + q·aj + r·ak] 能取得的最大值。\n\n[samples]\n\n## Note\n\n在第一个样例中，我们可以取 #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]。","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^9, 10^9] $.\n\n**Constraints**  \n$ 1 \\leq i \\leq j \\leq k \\leq n $\n\n**Objective**  \nCompute:  \n$$\n\\max_{1 \\leq i \\leq j \\leq k \\leq n} \\left( p \\cdot a_i + q \\cdot a_j + r \\cdot a_k \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF855B","tags":["brute force","data structures","dp"],"sample_group":[["5 1 2 3\n1 2 3 4 5","30"],["5 1 2 -3\n-1 -2 -3 -4 -5","12"]],"created_at":"2026-03-03 11:00:39"}}