问题陈述
2014年春天,一名学生顺利考入大学,开始独自生活。此时的问题是晚餐该如何安排。他决定制定接下来$N$天晚餐的计划。
他希望在$N$天内获得的幸福感总和尽可能大。当然,吃越美味或越喜欢的食物,幸福感就越高。
他的晚餐选择有两个,要么去附近的食堂,要么自己做饭。
食堂获得的幸福度会根据当天的菜单而异。Memeu每天都会变化,但每天只有一种类型可选,$N$白天菜单已经公开。因此,他知道如果他带$i$($1 \leq i \leq N$)去自助餐厅,他会获得$C_i$幸福感。
自煮带来的幸福感取决于自煮体验开始时的幸福感。家庭烹饪力量 它是将乘以常数$P$。家庭烹饪力量 它是将的青少年价值为$Q美元,每天如果你去食堂,会得-1;如果你在家做饭,+1;在一天用餐结束时会变。 [
让我们为他找到最大的幸福总和。
输入
输入以 $N+1$ 行的形式表示。
$N$$P$$Q$
$C_1$
$C_2$
:
:
$C_N$
- 第一行给定了三个整数 $N、P 和 Q$,分别是用于计算自炊天数和幸福度的常数。家庭烹饪力量 它是将是少年值。
- 从第2行到第 $N+1$ 行,每行给出一个整数,第 $i+1$ 行给出第 $i$ 天去食堂时获得的幸福度。
约束
- $1 \leq N \leq 500{,}000$
- $0 \leq P \leq 500{,}000$
- $ |Q| \leq 500{,}000$
- $ | C_i | \leq 500{,}000$
输出
输出幸福度可能达到的最大值。
示例输入 1
1 1 1 2
样本输入 1 的输出
2
- 需要考虑的计划只有一天。去食堂幸福度是2,自炊是1,因此答案是2。
示例输入 2
3 2 1 3 3 3
样本输入 2 的输出
12
- 在这个例子中,每天自炊是最优的,幸福度为 $2 imes 1+2 imes 2+2 imes 3 = 12$。
示例输入 3
3 1 -1 2 -3 2
样本输入 3 的输出
2
- 仅在第2天自炊是最优的。
示例输入 4
3 1 -10 -10 -10 -10
样本输入 4 的输出
-27
- 答案也可能为负数。无论多难吃,晚餐都必须吃。