TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

68.0% (34/50)

Tags

Description

詠堯電死(也稱永搖電死,簡稱yyds)是中國大陸網絡熱詞,最早出現於《英雄聯盟》前職業選手山泥若的一次直播中,在直播中他評價鄭詠堯(ID:yungyaorz):“詠堯,永遠的神!”。這一網絡熱詞現已成功“出圈”,用於娛樂、體育等多個方面。

“yyds”,“永遠滴神”等關聯名稱現已被部分商家申請註冊商標,分類涉及多個方面。

2040年,小龍作為颱北市的市長,希望能開發一種無汙染的替代能源。

聰明的他很快找到了yungyaorz,希望能利用他的電能作為發電站的能源來源。

其發電方法如下:

我們可以把颱北市看成一個數線,

在颱北市已經設置了$n$個發電站用來接收yungyaorz的電能,

其在數線上的座標分別為$x_1$、$x_2$...、$x_n$(座標已經過排序)。

yungyaorz的位置為$s$(位置必須為整數),自身帶有的電能為$k$,他對外會發出一個電場(尚未受到物理學界證實)

且此電場的大小會根據距離遞減,且遞減率$p$,

意即若某點距離$s$的距離為$d$,則該點的電場值為 $k - dp$ (注意:此值可能為負)。

而電場值能夠成為發電機電量的來源。

為了最大化發電量,小龍決定讓yungyaorz待在一個特定的位置,使得發電機產生的電量最大(即發電機所在位置的電場值和最大)。

為了評估預算,請你幫小龍計算發電機所在位置電場值和的最大值。

Input Format

輸入格式:

$n\ k\ p$

$x_1\ x_2\ \cdots\ x_n$

第一行有三個整數$n$、$k$、$p$,第二行有$n$個整數$x$,意義同題敘。

輸入範圍:

$1 \leq n \leq 10^6$

$1 \leq k \leq 10^9$

$1 \leq p \leq 1000$

對於$1 \leq i \leq n$,$1 \leq x_i \leq 10^6$

Output Format

請輸出一個整數代表發電機所在位置電場值和的最大值。

Sample Input 1

4 5 2
1 3 3 5

Sample Output 1

12

Sample Input 2

5 10 1
1 6 9 10 14

Sample Output 2

33

Hints

範測說明:

第一筆:

當我們選取$s = 3$時,

第1台發電機的電場值為$5 - |3 - 1| \cdot 2 = 1$

第2台發電機的電場值為$5 - |3 - 3| \cdot 2 = 5$

第3台發電機的電場值為$5 - |3 - 3| \cdot 2 = 5$

第4台發電機的電場值為$5 - |5 - 3| \cdot 2 = 1$

電場值和 $= 1+5+5+1 = 12$ 為最大值。

Problem Source

建中電研110上學期大社社內賽

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536
1 1000 250000 250000 65536
2 1000 250000 250000 65536
3 1000 250000 250000 65536
4 1000 250000 250000 65536
5 1000 250000 250000 65536
6 1000 250000 250000 65536
7 1000 250000 250000 65536
8 1000 250000 250000 65536
9 1000 250000 250000 65536