2275 . 芒果不想寫 p7

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

81.8% (63/77)

Submission's AC Ratio

19.9% (88/443)

Tags

CKcon 2022-CKcon

Description

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

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

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

Input Format

第一行會有兩個整數 n, k，1≤k≤n≤2⋅106
第二行會有一個由 01 組成的字串，字串長度為 n，代表接下來每一個大杓桃子會不會上線， 0 代表桃子不會上線， 1 則反之。
第三行會有 n 個數 ai ，分別代表芒果在這個大杓的快樂度
−109≤ai≤109

Output Format

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

Sample Input 1

5 3
10101
4 8 -7 6 -3

Sample Output 1

12

Sample Input 2

10 6
1010011110
-9 12 -4 -5 -3 13 -7 -19 28 -9

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≤3000 13
3 14~23 n≤2×105,ai≥0 16
4 2~33 n≤2×105 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
Submit
Back to Top