Computer Game
Contest: Codeforces Round 518 (Div. 1) [Thanks, Mail.Ru!]
Difficulty rating: 3100
Tags: dp, greedy, math, probabilities

Ivan plays some computer game. There are $$$n$$$ quests in the game. Each quest can be upgraded once, this increases the reward for its completion. Each quest has $$$3$$$ parameters $$$a_{i}$$$, $$$b_{i}$$$, $$$p_{i}$$$: reward for completing quest before upgrade, reward for completing quest after upgrade ($$$a_{i} < b_{i}$$$) and probability of successful completing the quest.

Each second Ivan can try to complete one quest and he will succeed with probability $$$p_{i}$$$. In case of success Ivan will get the reward and opportunity to upgrade any one quest (not necessary the one he just completed). In case of failure he gets nothing. Quests do not vanish after completing.

Ivan has $$$t$$$ seconds. He wants to maximize expected value of his total gain after $$$t$$$ seconds. Help him to calculate this value.

Input format:
First line contains $$$2$$$ integers $$$n$$$ ($$$ 1 \le n \le 10^{5}$$$) and $$$t$$$ ($$$ 1 \le t \le 10^{10}$$$) — number of quests and total time.

Following $$$n$$$ lines contain description of quests. Each description is $$$3$$$ numbers $$$a_{i}$$$ $$$b_{i}$$$ $$$p_{i}$$$ ($$$1 \le a_{i} < b_{i} \le 10^{8}$$$, $$$0 < p_{i} < 1$$$) — reward for completing quest before upgrade, reward for completing quest after upgrade and probability of successful completing of quest. $$$a_{i}$$$ and $$$b_{i}$$$ are integers. All probabilities are given with at most $$$9$$$ decimal places.

Output format:
Print the expected value.

Your answer will be accepted if 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 considered correct if $$$\frac{|a-b|}{max⁡(b, \,\, 1)} \le 10^{-6}$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3 2
3 1000 0.5
1 2 0.48
3 20 0.3

Example output:
252.2500000000000

Example input:
2 2
1 1000 0.1
2 3 0.2

Example output:
20.7200000000000

Editorial:
Let's denote $$$max(b_{i} p_{i})$$$ as $$$M$$$. Independent of our strategy we cannot get more than $$$M$$$ in one second (in expected value). But if we could upgrade one quest, we would upgrade the quest which maximizes $$$b_{i} p_{i}$$$ and then try to complete only this quest each second, thus getting $$$+M$$$ to expected value each second. Therefore, our strategy looks like this: try to complete quests in some order, once we complete one quest we will always get $$$+M$$$ to expected value each second.
This observation leads to DP solution. Once we have one quest completed we already know what we will get, so interesting states are only those in which no quests are completed yet. Then it is not important what quests we tried to complete before, the only important parameter is remaining time.
$$$dp_{t+1} = max(p_{i} (a_{i} + tM) + (1 - p_{i}) dp_{t})$$$.
If we succeed then we will get $$$a_{i}$$$ as a reward and for remaining $$$t$$$ seconds we will get $$$M$$$ each second, otherwise we get nothing and now only $$$t$$$ seconds left. This solution works in $$$O(nT)$$$ time which is too slow.
We can slightly rewrite the formula for transition: $$$dp_{t+1} = max(p_{i} (a_{i} + tM) + (1 - p_{i}) dp_{t}) = dp_{t} + max(p_{i} (tM - dp_{t}) + p_{i} a_{i})$$$.
Now we can see that we take maximum value of functions $$$p_{i} \cdot x + p_{i} a_{i}$$$ in point $$$x_{t} = tM - dp_{t}$$$. We can build convex hull on these lines thus getting $$$O(n \log n + T \log n)$$$ solution.
But that's not all. We can actually prove that $$$x_{t} \le x_{t+1}$$$ or, after some substitutions and simplifications, $$$dp_{t+1} - dp_{t} \le M$$$. This we will prove by actual meaning of $$$dp_{t}$$$. Take optimal solution for $$$t+1$$$ seconds and do the same for $$$t$$$ seconds, except that we don't have last second, so we will just drop our action. But we can't gain more than $$$M$$$ in one second, so this drop cannot decrease answer more than $$$M$$$. Thus the inequality is proven.
This means that we only move right along over convex hull, so for each line there will be consecutive seconds in which we are using that line. If we could somehow determine these segments of times for each line and learn how to make many DP transitions at once then we would solve the problem even faster.
Let's start with learning how to make many DP transitions (when we are staying on one line for the whole time). It is more clear using first formula for DP transition: $$$dp_{t+1} = p_{i} (a_{i} + tM) + (1 - p_{i}) dp_{t}$$$ (we don't have max now because we already know which line to use). We can see that to get vector $$$\begin{pmatrix} dp_{t+1} & t+1 & 1 \end{pmatrix}^{T}$$$ from vector $$$\begin{pmatrix} dp_{t} & t & 1 \end{pmatrix}^{T}$$$ we can apply linear transformation i.e. multiply by some matrix:
$$$\begin{pmatrix} dp_{t+1} \\ t+1 \\ 1 \end{pmatrix} = \begin{pmatrix} 1 - p_{i} & p_{i} M & p_{i} a_{i} \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} dp_{t} \\ t \\ 1 \end{pmatrix} $$$
To apply it $$$k$$$ times just use binary exponentiation to get $$$k$$$-th power of transition matrix.
To determine how long we actually have to stay on given line we will use binary search on answer. We know for which value of $$$x$$$ we should move to the next line and we know that $$$x$$$ increases with each second, so we can try to stay on given line for some time and see if we should actually change the line.
This is already $$$O(n (\log n + \log ^{2} T) )$$$ solution, but we can improve it one more time by making binary exponentiation and binary search on power for this exponentiation at the same time.
Final complexity is $$$O(n (\log n + \log T) )$$$