← 返回题目列表

AtCoder · arc174_a

A. 乘法

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

分数: 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