分数: 300 点
问题陈述
给你一个长度的整数序列 N, A=(A_1,A_2,\dots,A_N),和一个整数 C.
求 中元素的最大可能和 A 执行以下操作后 最多一次:
- 指定整数 l 和 r 这样 1 \le l \le r \le N,并将每个相乘 A_l,A_{l+1},\dots,A_r by C.
约束
- 所有输入值均为整数。
- 1 \le N \le 3 \times 10^5
- -10^6 \le C \le 10^6
- -10^6 \le A_i \le 10^6
输入
输入由标准输入按以下格式给出:
N C A_1 A_2 \dots A_N
输出
将答案打印为整数。
示例输入 1
5 2 -10 10 20 30 -20
示例输出 1
90
在此输入中, A=(-10,10,20,30,-20), C=2.
执行一次指定操作后 l=2 和 r=4, A 将是 (-10,20,40,60,-20).
这里,元素的总和 A is 90,这是可实现的最大值。
示例输入 2
5 1000000 -1 -2 -3 -4 -5
示例输出 2
-15
在此输入中, A=(-1,-2,-3,-4,-5), C=1000000.
不执行运算,中的元素之和 A is -15,这是可实现的最大值。
示例输入 3
9 -1 -9 9 -8 2 -4 4 -3 5 -3
示例输出 3
13