CF2023D Many Games

最近，你获得了一张通往世界上唯一一家真正能赢钱的赌场的稀有门票，你想充分利用这个机会。 该赌场的规则如下： - 赌场一共有 $n$ 个游戏。 - 每个游戏你最多只能玩一次。 - 每个游戏有两个参数：$p_i$（$1 \le p_i \le 100$）和 $w_i$——分别表示该游戏的获胜概率（百分比）和获胜时的奖金。 - 如果你决定玩的任意一个游戏输了，那么你将一无所获（即使你赢了其他游戏也得不到奖金）。 你需要提前选择一组要参与的游戏，使得你的期望奖金最大。 具体来说，如果你选择了编号为 $i_1 < i_2 < \ldots < i_k$ 的游戏，你全部获胜的概率为 $\prod\limits_{j=1}^k \frac{p_{i_j}}{100}$，此时你获得的奖金为 $\sum\limits_{j=1}^k w_{i_j}$。 也就是说，你的期望奖金为 $\left(\prod\limits_{j=1}^k \frac{p_{i_j}}{100}\right) \cdot \left(\sum\limits_{j=1}^k w_{i_j}\right)$。 为了避免破产，赌场老板对每个单独游戏的期望奖金做了限制。对于所有 $i$（$1 \le i \le n$），都有 $w_i \cdot p_i \le 2 \cdot 10^5$。 你的任务是，选择赌场中的某些游戏，使得可以获得的期望奖金最大。

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示可玩的游戏数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $p_i$ 和 $w_i$（$1 \leq p_i \leq 100$，$1 \leq w_i, p_i \cdot w_i \leq 2 \cdot 10^5$），分别表示第 $i$ 个游戏的获胜概率和奖金。

输出一个实数，表示通过选择某些游戏可以获得的最大期望奖金。 如果你的答案与标准答案的相对或绝对误差不超过 $10^{-6}$，则视为正确。形式化地说，若你的答案为 $a$，标准答案为 $b$，则当 $\frac{|a-b|}{\max(b, 1)} \le 10^{-6}$ 时，答案被接受。

在第一个样例中，你可以选择第一个和第三个游戏。此时期望奖金为 $\left(\frac{p_1}{100}\cdot \frac{p_3}{100}\right) \cdot (w_1 + w_3) = \left(\frac{80}{100}\cdot \frac{50}{100}\right) \cdot (80 + 200) = 112$。 在第二个样例中，你可以选择第一个和第二个游戏。此时期望奖金为 $\left(\frac{p_1}{100}\cdot \frac{p_2}{100}\right) \cdot (w_1 + w_2) = \left(\frac{100}{100}\cdot \frac{100}{100}\right) \cdot (1 + 1) = 2$。 在第三个样例中，你只能选择第二个游戏。此时期望奖金为 $\frac{p_2}{100} \cdot w_2 = \frac{2}{100} \cdot 1000 = 20$。 由 ChatGPT 4.1 翻译