P16550 [ICPC 2026 LAC] Dropshipping

Drew P. Shipper 收到了 $N$ 个在名为 EvenBuy 的商店购买产品的客户请求，该商店所有产品的价格均为偶数。为了完成第 $i$ 个请求，Drew 必须在 EvenBuy 购买一款价格为 $A_i$ 的特定产品，并且 Drew 已经向客户收取了这笔款项。 Drew 这样做是为了盈利，这依赖于 EvenBuy 提供的一项忠诚计划：Drew 每完成 $X$ 次全价购买后，他在下一次单次购买中可获得 $50\%$ 的折扣。这次折扣购买不计入获得下一次折扣所需的 $X$ 次全价购买中。因为 Drew 的客户已提前向他支付了全价，所以每当他以折扣价购买商品时，他就将折扣金额作为自己的利润留存。 Drew 可以决定他在 EvenBuy 的购买顺序，以最大化自己的总利润。然而，交付时间与购买顺序直接相关，为避免客户投诉，他不能过度推迟某次购买。具体来说，Drew 必须在他于 EvenBuy 的前 $i+K$ 次购买之内完成第 $i$ 个请求。 你的任务是找出 Drew 能够获得的最大总利润。每次购买恰好完成一个请求，且每个请求必须恰好被完成一次。

第一行包含三个整数 $N$、$X$（$1 \le N, X \le 2 \times 10^5$）和 $K$（$0 \le K \le 2 \times 10^5$），分别表示客户请求的数量、获取一次 $50\%$ 折扣所需的全价购买次数，以及交付限制（第 $i$ 个请求必须在前 $i + K$ 次购买内完成）。 第二行包含 $N$ 个偶数整数 $A_1, A_2, \ldots, A_N$（$2 \le A_i \le 10^9$），表示所请求产品的价格。

输出一行一个整数，表示 Drew 能够获得的最大总利润。

**样例 1 解释：** 由于 $K=0$，第 $i$ 个请求必须恰好为第 $i$ 次购买。因为只有第二次购买是折扣购买，Drew 只能获得 $4/2 = 2$ 的利润。 **样例 2 解释：** 现在第 $i$ 个请求必须在前 $i + 1$ 次购买内完成。因此合法的购买顺序有 $[6, 4, 14]$、$[6, 14, 4]$、$[4, 6, 14]$ 和 $[14, 6, 4]$。顺序 $[6, 14, 4]$ 是最优的，因为 Drew 可以在第二次购买中获得 $14/2 = 7$ 的利润。 翻译由 DeepSeek V4 Pro 完成