Puju

시간 제한1초메모리 제한1024 MB

요약

덤불이 있는 한 줄의 칸들에서 S에서 시작한 트랙터가 최대 K번 이동해 덤불을 제거할 때, 이후 만들 수 있는 가장 큰 연결된 경작 가능 구역의 크기를 구한다.

난이도: 보통10점 중 7점
유형: 슬라이딩 윈도우, 투 포인터, 그리디, 누적 합
정답자: 아직 제출이 없습니다

문제

Aednik Kazimir ostis hiljuti uue maalapi, mis koosneb $N$ sirges reas olevast ruudust. Ruudud on nummerdatud vasakult paremale $1 \ldots N$ . Kahjuks on ainult mõned ruudud aianduseks sobivad, sest osadel ruutudel kasvavad pujutihnikud. Nende hävitamiseks rentis Kazimir rohimistraktori.

Töö alguses on Kazimir traktoriga ruudus $S$ . Igal sammul võib ta liikuda oma asukohast ühte selle naaberruutu (s.t ruudust $i$ ruutu $i - 1$ või ruutu $i + 1$ ). Kui uues ruudus on pujud, juurib traktor need välja ja ruut muutub aianduseks sobivaks. Kahjuks on traktoril kütust ainult $K$ sellise sammu jaoks.

Rohimistöö järel võib Kazimir piiramatult liikuda ühest pujuvabast ruudust selle pujuvabadesse naabritesse ja igale poole taimi istutada, kuid ei pääse läbi pujudega ruutudest. Kirjutada programm, mis leiab maksimaalse pinna, millel Kazimir saab taimi kasvatama hakata.

입력

Sisendi esimesel real on maalapi suurus $N$ ( $1 \le N \le 10^6$ ), traktori kütusevaru $K$ ( $0 \le K \le 10^9$ ) ja Kazimiri lähtekoht $S$ ( $1 \le S \le N$ ).

Teisel real on täpselt $N$ märki, kus '.' tähistab pujuvaba ja '#' pujudega ruutu. Ruut $S$ (Kazimiri lähtekoht) on aianduseks sobiv.

출력

Väljastada maksimaalne ruutude arv, millel Kazimir saab hakata taimi kasvatama.

예제5

예제 1
입력
```
10 1 1
.#........
```
예상 출력
```
10
```
예제 2
입력
```
10 1 3
.#.#......
```
예상 출력
```
8
```
예제 3
입력
```
10 2 3
.#.#......
```
예상 출력
```
8
```
예제 4
입력
```
10 3 3
.#.#......
```
예상 출력
```
10
```
예제 5
입력
```
10 5 1
.#########
```
예상 출력
```
6
```