시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 165 | 51 | 47 | 37.600% |
과외맨은 배트맨, 스파이더맨, 슈퍼맨과 같은 슈퍼 히어로를 따라하는 한국의 대표 영웅이다. 오늘은 스파이더맨을 따라해보려고 한다. 과외맨은 고층 건물의 옥상을 점프하면서 돌아다니려고 한다.
고층 건물은 총 N개가 있고, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 매겨져 있다. 지금 과외맨은 K번 건물 위에 있다. 과외맨은 아직 힘이 많이 부족한다. 따라서, 현재 있는 건물의 왼쪽 또는 오른쪽 건물로만 점프해서 이동할 수 있다. 또, 지금 자신이 있는 건물의 높이보다 높지 않은 빌딩으로만 이동할 수 있다.
이런 과외맨을 도와주고 위해서 상근이는 일부 건물의 옥상에 트램폴린을 설치해 놓았다. 과외맨이 트램폴린을 이용해 점프를 한다면 다른 모든 건물로 이동할 수 있고, 건물의 높이와 상관없이 이동할 수 있다.
과외맨이 방문할 수 있는 서로 다른 건물의 개수의 최댓값을 구하는 프로그램을 작성하시오. 과외맨은 점프를 K번 빌딩에서 시작한다. 같은 건물을 여러 번 방문할 때도, 방문한 건물의 개수는 한 개로 센다.
첫째 줄에 건물의 수 N과 점프를 시작하는 건물의 번호 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N)
둘째 줄에는 106보다 작은 N개의 정수가 주어진다. 이 정수는 건물의 높이이며, 1번 건물부터 순서대로 주어진다.
셋째 줄에는 '.' 또는 'T'로 이루어진 N개의 문자가 주어진다. i번째 문자가 'T'인 경우에는 i번 건물의 옥상에 트램폴린이 설치되어 있는 것이다.
첫째 줄에 과외맨이 방문할 수 있는 서로 다른 건물 개수의 최댓값을 출력한다.
6 4 12 16 16 16 14 14 .T....
5
10 1 10 7 3 1 1 9 8 2 4 10 ..T..T....
7
Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Croatian Olympiad in Informatics 2012 4번