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 最近迷上偶像活動了，而他最推的偶像是星野☆布萊恩。
星野☆布萊恩是從「偶像選拔祭」這個節目出道的，而他是當年的第一名。

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

偶像選拔祭的規則如下，總共有 N 位選手，編號 1∼N，每位選手的能力值分別為 a1∼aN。
在經過層層選拔後，N 位選手會組成團體出道，假設共組了 X 個團體，X 可以是 1∼N 的整數（X=1 代表全部選手都在同一個團體，X=N 代表每個選手都自己組成一個團體）。
第 i 個團體的成員會是編號 li∼ri 的選手，寫成區間的形式是 [l1,r1],[l2,r2],…,[lX,rX]。
每個團體至少有一人，且每個選手恰屬於一個團體，也就是說 l1=1,rX=N，對所有 1≤i<X，ri+1=li+1。

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

Input Format

第一行有三個整數 N,K,P。
第二行有 N 個正整數 a1∼aN，代表每個選手的能力值。

對於所有測試資料：

  • 1≤N≤2×105
  • 1≤K≤N
  • 0≤P≤1012
  • 1≤ai≤109

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≤500 11
4 0~3, 6~17 N≤2000 12
5 1, 3, 18~29 ai≤ai+1（1≤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