309963: CF1765F. Chemistry Lab
Memory Limit：512 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Chemistry Lab
题目描述
Monocarp is planning on opening a chemistry lab. During the first month, he's going to distribute solutions of a certain acid. First, he will sign some contracts with a local chemistry factory. Each contract provides Monocarp with an unlimited supply of some solution of the same acid. The factory provides $ n $ contract options, numbered from $ 1 $ to $ n $ . The $ i $ -th solution has a concentration of $ x_i\% $ , the contract costs $ w_i $ burles, and Monocarp will be able to sell it for $ c_i $ burles per liter. Monocarp is expecting $ k $ customers during the first month. Each customer will buy a liter of a $ y\% $ -solution, where $ y $ is a real number chosen uniformly at random from $ 0 $ to $ 100 $ independently for each customer. More formally, the probability of number $ y $ being less than or equal to some $ t $ is $ P(y \le t) = \frac{t}{100} $ . Monocarp can mix the solution that he signed the contracts with the factory for, at any ratio. More formally, if he has contracts for $ m $ solutions with concentrations $ x_1, x_2, \dots, x_m $ , then, for these solutions, he picks their volumes $ a_1, a_2, \dots, a_m $ so that $ \sum \limits_{i=1}^{m} a_i = 1 $ (exactly $ 1 $ since each customer wants exactly one liter of a certain solution). The concentration of the resulting solution is $ \sum \limits_{i=1}^{m} x_i \cdot a_i $ . The price of the resulting solution is $ \sum \limits_{i=1}^{m} c_i \cdot a_i $ . If Monocarp can obtain a solution of concentration $ y\% $ , then he will do it while maximizing its price (the cost for the customer). Otherwise, the customer leaves without buying anything, and the price is considered equal to $ 0 $ . Monocarp wants to sign some contracts with a factory (possibly, none or all of them) so that the expected profit is maximized — the expected total price of the sold solutions for all $ k $ customers minus the total cost of signing the contracts from the factory. Print the maximum expected profit Monocarp can achieve.输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 5000 $ ; $ 1 \le k \le 10^5 $ ) — the number of contracts the factory provides and the number of customers. The $ i $ -th of the next $ n $ lines contains three integers $ x_i, w_i $ and $ c_i $ ( $ 0 \le x_i \le 100 $ ; $ 1 \le w_i \le 10^9 $ ; $ 1 \le c_i \le 10^5 $ ) — the concentration of the solution, the cost of the contract and the cost per liter for the customer, for the $ i $ -th contract.
输出格式
Print a single real number — the maximum expected profit Monocarp can achieve. Your answer is considered correct if its absolute or relative error does not exceed $ 10^{-6} $ . Formally, let your answer be $ a $ , and the jury's answer be $ b $ . Your answer is accepted if and only if $ \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.400000000000000Input
暂时还没有翻译
Output
**化学实验室**
**题目描述**
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
```**化学实验室** **题目描述** 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 ```
**题目描述**
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
```**化学实验室** **题目描述** 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 ```