레이팅 미적용설명
레시피 벨트에 \(N\)개의 재료가 순서대로 놓여 있고 \(i\)번째 재료의 종류가 \(a_i\)이다.
요리사는 연속한 재료 구간만 사용할 수 있으며, 사용한 구간에 등장하는 서로 다른 재료 종류가 \(K\)가지를 넘지 않아야 한다. 이 조건을 만족하는 가장 긴 연속 구간의 길이를 구하여라.
제약
\(1 \le K \le N \le 1500\), \(1 \le a_i \le 10^9\)
입력 형식
첫째 줄에 재료 수 \(N\)과 허용 종류 수 \(K\)가 주어진다.
둘째 줄에 \(N\)개의 재료 종류 \(a_1, \dots, a_N\)이 주어진다.
출력 형식
서로 다른 재료가 \(K\)종 이하인 가장 긴 연속 구간의 길이를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 40점 | \(1 \le N \le 200\) |
Subtask 2 | 60점 | 추가 제약이 없다. |
예제 1
입력
8 2
1 2 1 2 3 3 4 5
출력
4
설명
서로 다른 재료가 \(2\)종 이하인 가장 긴 구간은 \([1,2,1,2]\)로 길이 \(4\)이다.
예제 2
입력
5 1
4 4 2 2 2
출력
3
설명
재료를 \(1\)종만 쓰는 가장 긴 구간은 \([2,2,2]\)로 길이 \(3\)이다.
문제 정보
riseoj 작성
출처 Original
태그