Puju

면접 대비

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

요약

N칸짜리 땅에서 시작 칸 S부터 최대 K걸음 동안 덤불을 제거한 뒤, 도달할 수 있는 가장 넓은 구역의 넓이를 구합니다.

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

문제

아드니크 카지미르는 최근 $N$ 개의 칸이 일렬로 늘어선 새 땅을 샀다. 칸은 왼쪽에서 오른쪽으로 $1$ 부터 $N$ 까지 번호가 매겨져 있다. 안타깝게도 일부 칸에는 푸유 덤불이 자라 있어 정원으로 쓰기 어렵다. 덤불을 없애려고 카지미르는 잡초 제거 트랙터를 빌렸다.

작업을 시작할 때 카지미르는 트랙터와 함께 칸 $S$ 에 있다. 한 걸음마다 현재 칸의 바로 옆 칸인 $i-1$ 또는 $i+1$ 중 하나로 이동할 수 있다. 이동한 칸에 덤불이 있으면 트랙터가 덤불을 뽑아내고, 그 칸은 정원으로 쓸 수 있게 된다. 다만 트랙터의 연료는 $K$ 걸음분뿐이다.

제거 작업이 끝나면 카지미르는 덤불이 없는 칸들 사이를 제한 없이 이동하며 원하는 곳에 식물을 심을 수 있다. 덤불이 있는 칸은 통과할 수 없다. 식물을 기를 수 있는 최대 면적을 구하라.

입력

첫 줄에는 땅의 크기 $N$ ( $1 \le N \le 10^6$ ), 트랙터의 연료 $K$ ( $0 \le K \le 10^9$ ), 카지미르의 시작 위치 $S$ ( $1 \le S \le N$ )가 주어진다.

둘째 줄에는 정확히 $N$ 개의 문자가 주어진다. '.'은 덤불이 없는 칸, '#'은 덤불이 있는 칸을 뜻한다. 칸 $S$ 는 정원으로 쓸 수 있다.

출력

식물을 기를 수 있는 칸의 최대 개수를 출력한다.

예제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
```