시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 180 60 36 42.353%

문제

그림1. 준표가 좋아하는 하얀색의 미미

준표는 오랜만에 미미와 함께 산책을 나왔다. 산책로에는 일렬로 검은색과 흰색 조약돌이 놓여 있다. 총 N개의 조약돌은 1번부터 N번까지 차례로 번호가 붙여져 있다. 준표는 이 조약돌을 주워 집에 장식하려고 한다.

준표는 임의의 지점에서 산책을 시작하고, 원하는 지점에서 산책로를 빠져나와 집으로 돌아간다. 이때 준표는 산책한 구간에 있는 모든 조약돌을 줍는다. 미미의 건강을 위해 준표는 조금이라도 더 긴 구간을 산책하고 싶다. 하지만 준표에게는 확고한 취향이 있어, 아래 조건을 만족하는 구간만을 산책할 수 있다.

  1. 준표는 까만색을 싫어한다. 그래서 까만색 조약돌은 B개 이하로 줍고 싶다.
  2. 준표는 미미와 같은 흰색을 좋아한다. 그래서 흰색 조약돌은 W개 이상 줍고 싶다.

만약 위 조건을 만족하는 구간이 없다면 준표는 바로 집으로 돌아간다. 이때 준표와 미미가 산책할 수 있는 구간 중 가장 긴 구간의 길이를 구해보자.

입력

첫 줄에 조약돌의 총 개수 N, 준표가 원하는 검은 조약돌의 최대개수 B와 하얀 조약돌의 최소개수 W가 주어진다. 둘째 줄에는 N개의 조약돌의 정보가 한 줄로 주어진다. i번째 문자가 B라면 i번 조약돌은 검은색이고, W라면 흰색이다.

출력

준표와 미미가 걷게 될 가장 긴 구간의 길이를 한 줄에 출력한다. 준표가 원하는 조건에 맞는 구간이 없다면 0을 출력한다.

Small (100점)

  • 1 ≤ N ≤ 3,000
  • 0 ≤ B, W, B+W ≤ N

Large (150점)

  • 1 ≤ N ≤ 300,000
  • 0 ≤ B, W, B+W ≤ N

예제 입력 1

10 1 2
WBBWWBWWBW

예제 출력 1

5

예제 입력 2

7 2 4
WBBBBBW

예제 출력 2

0

출처

University > 아주대학교 > 2018 Ajou Porgramming Contest: Division 2 F번