CF277D Google Code Jam

许多同学一定对 Google Code Jam 赛制比较熟悉。让我们来回顾一下与本题相关的几个关键点：比赛期间，选手们被要求解决若干道题，每道题分为两个子问题：一个是数据范围较小的简单部分（Small input），一个是数据范围较大的困难部分（Large input）。只有当你已经解决了该题目的 Small input 后，才可以提交 Large input 的解答。题目的解答顺序没有其它限制。选手可以先解决 Small input，再去做另一题，之后再回来做该题的 Large input。每个输入的解答（一般不同题目得分不同）会给予选手一定的分数。只有所有测试点完全通过，才计分。选手提交 Small input 后会立即得到结果，而 Large input 的结果则要等比赛结束才会公布。在比赛最终结果中，选手按照分数降序排序；如果分数相同，则按照时间惩罚升序排序。根据 Google Code Jam 规则，时间惩罚为最后一个通过的解答的提交时间。 Vasya 决定在新一轮比赛中尝试一种新策略。比赛一开始，他很快读完所有题，并且准确地评估了解决每道题所需的时间。具体来说，对于每一道题 Vasya 都已知如下五个数值： - 解决第 $i$ 道题的 Small input 可得 $scoreSmall_{i}$ 分，解决 Large input 可再得 $scoreLarge_{i}$ 分。即完成该题最多可得 $scoreSmall_{i}+scoreLarge_{i}$ 分。 - Vasya 解决第 $i$ 道题 Small input 需要恰好 $timeSmall_{i}$ 分钟。再将代码优化为 Large input 解法，则需继续花 $timeLarge_{i}$ 分钟。 - Vasya 经验丰富，所有 Small input 都能一次通过。但对于 Large input，在比赛最终评测时，有 $probFail_{i}$ 的概率评为错误结果。请注意，这样的解答不计入得分和时间惩罚。 比赛总时长为 $t$ 分钟。读题和提交解答所用时间可视为零。Vasya 允许刚好在比赛结束时提交解答。 Vasya 想选择一组输入以及它们的解题顺序，使得获得分数的期望最大；如果有多种方案能获得相同的期望分数，则需要最小化时间惩罚的期望。请帮助 Vasya 完成此任务。

第一行包含两个整数 $n$ 和 $t$（$1 \leq n \leq 1000, 1 \leq t \leq 1560$）。接下来 $n$ 行，每行包含 5 个数：$scoreSmall_{i}, scoreLarge_{i}, timeSmall_{i}, timeLarge_{i}, probFail_{i}$（$1 \leq scoreSmall_{i}, scoreLarge_{i} \leq 10^9, 1 \leq timeSmall_{i}, timeLarge_{i} \leq 1560, 0 \leq probFail_{i} \leq 1$ ）。 $probFail_{i}$ 是一个实数，精确到小数点后最多 6 位。其它所有数均为整数。

输出两个实数，分别为最大可能的期望总得分和对应的最小时间惩罚期望。如果绝对误差或相对误差不超过 $10^{-9}$，就视为正确。

在第一个样例中，一种最优的解题顺序是： 1. 第三题的 Small input。 2. 第一题的 Small input。 3. 第三题的 Large input。 4. 第一题的 Large input。 注意，如果你用第二题的 Small input 替换掉第三题的两个输入，总期望分数相同，但时间罚分期望会更大（为 $38$）。 由 ChatGPT 5 翻译