TopCoder

Caido
$\text{W}ai\text{M}ai\text{QQ}\sim$

User's AC Ratio

87.9% (29/33)

Submission's AC Ratio

24.1% (40/166)

Tags

Description

芒果喜歡待在 DC 聊天,桃子喜歡 p7
接下來有 $n$ 大杓的時間(大杓是一種時間單位)
芒果用奇異果的魔法得知了桃子接下來每個大杓會不會上線
桃子要是上線了然後發現芒果也在上線就會去催芒果寫 p7
芒果想要選擇一段連續的時段聊天,但是他不想被催 p7 太多次,所以他訂下一個限制:不能跟桃子同時上線超過 $k$ 大杓

已知芒果接下來每個大杓如果待在 DC 的話的快樂度
他獲得的總快樂度就是每個待在 DC 的大杓的快樂度總和
請幫芒果算出在他不違反題目限制的情況下總快樂度最大會是多少

芒果也可以選擇從不上線 這樣他的快樂度就會是 $0$

Input Format

第一行會有兩個整數 $n$, $k$,$1 \leq k \leq n \leq 2 \cdot 10 ^ 6$
第二行會有一個由 $01$ 組成的字串,字串長度為 $n$,代表接下來每一個大杓桃子會不會上線, $0$ 代表桃子不會上線, $1$ 則反之。
第三行會有 $n$ 個數 $a_i$ ,分別代表芒果在這個大杓的快樂度
$-10 ^ 9 \leq a_i \leq 10 ^ 9$

Output Format

輸出一個數字,代表芒果可以獲得的總快樂度

Sample Input

// Sample input 1
5 3
10101
4 8 -7 6 -3
// Sample input 2
10 6
1010011110
-9 12 -4 -5 -3 13 -7 -19 28 -9

Sample Output

// Sample output 1
12

// Sample output 2
28

Hints

由於本題輸入量較大,建議使用 scanf/printf 或是使用 cin/cout並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);以加快輸入的速度。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~13 $n \le 3000$ 13
3 14~23 $n \le 2 \times 10 ^ 5, a_i \ge 0$ 16
4 2~33 $n \le 2\times 10 ^ 5$ 32
5 2~43 無其他限制 39

Testdata and Limits

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