← 返回题目列表

AtCoder · icpc2014summer_day4_d

D. 晚餐

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

问题陈述

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
  • 答案也可能为负数。无论多难吃,晚餐都必须吃。