Description

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

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

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

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

其發電方法如下:

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

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

其在數線上的座標分別為x1x2...、xn(座標已經過排序)。

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

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

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

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

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

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

Input Format

輸入格式:

n k p

x1 x2  xn

第一行有三個整數nkp,第二行有n個整數x,意義同題敘。

輸入範圍:

1n106

1k109

1p1000

對於1in1xi106

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|31|2=1

第2台發電機的電場值為5|33|2=5

第3台發電機的電場值為5|33|2=5

第4台發電機的電場值為5|53|2=1

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

Subtasks

No. Testdata Range Score

TopCoder

餘切
freeh1

User's AC Ratio

100.0% (13/13)

Tags

Problem Source

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

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