CF1067D Computer Game

Ivan 玩一个电脑游戏。游戏中有 $n$ 个任务。每个任务都可以升级一次，升级后完成该任务的奖励会增加。每个任务有 $3$ 个参数 $a_{i}$、$b_{i}$、$p_{i}$：升级前完成任务的奖励、升级后完成任务的奖励（$a_{i} < b_{i}$），以及成功完成该任务的概率。 每秒 Ivan 可以尝试完成一个任务，他成功的概率为 $p_{i}$。若成功，他将获得奖励，并可以选择升级任意一个任务（不一定是刚刚完成的那个）。若失败，则什么也得不到。任务在完成后不会消失。 Ivan 有 $t$ 秒时间。他希望在 $t$ 秒后获得的总期望收益最大。请帮助他计算这个期望值。

第一行包含两个整数 $n$（$1 \le n \le 10^{5}$）和 $t$（$1 \le t \le 10^{10}$），分别表示任务数量和总时间。 接下来的 $n$ 行，每行描述一个任务。每行包含 $3$ 个数 $a_{i}$、$b_{i}$、$p_{i}$（$1 \le a_{i} < b_{i} \le 10^{8}$，$0 < p_{i} < 1$），分别表示升级前完成该任务的奖励、升级后完成该任务的奖励，以及成功完成该任务的概率。$a_{i}$ 和 $b_{i}$ 是整数。所有概率最多保留 $9$ 位小数。

输出期望值。 如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。形式化地，设你的答案为 $a$，标准答案为 $b$，当 $\frac{|a-b|}{\max(b,\,\, 1)} \le 10^{-6}$ 时，答案被认为是正确的。

由 ChatGPT 4.1 翻译