No.2553 Holidays
タグ : / 解いたユーザー数 20
作問者 :
sepa38
/ テスター :
Seed57_cash
Problem Statement
Sepa studied hard, so he is allowed to change at most $M$ weekdays into holidays among the $N$ days starting from tomorrow. When Sepa creates holidays, the following rules apply for a string $S$ of length $N$.
- If $S_i$ is
-, the day $i$ days from today is originally a weekday, but it can be changed into a holiday. - If $S_i$ is
o, the day $i$ days from today is already a holiday. - If $S_i$ is
x, the day $i$ days from today is a weekday and cannot be changed into a holiday.
After all operations are finished, all days satisfying the following condition are replaced with holidays.
- For $i$ satisfying $2 \leq i \leq N - 1$, if the day $i - 1$ days from today is a holiday, $S_i \neq$
x, and the day $i + 1$ days from today is a holiday, then the day $i$ days from today becomes a holiday.
Find the maximum possible number of holidays among the $N$ days starting from tomorrow when Sepa acts optimally.
Input
$N \ M$ $S$
Constraints
- $N, M$ are integers.
- $3 \leq N \leq 10^5$
- $0 \leq M \leq N$
- $S_i$ is one of
-,o,x - $S_1$ and $S_N$ are
x
Output
Print the answer on $1$ line.
Sample
Sample 1
Input
8 2 x-o----x
Output
5
By changing the days $5$ days and $7$ days from today into holidays, the string becomes x-o-o-ox.
The days $4$ days and $6$ days from today also become holidays, so it becomes x-ooooox.
Sample 2
Input
20 5 xo--x-o--o--------ox
Output
14
Sample 3
Input
5 0 xo-ox
Output
3
Even without performing any operation, the day $3$ days from today becomes a holiday.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。