아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Rick-Roll Virus

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

요약
일직선에 놓인 N명 중 일부가 감염된 상태에서, 하루 뒤 거리 K 이내로 퍼진 뒤의 감염자를 M개의 치료제로 모두 치료할 수 있는지 판정한다.
난이도

보통10점 중 4점

유형
그리디, 구현, 구간
정답자
아직 제출이 없습니다

문제

2033년, 하루나라에서 밈 1위를 결정하고자 하는 투표에서 Rick Astley가 우승함과 동시에 하루나라에서 Rick-Roll Virus가 전염되고 있다. 이 바이러스에 감염되면 항상 Never gonna give you up을 흥얼거리기 때문에 haru_202는 이 바이러스를 막으려고 한다.

하루나라에 사는 NN명의 사람들은 일직선상에서 연속적으로 인접하여 살아가고 있으며, x=ix=i에 위치한 감염자는 11일 뒤 바이러스를 x=max⁡(1,i−K)x = \max(1, i-K), ⋯\cdots, ii, ⋯\cdots, min⁡(N,i+K)\min(N, i+K)에 있는 사람들에게 전염시킨다.

11일 뒤, haru_202가 치료제 MM개를 사용하여 Rick-Roll Virus에 감염된 사람을 모두 치료할 수 있는가? 단, 치료제는 11명에게 11개씩만 사용할 수 있다.

입력

첫 번째 줄에 정수 NN, MM, KK가 공백으로 구분되어 주어진다. (1≤N≤10,000;(1 \leq N \leq 10\\,000; 0<M≤N;0 < M \leq N; 0≤K≤⌊N2⌋)0 \leq K \leq \lfloor\frac{N}{2}\rfloor)

두 번째 줄에 사람들의 감염 상태를 나타내는 길이 NN의 문자열 SS가 주어진다. S_iS\_i는 x=ix=i에 위치한 사람의 감염상태를 나타내며, 다음과 같다. (1≤i≤N)(1 \leq i \leq N)

  • .: 감염되지 않음
  • R: 감염됨

출력

11일 뒤 Rick-Roll Virus에 감염된 사람들을 MM개의 치료제로 모두 치료할 수 있으면 Yes, 아니면 No를 출력한다.

예제2

  1. 예제 1

    입력
    5 3 1
    ..R..
    
    예상 출력
    Yes
    
  2. 예제 2

    입력
    10 1 1
    RRRRRRRRRR
    
    예상 출력
    No