Server Time:

User's AC Ratio in this contest

15.4% (2/13)

Submission's AC Ratio in this contest

4.3% (2/47)

Description

時間回到學期第三週某天晚上,
剛讀完課程教材的偉杰一邊吃著牛肉麵一邊思考著最大區間和問題:

給定長度為 $N$ 的整數數列 $A_1, A_2, ... , A_N$,對於所有 $i \le j$ 要求找到最大的 $A_i+A_{i+1}+...+A_j$

想著想著他發現:欸不是,今天的牛肉麵也太好吃了吧!?
牛肉麵,看似簡單 但其實要做到好吃是非常複雜的。
粗略分解有湯有麵有肉,不但要面面俱到,並且東鳴西應,好吃的東西全部加起來不一定總是好吃的,
所以隨著其他食材的調整,原先的食材料理過程也得跟著變化,這種調整會使得好吃程度具有倍數效應

偉杰覺得好吃程度跟最大區間和有異曲同工之妙,於是他就想:
若可選擇至多一段連續區間乘上整數 $x$,使得改變後的 $A$ 最大區間和變得更大,那最大是多少?

例如 $A = (-3, 7, -3, 2, -7), x = -2$
最佳解為將 $[3, 5]$ 中數字乘上 $x$,則 $A' = (-3, 7, 6, -4, 14)$ 的最大區間和為 $23 = \sum\limits_{i=2}^{5} A'_i$

Input Format

第一列給兩個整數 $N, x$ 表示數列長度及欲乘上的整數 $(1 \le N \le 5\cdot 10^5, \left| x \right| \le 100)$
第二列給 $N$ 個整數 $\{A_i\}_{i=1}^N$ 表示原問題中的數列 $(\left| A_i \right| \le 10^9)$

Output Format

輸出選擇至多一段連續區間乘上整數 $x$ 後的 $A$ 的最大區間和的最大可能值

Sample Input 1

5 -2
-3 7 -2 3 -7

Sample Output 1

22

Sample Input 2

5 42
-1 -2 -100 -4 -1

Sample Output 2

0

Sample Input 3

1 -1
2

Sample Output 3

2

Sample Input 4

7 -2
-1 -2 -3 -4 -5 3 -5

Sample Output 4

34

Hints

  • 空區間也算一種區間 (即區間和為 $0$)
  • 至多一段連續區間乘上整數 $x$ 代表不一定要選一段區間做改變
  • 偉杰喜歡吃牛肉麵

Problem Source

CODEFORCES 1155D Beautiful Array

Subtasks

No. Testdata Range Score
1 0~29 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 131072 65536 1
1 1000 131072 65536 1
2 1000 131072 65536 1
3 1000 131072 65536 1
4 1000 131072 65536 1
5 1000 131072 65536 1
6 1000 131072 65536 1
7 1000 131072 65536 1
8 1000 131072 65536 1
9 1000 131072 65536 1
10 1000 131072 65536 1
11 1000 131072 65536 1
12 1000 131072 65536 1
13 1000 131072 65536 1
14 1000 131072 65536 1
15 1000 131072 65536 1
16 1000 131072 65536 1
17 1000 131072 65536 1
18 1000 131072 65536 1
19 1000 131072 65536 1
20 1000 131072 65536 1
21 1000 131072 65536 1
22 1000 131072 65536 1
23 1000 131072 65536 1
24 1000 131072 65536 1
25 1000 131072 65536 1
26 1000 131072 65536 1
27 1000 131072 65536 1
28 1000 131072 65536 1
29 1000 131072 65536 1