시간 제한메모리 제한제출정답맞힌 사람정답 비율
6 초 512 MB2512736.842%

문제

You have a deck of n cards. Each card has a value: the card values lie between 1 to n, possibly with some repeated values, and possibly with some values never occurring. There is also a special integer k that will be used in calculating a score.

You are playing a game that involves drawing all the cards from the deck one by one. When you draw a card, you may choose to either add it to your hand or discard it. You may also score your entire hand at any time. When you score a hand with x cards, you gain xk/2 points and then you discard all cards in that hand. At any point in time, your hand may only contain cards with the same number on them. Given the initial order of the cards in the deck, what is the maximum possible score you can obtain?

입력

The first line of input will contain two space-separated integers k and n. The value k is the value used in the expression xk/2 to compute points (2 ≤ k ≤ 4). The value n is the number of cards in the deck (1 ≤ n ≤ 1 000 000). The next n lines contain one integer per line, where the ith of these n lines is the i th card from the top of the deck (1 ≤ i ≤ n).

출력

Output one floating point number, which is the maximum score you can obtain from playing optimally. If your answer is p and the correct answer is q, then your answer will be considered correct if |p - q| / q ≤ 10-6.

예제 입력 1

3 5
1
2
2
1
1

예제 출력 1

6.656854249

We know the cards we draw in order are [1, 2, 2, 1, 1] and that discarding a hand of x cards gives us a score of x1.5.

The optimal strategy is to draw one card, score that hand, draw two cards, score that hand, and draw two more cards and score that hand. This strategy gives a score of 11.5 + 21.5 + 21.5 ≈ 6.656854249.

예제 입력 2

4 5
1
2
2
1
1

예제 출력 2

9.0

We know the cards we draw in order are [1, 2, 2, 1, 1] and that scoring a hand of x cards gives us a score of x2.

An optimal strategy is to take all cards with 1, and score them all at the end. This strategy gives a score of 3 2 = 9. Note that taking the first card and scoring, then taking the next two cards and scoring, and then taking the final two cards and scoring, will also yield 12 + 22 + 22 = 9.

출처

Olympiad > Canadian Computing Competition & Olympiad > 2019 > CCO 2019 4번

  • 문제의 오타를 찾은 사람: 79brue