P12933 [NOISG 2020 Prelim] Solar Storm

Squeaky 老鼠是宇宙飞船的船长，正在执行探索太阳系边界的任务。飞船呈长条状，沿着飞船的长度方向有一条笔直的通道，$N$ 个舱室连接在通道的不同位置。舱室从左到右编号为 $1$ 到 $N$，相邻舱室之间的距离不一定相等。 每个舱室 $i$（$1 \leq i \leq N$）中都有重要的设备，用于支持飞船的运行，设备的重要性用正整数 $v_i$ 表示。相邻舱室之间有电缆连接，设备可以通过其他舱室远程控制。 然而，一场太阳风暴即将袭击飞船！太阳风暴会释放大量带电粒子，如果不加保护，将会损坏飞船上的设备。 幸运的是，船员随船携带了 $S$ 个防护盾。每个防护盾可以放置在任意舱室，也可以选择不使用。每个防护盾能在其所在位置产生磁场，保护半径为 $K$ 米，半径范围内的所有舱室设备都能被保护（包括防护盾所在的舱室）。 需要注意： - 通道本身无需保护，因为电缆不受带电粒子的影响； - 为了方便后续操作，Squeaky 希望所有被保护的舱室之间可以相互控制设备； - 具体而言，如果两个被保护的舱室之间存在未被保护的舱室，则无法相互控制设备，这是不允许的。 请你作为工程师，帮助 Squeaky 确定防护盾的最优放置方案，最大化被保护舱室的重要性总和，并保证控制连通性。

第一行三个整数 $N,\ S,\ K$，分别表示舱室数量、防护盾数量、防护盾的保护半径（单位：米）。 第二行 $N - 1$ 个整数 $d_i$，第 $i$ 个舱室与第 $i+1$ 个舱室之间的距离。 第三行 $N$ 个整数 $v_i$，第 $i$ 个舱室的重要性。

第一行一个整数 $T$，表示实际使用的防护盾数量，$0 \leq T \leq S$。 第二行 $T$ 个整数，表示放置防护盾的舱室编号，顺序不限。若有多种方案都能达到最优，输出任意一种均可。

【样例解释】 对于样例 #1： 飞船的结构如下： 部署两个防护盾的最优位置是在第 $3$ 和第 $5$ 个舱室。 第 $3$ 个舱室的防护盾将保护第 $2, 3, 4$ 个舱室；第 $5$ 个舱室的防护盾将保护第 $5$ 个舱室。 注意，舱室 $4$ 和 $5$ 之间的通道没有完全被保护，这是允许的，因为通道上的电缆不会受到损害。 请注意，如果将两个防护盾部署在第 $3$ 和第 $6$ 个舱室，这不是一个合法方案，因为第 $5$ 个舱室会被太阳风暴损坏，导致第 $6$ 个舱室的船员无法控制第 $2, 3, 4$ 个舱室的设备。 对于样例 #2： 飞船的结构与样例 $1$ 相同，但防护盾的半径更大。 在第 $4$ 个舱室部署一个防护盾足以保护所有舱室。 注意，还有许多其他可接受的方案。 其他一些可选方案包括： - 仅在第 $3$ 个舱室部署一个防护盾； - 分别在第 $3$ 和第 $5$ 个舱室各部署一个防护盾； - 在第 $3$ 个舱室部署两个防护盾。 所有能够最大化被保护舱室总重要性的合法方案都会被接受。 对于样例 #3： 飞船的结构与样例 $1$ 相同。 在第 $5$ 个舱室部署防护盾可以保护第 $5$ 和第 $6$ 个舱室，这是最优方案。 注意，同样也可以选择将防护盾部署在第 $6$ 个舱室，这也是最优的。 对于样例 #4： 最优方案是在第 $6$ 个舱室部署防护盾，这将保护第 $4, 5, 6, 7, 8$ 个舱室。 注意，同样也可以选择在第 $7$ 个舱室部署防护盾，这也是最优的。 对于样例 #5： 部署三个防护盾的最优位置是第 $3, 4, 5$ 个舱室。 【数据范围】 - $1 \leq S \leq N \leq 10^6$ - $1 \leq K \leq 10^{12}$ - $1 \leq d_i \leq 10^6$ - $1 \leq v_i \leq 10^6$ | 子任务编号 | 分值 | 附加限制 | | :--------: | :--: | :----------------------------------------------------------: | | $1$ | $10$ | $S = 1,\ N \leq 10^4,\ K \leq 10^9,\ d_i \leq 10^5,\ v_i \leq 10^5$ | | $2$ | $7$ | $S = 1,\ d_i = 1$ | | $3$ | $11$ | $S = 1$ | | $4$ | $8$ | $K = 1,\ d_i = 2$ | | $5$ | $18$ | $N \leq 10^4$ | | $6$ | $16$ | $S \leq 50$ | | $7$ | $30$ | 无附加限制 |