시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB90424818727.180%

문제

주띵이는 오프라인 카드 게임 하프 스톤을 좋아하는 평범한 대학생이다. 주띵이가 자주 방문하는 게임용품 전문점인 '카드 몬스터'에서는 개점 3주년을 기념해 카드 팩 이벤트를 진행하고 있다. 이벤트에 참여한 사람은 사장이 만든 규칙을 만족하면 한 번에 많은 카드를 저렴하게 구매할 수 있다.

  1. N개의 카드가 한 줄로 진열되어 있으며, 카드의 자리는 바꿀 수 없다.
  2. 좌/우로 연속한 카드들을 묶어 하나의 '카드 팩'을 구성할 수 있다.
  3. 주띵이는 정확히 M개의 카드 팩을 구매해야 한다.
  4. 각 카드 팩을 구성하는 카드의 수는 일치해야 한다.
  5. 한 카드 팩안에 같은 종류의 카드가 두 장 이상 존재해서는 안 된다.
  6. 하나의 카드가 여러 카드팩에 속할 수 는 없다.

예를 들어서 N=10이고 M=3인 경우를 가정해보자. 각 카드의 식별 번호가 차례로 10, 9, 7, 7, 9, 8, 8, 8, 2, 1 이라고 한다면, 아래와 같은 방법들로 구매할 수도 있다.

그림1. 카드 팩을 한 장으로 구성한 경우의 예시

그림 2. 카드 팩을 두 장으로 구성한 경우의 예시

그림 3. 구매할 수 없는 경우의 예시

개점 이벤트로 인해 각 카드 팩을 구성하는 카드 수에 상관없이 항상 가격이 일정하므로, 주띵이는 최대한 많은 카드를 카드 팩으로 구성하려고 한다. 하지만 한 번 카드 팩을 구성한 이후에 수정하는 것은 가게 주인이 좋아하지 않으므로, 미리 가장 이득이 되는 방법을 설계한 후 구성하려고 한다. 주띵이를 도와주자. 주띵이가 각 카드 팩에 구성할 수 있는 최대의 카드 수는 몇 장인가?

입력

첫 줄에는 두 개의 자연수 N과 M이 공백으로 구분되어 주어진다. N은 상점에 진열된 카드의 수이며 M은 주띵이가 구매해야 할 카드 팩의 수다. 이후 두 번째 줄에는 총 N개의 나열된 카드에 대한 자연수 식별 번호가 입력으로 주어진다. 가장 왼쪽에 나열된 카드부터 오른쪽에 나열된 카드까지 실제 위치와 같은 순서로 식별 번호가 주어지며, 각 식별 번호는 공백으로 구분되어 있다.

각 카드의 식별번호는 1 이상 50만 이하의 자연수이다.

출력

이벤트의 규칙을 모두 만족하면서 주띵이가 하나의 카드 팩에 구성할 수 있는 카드의 최대 수량을 한 줄에 출력한다.

Small (50점)

  • 1 ≤ N ≤ 100,000
  • M = 1

Large (150점)

  • 1 ≤ N ≤ 100,000
  • 1 ≤ M ≤ N

예제 입력 1

10 1
5 2 5 3 4 1 3 1 2 1

예제 출력 1

5

예제 입력 2

10 1
4 4 4 5 4 4 3 4 5 4

예제 출력 2

3

예제 입력 3

10 3
10 9 7 7 9 8 8 8 2 1

예제 출력 3

3

힌트

3번 예제는 Small 에서는 나오지 않는다.

출처

University > 아주대학교 > 2018 Ajou Programming Contest > Division 1 D번