問題一覧 > 通常問題

No.2553 Holidays

レベル : / AI推定難易度 : 1950 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 20
作問者 : sepa38 / テスター : dyktr_06 InTheBloom Seed57_cash
お気に入りにしたユーザー ProblemId : 10020 / 自分の提出
問題文最終更新日: 2023-11-25 12:02:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
MMA Contest 017 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。