#P19011. [Roi2026]分布式系统

[Roi2026]分布式系统

题目描述

一家公司有 nn 台服务器,编号为 11 到 nn。最初,第 ii 台服务器上运行着 aia_i 个服务。

服务器可能发生故障,因此公司为每台服务器指定了一台备用服务器:第 ii 台服务器的备用服务器编号为 pip_i。若 pi=ip_i=i,则第 ii 台服务器具有高可靠性,永远不会发生故障。

不同服务器的备用服务器互不相同。因此,p1,p2,…,pnp_1,p_2,\ldots,p_n 是 11 到 nn 的一个排列。

当第 ii 台服务器发生故障时,它当前运行的全部服务都会转移到第 pip_i 台服务器上。随后,第 ii 台服务器被一台没有运行任何服务的新服务器替换。服务器编号及其备用服务器编号保持不变。服务转移和服务器替换的过程非常快,在此期间不会发生其他故障。

公司准备测试系统的可靠性,使服务器依次发生故障,故障次数不超过 kk。任意两次故障都不会同时发生。

请问,经过不超过 kk 次故障后,同一台服务器上最多可能运行多少个服务?

输入格式

第一行包含两个整数 n,kn,k(1≤k<n≤1051\le k<n\le 10^5),分别表示服务器数量和最多允许的故障次数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai≤1090\le a_i\le 10^9),表示最初各台服务器上运行的服务数量。

第三行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n(1≤pi≤n1\le p_i\le n),表示备用服务器编号。保证 pp 是一个排列。

输出格式

输出一个整数,表示一台服务器上可能运行的最多服务数量。

子任务与评分

子任务 分值 附加限制 必要子任务
1 15 n≤1000, k=1n\le 1000,\ k=1 无
2 27 n≤1000n\le 1000 样例、1
3 21 pi=i mod n+1p_i=i\bmod n+1 无
4 37 无 样例、1、2、3

每个子任务内的全部测试点及必要子任务均通过,才获得该子任务的分数。样例为子任务 0。

样例 1

4 2
6 10 7 9
2 3 4 1
26

样例 2

3 1
1000000000 993 2010
1 3 2
1000000000

样例 3

11 5
3 5 12 7 5 9 2 6 0 9 4
2 8 9 6 5 11 3 1 10 7 4
23

样例说明

样例 1 中,先使服务器 2 故障,其 10 个服务转移到服务器 3,服务器 3 上共有 10+7=1710+7=17 个服务;再使服务器 3 故障,17 个服务转移到服务器 4,使其运行 9+17=269+17=26 个服务。

阶段 服务器 1 服务器 2 服务器 3 服务器 4
最初 6 10 7 9
服务器 2 故障后 0 17
服务器 3 故障后 0 26

若反过来先使服务器 3 故障,再使服务器 2 故障,服务数量依次变为 [6,10,0,16][6,10,0,16] 和 [6,0,10,16][6,0,10,16],最多只有 16 个服务,因此故障顺序会影响答案。

样例 2 中,可以不发生任何故障,服务器 1 上已有 10910^9 个服务。服务器 1 的备用服务器是自身,所以它永远不会故障。使服务器 2 或 3 故障也不会改变答案。