15648번 - 추출하는 폴도 바리스타입니다 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 64 MB | 505 | 243 | 171 | 47.368% |
문제
추출하는 폴은 바리스타입니다. 폴에게는 커피콩 N개가 순서대로 주어집니다. 폴은 이 중 몇 개를 골라서 추출할 예정입니다. 이때, 최종 결과물의 질이 좋아야 할 것입니다. 결과물의 질이 좋기 위해서는, 커피콩들의 종류(정수로 표현됩니다.)로 이루어진 수열의 부분수열을 A라고 하면, 2 이상의 모든 i 에 대해 Ai - 1 ≡ Ai (mod k) 나 Ai - 1 - d ≤ Ai ≤ Ai - 1 + d를 만족함을 뜻합니다.
폴을 위해서 질이 좋은 커피 추출물 중 가장 많은 커피콩을 고를 때 그 개수를 구해주세요.
입력
첫째 줄에 N, k 와 d가 주어집니다. (1 ≤ N ≤ 5 × 105, 1 ≤ k, d ≤ 5 × 105)
N개의 커피콩의 순서와 각각의 번호를 나타내는 길이 N의 배열 S가 다음 줄에 주어집니다. (1 ≤ Si ≤ 5 × 105)
출력
질이 좋은 커피 추출물 중 가장 많은 커피콩을 고를 때 그 개수를 출력합니다.
예제 입력 1
9 7 2 1 5 12 10 8 6 4 4 3
예제 출력 1
8
출처
- 문제의 오타를 찾은 사람: jh05013
- 문제를 만든 사람: moonrabbit2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호