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$ 個數字 $a_1, a_2, \dots, a_N$，以及兩個常數 $K, b$，你必須要選擇一些數字 $L_1, L_2, \dots, L_M$，滿足：

  • $1 = L_1 < L_2 < L_3 < \dots < L_M = N$
  • $L_{i + 1} - L_i \leq K \forall i \in [1, M - 1]$

你得到的分數會是：

$\sum_{i = 1}^ {M} a_{L_i} - b\sum_{i = 1}^ {M - 1}(L_{i + 1} - L_i)^ 2$

請你最大化此分數。

Input Format

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

接下來的一行，包含 $N$ 個整數，分別是 $a_1, a_2, \dots, a_N$。

  • $2 \leq N \leq 5 \times 10^ 5$
  • $1 \leq K \leq N$
  • $-10^ 9 \leq a_i \leq 10^ 9$
  • $0 \leq b \leq 10^ 5$

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 \neq 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