CF1765F.Chemistry Lab
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 xi% , the contract costs wi burles, and Monocarp will be able to sell it for ci 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≤t)=100t .
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 x1,x2,…,xm , then, for these solutions, he picks their volumes a1,a2,…,am so that i=1∑mai=1 (exactly 1 since each customer wants exactly one liter of a certain solution).
The concentration of the resulting solution is i=1∑mxi⋅ai . The price of the resulting solution is i=1∑mci⋅ai .
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≤n≤5000 ; 1≤k≤105 ) — the number of contracts the factory provides and the number of customers.
The i -th of the next n lines contains three integers xi,wi and ci ( 0≤xi≤100 ; 1≤wi≤109 ; 1≤ci≤105 ) — 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 max(1,∣b∣)∣a−b∣≤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