你有一個長度為 $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$ 。
第一行有兩個正整數 $N,k(k\leq N\leq1.5\times10^ 6)$ ,分別如題目所述。
接下來一行有 $N$ 個非負整數,第 $i$ 個整數 $a_i(a_i\leq10^ 6)$ 代表序列中第 $i$ 個元素。
輸出一個整數,代表你最大能選到的元素總和。
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 | |
24 | 1000 | 65536 | 65536 | |
25 | 1000 | 65536 | 65536 | |
26 | 1000 | 65536 | 65536 | |
27 | 1000 | 65536 | 65536 | |
28 | 1000 | 65536 | 65536 | |
29 | 1000 | 65536 | 65536 | |
30 | 1000 | 65536 | 65536 | |
31 | 1000 | 65536 | 65536 | |
32 | 1000 | 65536 | 65536 | |
33 | 1000 | 65536 | 65536 | |
34 | 1000 | 65536 | 65536 | |
35 | 1000 | 65536 | 65536 | |
36 | 1000 | 65536 | 65536 | |
37 | 1000 | 65536 | 65536 | |
38 | 1000 | 65536 | 65536 | |
39 | 1000 | 65536 | 65536 | |
40 | 1000 | 65536 | 65536 | |
41 | 1000 | 65536 | 65536 | |
42 | 1000 | 65536 | 65536 | |
43 | 1000 | 65536 | 65536 | |
44 | 1000 | 65536 | 65536 | |
45 | 1000 | 65536 | 65536 | |
46 | 1000 | 65536 | 65536 | |
47 | 1000 | 65536 | 65536 | |
48 | 1000 | 65536 | 65536 | |
49 | 1000 | 65536 | 65536 | |
50 | 1000 | 65536 | 65536 | |
51 | 1000 | 65536 | 65536 | |
52 | 1000 | 65536 | 65536 | |
53 | 1000 | 65536 | 65536 | |
54 | 1000 | 65536 | 65536 | |
55 | 1000 | 65536 | 65536 | |
56 | 1000 | 65536 | 65536 | |
57 | 1000 | 65536 | 65536 | |
58 | 1000 | 65536 | 65536 | |
59 | 1000 | 65536 | 65536 | |
60 | 1000 | 65536 | 65536 | |
61 | 1000 | 65536 | 65536 | |
62 | 1000 | 65536 | 65536 | |
63 | 1000 | 65536 | 65536 | |
64 | 1000 | 65536 | 65536 | |
65 | 1000 | 65536 | 65536 | |
66 | 1000 | 65536 | 65536 | |
67 | 1000 | 65536 | 65536 | |
68 | 1000 | 65536 | 65536 | |
69 | 1000 | 65536 | 65536 |