P6674 [CCO 2019] Card Scoring

您下载了一款卡牌游戏。 这款游戏的规则如下： 1. 共有 $n$ 张牌，每张牌有一个种类，种类共有 $n$ 种，用 $1\sim n$ 的整数表示，同时还有一个评分参数 $k$。 2. 您按顺序摸这 $n$ 张牌，每张牌有两种选择，拿走或不要。 3. 在任何情况下，您都要保证，您的手上的牌里只能有一种种类的牌。 4. 在摸完牌后，您可以选择结算您的分数。分数的计算方式为：若您有 $x$ 张牌，您会获得 $x^{\frac{1}{2}k}$ 的分数。结算完分数后，您的手牌将被清空，且您的总分会进行累加。 现在，您决定计算，这款手牌游戏可能取得的总分的最大值是多少。

第一行为两个整数 $k,n$。 接下来 $n$ 行，一行一个数，表示牌的种类。

仅一行一个实数，表示可能取得的最高分。

#### 样例解释 #### 样例 1 解释 最优方案为不放弃每一张牌，摸完第一、三、五张牌后计分，分数为：$1^{1.5}+2^{1.5}+2^{1.5}\approx 6.656854249$。 #### 样例 2 解释 最优方案有两种，一种是弃掉种类为 $2$ 的牌，在第五张牌摸完后计分，共得 $3^2=9$ 分。 另一种同样例一，分数为：$1^{2}+2^{2}+2^{2}=9$。 #### SPJ 计分标准 设您的答案为 $p$，标准答案为 $q$，若 $\frac{|p-q|}{q}\le 10^{-6}$，您可以 AC。 #### 数据范围及限制 对于 $100\%$ 的数据，保证 $2\le k\le 4$，$1\le n\le 10^6$，牌的种类 $\in \{1,n\}$。 | 子任务 | $n\le $ | $k=$ | 分值 | | - | - | - | - | | 1 | $20$ | 无特殊限制 | $16$ | 2 | $300$ | $2$ | $4$ | 3 | $300$ | 无特殊限制 | $20$ | 4 | $5\times 10^3$ | 无特殊限制 | $12$ | 5 | 无特殊限制 | $4$ | $12$ | 6 | 无特殊限制 | 无特殊限制 | $36$ #### 说明 本题译自 [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。