P6674 [CCO 2019] Card Scoring

You downloaded a card game. The rules of this game are as follows: 1. There are $n$ cards in total. Each card has a type. There are $n$ possible types, represented by integers $1 \sim n$. There is also a scoring parameter $k$. 2. You draw these $n$ cards in order. For each card, you have two choices: take it or discard it. 3. In all cases, you must ensure that the cards in your hand contain only one type. 4. After finishing drawing cards, you may choose to score your hand. The score is calculated as follows: if you have $x$ cards, you gain $x^{\frac{1}{2}k}$ points. After scoring, your hand will be cleared, and the points will be added to your total score. Now, you want to compute the maximum possible total score in this card game.

The first line contains two integers $k, n$. The next $n$ lines each contain one integer, representing the type of a card.

Output one real number in a single line, representing the maximum score that can be achieved.

#### Sample Explanation #### Sample 1 Explanation The best strategy is to discard no cards, and score after drawing the 1st, 3rd, and 5th cards. The score is $1^{1.5} + 2^{1.5} + 2^{1.5} \approx 6.656854249$. #### Sample 2 Explanation There are two optimal strategies. One is to discard the cards of type $2$, and score after drawing the 5th card, gaining $3^2 = 9$ points in total. The other is the same as Sample 1, with score $1^{2} + 2^{2} + 2^{2} = 9$. #### SPJ Scoring Standard Let your answer be $p$ and the standard answer be $q$. If $\frac{|p-q|}{q} \le 10^{-6}$, you will be accepted. #### Constraints and Limits For $100\%$ of the testdata, it is guaranteed that $2 \le k \le 4$, $1 \le n \le 10^6$, and the card type $\in \{1,n\}$. | Subtask | $n \le$ | $k = $ | Points | | - | - | - | - | | 1 | $20$ | No special restrictions | $16$ | | 2 | $300$ | $2$ | $4$ | | 3 | $300$ | No special restrictions | $20$ | | 4 | $5 \times 10^3$ | No special restrictions | $12$ | | 5 | No special restrictions | $4$ | $12$ | | 6 | No special restrictions | No special restrictions | $36$ | #### Notes This problem is translated from [Canadian Computing Olympiad 2019](https://cemc.math.uwaterloo.ca/contests/computing/2019/index.html) [Day 2](https://cemc.math.uwaterloo.ca/contests/computing/2019/stage%202/day2.pdf) T1 Card Scoring. Translated by ChatGPT 5