该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

任务排序

题目描述

在一个任务调度系统中，有 $n$ 个任务需要被依次执行。 每个任务 $i$ 有三个属性：

• $a_i$：该任务单独执行时获得的基础收益
• $t_i$：该任务的执行时长
• $x_i$：该任务对后续任务产生的干扰强度

系统发现如下规律：

如果任务 $i$ 排在任务 $j$ 前面执行，那么任务 $j$ 的收益会减少 $\frac{x_i}{t_i \times t_j}$

一个任务只会受到所有排在它前面的任务的干扰影响，所有干扰损失会累加。

你的任务是：合理安排任务执行顺序，使得最终获得的总收益最大。

输入格式

第一行一个整数 $n$，表示任务数量。

接下来 $n$ 行，每行三个整数：$a_i,\ t_i,\ x_i$ 表示第 $i$ 个任务的属性。

输出格式

输出一个实数，表示最大总收益。

答案与标准答案误差不超过 $10^{-6}$ 即视为正确。

3
10 2 4
8 3 6
7 1 5

20.6666666667

样例解释

经过计算，最优顺序为：任务 1 → 任务 3 → 任务 2。

总收益为：

$$8 + 10 + 7 - \frac{4}{2 \times 1}- \frac{4}{2 \times 3}- \frac{5}{1 \times 3} = 25 - 2 - 0.6666666666 - 1.6666666666 = 20.6666666667$$

数据范围

对于 $20\%$ 的数据满足 $1 \le n \le 8$。

对于 $60\%$ 的数据满足 $1 \le n \le 1000$。

对于 $100\%$ 的数据满足 $1 \le n \le 2 \times 10^5,1 \le a_i, t_i, x_i \le 10^6$。