시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 1024 MB | 168 | 42 | 30 | 23.438% |
길이 $N$인 수열 $A_1, A_2, \dots , A_N $이 있다.
이 수열을 순서를 바꾸지 않고 $K$개의 수열로 쪼갤 수 있다.
예를 들어 수열 [1, 3, 5, 7, 9]를 [1], [3, 5], [7, 9] 와 같이 3개의 수열로 쪼갤 수 있다. 하지만 [1], [3, 7], [5, 9] 와 같이 쪼갤 수는 없다.
이 때 모든 수열은 하나 이상의 수를 포함해야 하고 모든 수는 정확히 하나의 수열에 포함되어야 한다.
수열에 포함된 서로 다른 수의 개수를 수열의 가치로 정의하자.
쪼개진 수열들의 가치의 합의 최댓값을 구하시오.
첫 번째 줄에 정수 $N$과 $K$가 공백으로 구분되어 주어진다. $(1\leq K \leq N \leq 2\times 10^5)$
두 번째 줄에 $N$개의 정수 $A_1,A_2, \dots , A_N$이 공백으로 구분되어 주어진다. $(1\leq A_1, A_2, \dots , A_N \leq N)$
첫 번째 줄에 쪼개진 수열들의 가치의 합의 최댓값을 출력한다.
5 2 2 3 2 4 3
5
5 2 2 1 1 2 2
4