CF1765F Chemistry Lab

Monocarp 计划开设一个化学实验室。在第一个月，他将分发某种酸的溶液。 首先，他会与当地一家化学工厂签订一些合同。每份合同都能为 Monocarp 提供无限量的某种酸溶液。工厂提供 $n$ 种合同选择，编号从 $1$ 到 $n$。第 $i$ 种溶液的浓度为 $x_i\%$，签订该合同的费用为 $w_i$ burles，Monocarp 可以以每升 $c_i$ burles 的价格出售。 Monocarp 预计在第一个月会有 $k$ 位顾客。每位顾客会购买一升 $y\%$ 浓度的溶液，其中 $y$ 是从 $0$ 到 $100$ 的实数，且每位顾客独立且均匀随机选择。更正式地说，数值 $y$ 小于等于某个 $t$ 的概率为 $P(y \le t) = \frac{t}{100}$。 Monocarp 可以以任意比例混合他与工厂签订合同获得的溶液。更正式地说，如果他签订了 $m$ 份浓度分别为 $x_1, x_2, \dots, x_m$ 的合同，那么对于这些溶液，他可以选择它们的体积 $a_1, a_2, \dots, a_m$，使得 $\sum \limits_{i=1}^{m} a_i = 1$（因为每位顾客只需要一升溶液）。 混合后溶液的浓度为 $\sum \limits_{i=1}^{m} x_i \cdot a_i$。混合后溶液的售价为 $\sum \limits_{i=1}^{m} c_i \cdot a_i$。 如果 Monocarp 能够获得浓度为 $y\%$ 的溶液，他会在满足条件的情况下尽量提高售价（即对顾客来说的价格）。否则，顾客会离开且本次售价视为 $0$。 Monocarp 想要选择与工厂签订哪些合同（可以不签，也可以全签），以使期望利润最大化——即所有 $k$ 位顾客购买溶液的期望总售价减去签订合同的总费用。 请输出 Monocarp 能获得的最大期望利润。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 5000$；$1 \le k \le 10^5$），分别表示工厂提供的合同数量和顾客数量。 接下来的 $n$ 行，每行包含三个整数 $x_i, w_i, c_i$（$0 \le x_i \le 100$；$1 \le w_i \le 10^9$；$1 \le c_i \le 10^5$），分别表示第 $i$ 份合同的溶液浓度、签订该合同的费用和每升售价。

输出一个实数，表示 Monocarp 能获得的最大期望利润。 如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。 更正式地说，设你的答案为 $a$，标准答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，答案被接受。

由 ChatGPT 4.1 翻译