2275 . 芒果不想寫 p7
TopCoder
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 1
5 3
10101
4 8 -7 6 -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
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 \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 |