芒果喜歡待在 DC 聊天,桃子喜歡 p7
接下來有 $n$ 大杓的時間(大杓是一種時間單位)
芒果用奇異果的魔法得知了桃子接下來每個大杓會不會上線
桃子要是上線了然後發現芒果也在上線就會去催芒果寫 p7
芒果想要選擇一段連續的時段聊天,但是他不想被催 p7 太多次,所以他訂下一個限制:不能跟桃子同時上線超過 $k$ 大杓
已知芒果接下來每個大杓如果待在 DC 的話的快樂度
他獲得的總快樂度就是每個待在 DC 的大杓的快樂度總和
請幫芒果算出在他不違反題目限制的情況下總快樂度最大會是多少
芒果也可以選擇從不上線 這樣他的快樂度就會是 $0$
第一行會有兩個整數 $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$
輸出一個數字,代表芒果可以獲得的總快樂度
由於本題輸入量較大,建議使用 scanf/printf
或是使用 cin/cout
並在程式前面加上 ios_base::sync_with_stdio(0);cin.tie(0);
以加快輸入的速度。
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 |