2328 . 偶像選拔祭

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

guagua0407
豬大哥

User's AC Ratio

30.0% (3/10)

Submission's AC Ratio

5.1% (4/79)

Tags

CKsim 2023-CKsim

Description

Caido 最近迷上偶像活動了，而他最推的偶像是星野$\Large ☆$布萊恩。
星野$\Large ☆$布萊恩是從「偶像選拔祭」這個節目出道的，而他是當年的第一名。

Caido 心想為什麼有人可以這麼優秀呢，這才想起來，星野$\Large ☆$布萊恩就讀的是植物園高級中學。
植物園高級中學是一所積極新創、學科齊全、學術實力雄厚、辦學特色鮮明，在國際上具有重要影響力與競爭力的綜合性高中，在多個學術領域具有非常前瞻的科技實力，擁有世界一流的實驗室與師資力量，各種排名均位於全球前列。歡迎大家報考植物園高級中學。

偶像選拔祭的規則如下，總共有 $N$ 位選手，編號 $1\sim N$，每位選手的能力值分別為 $a_1\sim a_N$。
在經過層層選拔後，$N$ 位選手會組成團體出道，假設共組了 $X$ 個團體，$X$ 可以是 $1\sim N$ 的整數（$X=1$ 代表全部選手都在同一個團體，$X=N$ 代表每個選手都自己組成一個團體）。
第 $i$ 個團體的成員會是編號 $l_i\sim r_i$ 的選手，寫成區間的形式是 $[l_1,r_1],[l_2,r_2],\dots ,[l_X,r_X]$。
每個團體至少有一人，且每個選手恰屬於一個團體，也就是說 $l_1=1,r_X=N$，對所有 $1\leq i<X$，$r_i+1=l_{i+1}$。

每個團體都會有收益，收益有可能是正的、等於零，也有可能是負的。
第 $i$ 個團體的收益會是團體成員裡能力值前 $\min(K,r_i-l_i+1)$ 小選手的能力值總和，扣掉出道成本 $P$。
Caido 很好奇在所有可能的團體分法中，總收益最大可以是多少，請你幫幫他！

Input Format

第一行有三個整數 $N,K,P$。
第二行有 $N$ 個正整數 $a_1\sim a_N$，代表每個選手的能力值。

對於所有測試資料：

  • $1\leq N\leq 2\times 10^ 5$
  • $1\leq K\leq N$
  • $0\leq P\leq 10^ {12}$
  • $1\leq a_i\leq 10^ 9$

Output Format

輸出一個整數，代表所有可能的團體分法中的最大總收益。

Sample Input 1

5 2 10
5 5 9 7 4

Sample Output 1

1

Sample Input 2

3 1 100
1 1 1

Sample Output 2

-99

Sample Input 3

3 2 1
48 76 3

Sample Output 3

125

Hints

在範例測資一中，總收益最大可以是 $1$，其中一個分法是分成 $[1,2],[3,5]$ 兩個團體，$(10-10)+(11-10)=1$。

在範例測資二中，只分成一個團體 $[1,3]$，總收益最大是 $-99$。

在範例測資三中，分成 $[1,2],[3,3]$ 兩個團體會有最大總收益 $(124-1)+(3-1)=125$。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 3~5 $P=0$ 1
3 0~3, 6~11 $N\leq 500$ 11
4 0~3, 6~17 $N\leq 2000$ 12
5 1, 3, 18~29 $a_i\leq a_{i+1}$（$1\leq i<N$） 15
6 1, 3, 30~33 $K=1$ 30
7 0~49 無其他限制 31

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 1572864 65536 1 3 4 7
1 3000 1572864 65536 1 3 4 5 6 7
2 3000 1572864 65536 1 3 4 7
3 3000 1572864 65536 2 3 4 5 6 7
4 3000 1572864 65536 2 7
5 3000 1572864 65536 2 7
6 3000 1572864 65536 3 4 7
7 3000 1572864 65536 3 4 7
8 3000 1572864 65536 3 4 7
9 3000 1572864 65536 3 4 7
10 3000 1572864 65536 3 4 7
11 3000 1572864 65536 3 4 7
12 3000 1572864 65536 4 7
13 3000 1572864 65536 4 7
14 3000 1572864 65536 4 7
15 3000 1572864 65536 4 7
16 3000 1572864 65536 4 7
17 3000 1572864 65536 4 7
18 3000 1572864 65536 5 7
19 3000 1572864 65536 5 7
20 3000 1572864 65536 5 7
21 3000 1572864 65536 5 7
22 3000 1572864 65536 5 7
23 3000 1572864 65536 5 7
24 3000 1572864 65536 5 7
25 3000 1572864 65536 5 7
26 3000 1572864 65536 5 7
27 3000 1572864 65536 5 7
28 3000 1572864 65536 5 7
29 3000 1572864 65536 5 7
30 3000 1572864 65536 6 7
31 3000 1572864 65536 6 7
32 3000 1572864 65536 6 7
33 3000 1572864 65536 6 7
34 3000 1572864 65536 7
35 3000 1572864 65536 7
36 3000 1572864 65536 7
37 3000 1572864 65536 7
38 3000 1572864 65536 7
39 3000 1572864 65536 7
40 3000 1572864 65536 7
41 3000 1572864 65536 7
42 3000 1572864 65536 7
43 3000 1572864 65536 7
44 3000 1572864 65536 7
45 3000 1572864 65536 7
46 3000 1572864 65536 7
47 3000 1572864 65536 7
48 3000 1572864 65536 7
49 3000 1572864 65536 7
Submit
Back to Top