#5736. 「OOI 2026 Day1」赛前焦虑

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day1 T4 「Волнение перед олимпиадой」 / 「Anxiety Before the Olympiad」。

在某次闭门奥林匹克竞赛的入口前，共有 $n$ 名选手在排队，他们被依次编号为 $1$ 到 $n$。已知每分钟都会有一名选手按编号升序进入赛场：第一分钟第一名选手入场，第二分钟第二名选手入场，依此类推。换句话说，第 $i$ 名选手会在入场程序启动后的第 $i$ 分钟进入赛场。

每位选手在赛前都有一定的焦虑程度，这种焦虑程度可以用一个整数（可能是负数）来表示。在入场程序启动前，第 $i$ 名选手的初始焦虑程度为 $a_i$。每过一分钟，选手的焦虑程度会变化 $b_i$。因此，在启动后的第 $x$ 分钟，第 $i$ 名选手的焦虑程度将变为 $a_i + x \cdot b_i$。

亚历山大（Aleksandr）是一位经验丰富的心理学家，他决定在队列中为选手们做心理疏导。亚历山大可以与选手交谈以平复他们的心情。每位选手最多只能被疏导一次。谈话结束后，该选手的焦虑程度会立刻变为 $0$，且此后不再发生变化。亚历山大对第 $i$ 名选手的“工作成效”定义为：交谈时刻该选手的焦虑程度。这意味着，如果亚历山大在启动后的第 $t_i$ 分钟与第 $i$ 名选手谈话，产生的成效即为 $a_i + t_i \cdot b_i$。请注意，如果选手的焦虑程度为负，则工作成效也为负。

亚历山大将按照选手编号从小到大的顺序进行工作。但他并不一定要和所有选手交谈，也就是说，他可能会放弃对排在队伍末尾的一批选手进行疏导。注意，与每位选手的交谈必须在其实际进入赛场之前完成。此外，亚历山大可以在同一分钟内连续与多名选手谈话。更正式地，亚历山大的工作流程如下：

• 亚历山大自行决定对队列中前 $k$ 名选手进行疏导。
• 对于这前 $k$ 名选手中的每一位，设定一个非负整数 $t_i$，表示与之谈话的时刻。$t_i$ 可以为 $0$，表示在第一个选手入场前就已经完成了谈话。
• 对于每个 $1 \leq i \leq k$，必须满足 $t_i < i$，因为谈话必须在选手入场前完成。
• 对于每个 $1 \leq i \leq k-1$，必须满足 $t_i \leq t_{i+1}$，因为亚历山大是按编号顺序开展工作的。
• 亚历山大工作的总成效由以下公式给出：

$$\sum_{i=1}^{k}(a_{i}+t_{i} \cdot b_{i})$$

亚历山大提前制定了一份工作计划。该计划由 $n$ 个整数 $p_1, p_2, \dots, p_n$ 组成。对于每个 $i$，若 $p_i \neq -1$，则意味着在启动后的第 $i$ 分钟（即前 $i$ 名选手刚入场时），亚历山大必须恰好完成了对前 $p_i$ 名选手的疏导工作，且没有开始处理后续选手。在这种情况下，保证满足 $p_i \geq i$。若 $p_i = -1$，则表示在第 $i$ 分钟时，对于已完成疏导的选手数量没有限制。

更正式地说，若 $p_i \neq -1$，则必须满足：

• $p_i \geq i$；
• $t_{p_i} < i$；
• 对于任何满足 $p_i < j \leq k$ 的 $j$，均有 $t_j \geq i$。

请帮助亚历山大确定，在满足所有限制条件的情况下，能够获得的最大总成效是多少。保证解一定存在。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^6)$，表示排队等候入场的选手人数。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(-10^9 \leq a_i \leq 10^9, -10^6 \leq b_i \leq 10^6)$，分别表示第 $i$ 名选手的焦虑参数。

最后一行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ $(i \leq p_i \leq n$ 或 $p_i = -1)$，描述亚历山大的工作计划。

保证对于任意一对 $1 \leq i < j \leq n$，只要 $p_i \neq -1$ 且 $p_j \neq -1$，就一定满足 $p_i \leq p_j$。

输出格式

输出一个整数，表示亚历山大能获得的最大总成效。

可以证明，亚历山大总能找到符合所有附加限制和计划的工作方案。

样例 1

输入

4
3 -6
4 -10
-7 -3
-3 6
3 3 -1 -1

输出

15

在第一个样例中，最优选择是 $k=4$ 且谈话时刻序列 $t=\{0, 0, 0, 3\}$。此时总成效为：

$$(3 + 0 \cdot (-6)) + (4 + 0 \cdot (-3)) + (-7 + 0 \cdot (-3)) + (-3 + 3 \cdot 6) = 3 + 4 - 7 + 15 = 15$$

样例 2

输入

4
-6 -1
-5 14
0 10
-30 2
2 3 -1 -1

输出

-1

在第二个样例中，最优选择是 $k=3$ 且谈话时刻序列 $t=\{0, 0, 1\}$。此时总成效为：

$$(-6 + 0 \cdot (-1)) + (-5 + 0 \cdot 14) + (0 + 1 \cdot 10) = -6 - 5 + 10 = -1$$

样例 3

输入

4
-6 -1
-5 14
0 10
-30 2
-1 -1 -1 -1

输出

23

在第三个样例中，最优选择是 $k=3$ 且谈话时刻序列 $t=\{0, 1, 2\}$。此时总成效为：

$$(-6 + 0 \cdot (-1)) + (-5 + 1 \cdot 14) + (0 + 2 \cdot 10) = -6 + 9 + 20 = 23$$

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	$n$ 限制	$b_i$ 限制	$p_i$ 限制	子任务依赖
$1$	$6$	$n \leq 100$	-	$p_i = -1$	-
$2$	$6$			无	$0, 1$
$3$	$7$	$n \leq 5000$		$p_i = -1$	$1$
$4$	$6$			无	$0, 1, 2, 3$
$5$	$7$	-	$b_i \leq 0$	$p_i = -1$	-
$6$	$5$			无	$5$
$7$	$7$		$b_i \geq 0$	$p_i = -1$	-
$8$	$5$			无	$7$
$9$	$9$		$b_i \leq b_{i+1}$	$p_i = -1$	-
$10$	$8$			无	$9$
$11$	$10$	$n \leq 10^5$	$b_i > 0$ 的数量 $\leq 10$	$p_i = -1$	-
$12$	$7$			无	$11$
$13$	$9$	-		$p_i = -1$	$1, 3, 5, 7, 9, 11$
$14$	$8$			无	$0 - 13$