You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Kiana 喜欢吃甜点，某天她从商店中买回来 $N$ 块切糕与 Tinytree 共同分享，其中第 $i$ 块切糕的大小用一个数 $A_i$ 来表示。

因为每块切糕的风味都不同，所以 Kiana 和 Tinytree 决定将每块切糕都切成两份，两人各选一份品尝。但切切糕是一个自古以来的大难题，经过商议，Kiana 打算执刀来切切糕，而 Tinytree 有 $M$ 次“优先选糕权”，可以获得一些切糕切开后的优先选择权，具体来说，两人按照如下流程进行操作：

步骤一：Kiana 从还没切的切糕中按自己的想法选一块出来，并将其切成两份，其中每份切糕的大小可以是任意正实数，也可以是 $\mathbf{0}$，且两份切糕的大小之和与切之前的大小相同。

步骤二：Tinytree 观察完 Kiana 切出的两份切糕大小后，如果还有“优先选糕权”次数剩余，则可以决定是否消耗 $1$ 次“优先选糕权”来进行优先选择。

步骤三：如果 Tinytree 选择使用“优先选糕权”，则她可以从两份切糕中任选一份，另一份则归 Kiana，如果 Tinytree 选择不使用或者已经用完了 $M$ 次“优先选糕权”，则 Kiana 从两份切糕中任选一份，另一份则归 Tinytree，然后两人回到步骤一，直到所有的切糕都切完。

假设 Kiana 和 Tinytree 都足够聪明，在自己可以操作时总是想办法让自己最终获得的切糕总大小尽可能大，且开始切第一块切糕之前 $N$ 块切糕的大小是两人都已知的，“优先选糕权”不要求全部用完。现在 Kiana 想知道，自己能获得的切糕总大小是多少，由于 Kiana 自己不会算，所以希望你能够帮助她。

输入格式

第一行包含两个正整数 $N$ 和 $M$（$1 \le M \le N \le 2500$），分别表示切糕的总数和 Tinytree 初始时“优先选糕权”的次数。
第二行包含 $N$ 个正整数，其中第 $i$ 个数 $A_i$（$1 \le A_i \le 50000$）表示第 $i$ 块切糕的大小。

输出格式

输出共一行，包含一个实数，表示Kiana 最终能获得的切糕总大小，所有输出精确到小数点后六位。

4 3
4 3 2 1

5.250000

提示

【样例解释 #1】

在这个样例中总共有 $4$ 块切糕，大小分别为 $4,3,2,1$，Tinytree 的“优先选糕权”一共有三次，两人可以按照如下顺序和方式来分配切糕：

第一块：Kiana 选择大小为 $3$ 的切糕，将其切成大小为 $1.25$ 和 $1.75$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1.75$ 的部分，Kiana 目前总共获得大小 $1.25$ 的切糕。

第二块：Kiana 选择大小为 $1$ 的切糕，将其切成大小为 $0$ 和 $1$ 的两部分，Tinytree 不使用“优先选糕权”，Kiana 独得此糕，目前总共获得大小 $2.25$ 的切糕。

第三块：Kiana 选择大小为 $2$ 的切糕，将其切成大小为 $1$ 和 $1$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $1$ 的部分，Kiana 目前总共获得大小 $3.25$ 的切糕。

第四块：Kiana 选择大小为 $4$ 的切糕，将其切成大小为 $2$ 和 $2$ 的两部分，Tinytree 使用一次“优先选糕权”选走 $2$ 的部分，Kiana 目前总共获得大小 $5.25$ 的切糕。

综上所述，该样例输出 $5.250000$，且可以证明在这个方案中如果任意一人改变自己的策略，其获得的切糕总大小不可能变得更大。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。

题解等资源可在 https://github.com/THUSAAC/THUPC2021-pre 查看。