← 返回题目列表

Codeforces · 1765/F

F. 化学实验室

中文机器翻译题面 查看原题

Monocarp 计划开设一个化学实验室。在第一个月,他将分发某种酸的溶液。

首先,他将与当地一家化工厂签订一些合同。每份合同都为 Monocarp 提供无限量的相同酸溶液的供应。工厂提供$$$n$$$合约选项,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 溶液的浓度为 $$$x_i\%$$$,合同成本为 $$$w_i$$$ 糖节,Monocarp 能够以每升 $$$c_i$$$ 糖节的价格出售。

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$$$ (确切地说是 $$$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$$$ 行的第 $$$i$$$ 包含三个整数 $$$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}$$$ 时,您的答案才会被接受。

示例

输入 #1

2 10
0 10 20
100 15 20

输出 #1

175.000000000000000

输入 #2

2 10
0 100 20
100 150 20

输出 #2

0.000000000000000

输入 #3

6 15
79 5 35
30 13 132
37 3 52
24 2 60
76 18 14
71 17 7

输出 #3

680.125000000000000

输入#4

10 15
46 11 11
4 12 170
69 2 130
2 8 72
82 7 117
100 5 154
38 9 146
97 1 132
0 12 82
53 1 144

输出#4

2379.400000000000000