169 . 序列分割

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

33.3% (16/48)

Tags

ioicamp ioicamp-2022

Description

給 N 個數字 a1,a2,…,aN，以及兩個常數 K,b，你必須要選擇一些數字 L1,L2,…,LM，滿足：

  • 1=L1<L2<L3<⋯<LM=N
  • Li+1−Li≤K∀i∈[1,M−1]

你得到的分數會是：

∑i=1MaLi−b∑i=1M−1(Li+1−Li)2

請你最大化此分數。

Input Format

輸入的第一行包含三個整數 N,K,b，分別代表序列的長度，以及兩個常數。

接下來的一行，包含 N 個整數，分別是 a1,a2,…,aN。

  • 2≤N≤5×105
  • 1≤K≤N
  • −109≤ai≤109
  • 0≤b≤105

Output Format

輸出一個整數於一行，代表最大的分數。

Sample Input 1

5 2 0
-1 -2 -3 -4 -5

Sample Output 1

-9

Sample Input 2

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

Sample Output 2

1

Sample Input 3

8 3 5
3 1 4 1 5 9 2 6

Sample Output 3

-4

Hints

Problem Source

IOICamp 2022 Day3 pA

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0, 3~12 b=0 80
3 1, 13~27 b≠0,K=N 80
4 0~37 無額外限制 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2 4
1 1000 262144 65536 1 3 4
2 1000 262144 65536 1 4
3 1000 262144 65536 2 4
4 1000 262144 65536 2 4
5 1000 262144 65536 2 4
6 1000 262144 65536 2 4
7 1000 262144 65536 2 4
8 1000 262144 65536 2 4
9 1000 262144 65536 2 4
10 1000 262144 65536 2 4
11 1000 262144 65536 2 4
12 1000 262144 65536 2 4
13 1000 262144 65536 3 4
14 1000 262144 65536 3 4
15 1000 262144 65536 3 4
16 1000 262144 65536 3 4
17 1000 262144 65536 3 4
18 1000 262144 65536 3 4
19 1000 262144 65536 3 4
20 1000 262144 65536 3 4
21 1000 262144 65536 3 4
22 1000 262144 65536 3 4
23 1000 262144 65536 3 4
24 1000 262144 65536 3 4
25 1000 262144 65536 3 4
26 1000 262144 65536 3 4
27 1000 262144 65536 3 4
28 1000 262144 65536 4
29 1000 262144 65536 4
30 1000 262144 65536 4
31 1000 262144 65536 4
32 1000 262144 65536 4
33 1000 262144 65536 4
34 1000 262144 65536 4
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
Submit
Back to Top