39 . 最大子序列和 - EXTREME

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

55.6% (5/9)

Submission's AC Ratio

36.4% (8/22)

Tags

2020 高階競技程式設計 - Contest #3

Description

你有一個長度為 $N$ 的序列，你想選取其中若干元素，使這些元素的總和最大，
但是你不能選取序列中的連續 $k$ 個元素$(a_i,a_{i+1},a_{i+2},\cdots,a_{i+k-1})$，
你想知道你最大能選到的元素總和為多少。

例如 $N=5,\ k=3$ ，序列為 $1,2,3,4,5$ ，
則你能選取最大且沒有連續 $k$ 個被選到的為 ${1,2,4,5}$ ，其總和為 $12$ 。

Input Format

第一行有兩個正整數 $N,k(k\leq N\leq1.5\times10^ 6)$ ，分別如題目所述。
接下來一行有 $N$ 個非負整數，第 $i$ 個整數 $a_i(a_i\leq10^ 6)$ 代表序列中第 $i$ 個元素。

Output Format

輸出一個整數，代表你最大能選到的元素總和。

Sample Input 1

5 3
1 2 3 4 5

Sample Output 1

12

Sample Input 2

9 3
1 9 4 5 7 5 6 3 8

Sample Output 2

36

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~19 $\forall\ i\neq j,\ a_i=a_j$ 7
2 0~39 $\forall\ i<j,\ a_i\leq a_j$ 15
3 0~69 無特別限制 78

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2 3
1 1000 65536 65536 1 2 3
2 1000 65536 65536 1 2 3
3 1000 65536 65536 1 2 3
4 1000 65536 65536 1 2 3
5 1000 65536 65536 1 2 3
6 1000 65536 65536 1 2 3
7 1000 65536 65536 1 2 3
8 1000 65536 65536 1 2 3
9 1000 65536 65536 1 2 3
10 1000 65536 65536 1 2 3
11 1000 65536 65536 1 2 3
12 1000 65536 65536 1 2 3
13 1000 65536 65536 1 2 3
14 1000 65536 65536 1 2 3
15 1000 65536 65536 1 2 3
16 1000 65536 65536 1 2 3
17 1000 65536 65536 1 2 3
18 1000 65536 65536 1 2 3
19 1000 65536 65536 1 2 3
20 1000 65536 65536 2 3
21 1000 65536 65536 2 3
22 1000 65536 65536 2 3
23 1000 65536 65536 2 3
24 1000 65536 65536 2 3
25 1000 65536 65536 2 3
26 1000 65536 65536 2 3
27 1000 65536 65536 2 3
28 1000 65536 65536 2 3
29 1000 65536 65536 2 3
30 1000 65536 65536 2 3
31 1000 65536 65536 2 3
32 1000 65536 65536 2 3
33 1000 65536 65536 2 3
34 1000 65536 65536 2 3
35 1000 65536 65536 2 3
36 1000 65536 65536 2 3
37 1000 65536 65536 2 3
38 1000 65536 65536 2 3
39 1000 65536 65536 2 3
40 1000 65536 65536 3
41 1000 65536 65536 3
42 1000 65536 65536 3
43 1000 65536 65536 3
44 1000 65536 65536 3
45 1000 65536 65536 3
46 1000 65536 65536 3
47 1000 65536 65536 3
48 1000 65536 65536 3
49 1000 65536 65536 3
50 1000 65536 65536 3
51 1000 65536 65536 3
52 1000 65536 65536 3
53 1000 65536 65536 3
54 1000 65536 65536 3
55 1000 65536 65536 3
56 1000 65536 65536 3
57 1000 65536 65536 3
58 1000 65536 65536 3
59 1000 65536 65536 3
60 1000 65536 65536 3
61 1000 65536 65536 3
62 1000 65536 65536 3
63 1000 65536 65536 3
64 1000 65536 65536 3
65 1000 65536 65536 3
66 1000 65536 65536 3
67 1000 65536 65536 3
68 1000 65536 65536 3
69 1000 65536 65536 3
Submit
Status
Ranklist
Back to Top