A15472. 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.
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.
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}$ .
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.400000000000000