CF2229G Roadworks

在一个正在建设中的村庄里，有 $n$ 个房屋排成一排，编号从 $1$ 到 $n$。第 $i$ 个房屋的接待能力为 $h_i$。 村庄里有 $n-1$ 条道路，第 $i$ 条道路连接第 $i$ 号房屋和第 $i+1$ 号房屋，并将在第 $d_i$ 天修建完成。最初，没有任何道路被修建。 你从第 $x$ 号房屋出发，将在村庄中从第 $1$ 天待到第 $k$ 天，初始满意度为 $0$。在第 $s$ 天，事件按如下顺序发生： - 所有 $d_i = s$ 的道路会被修建； - 你可以选择移动到相邻的房屋（前提是道路已经修好），也可以选择留在当前房屋； - 你的满意度增加 $h_j$，其中 $j$ 是你当前所在的房屋编号。 请你找出经过 $k$ 天后你能获得的最大满意度。

每个测试用例包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的组数。接下来是每组测试用例的描述。 每组测试用例的第一行包含三个整数 $n$、$k$ 和 $x$（$2 \le n \le 2 \cdot 10^5$，$1 \le k \le 10^9$，$1 \le x \le n$），分别表示房屋数量、天数和起始房屋编号。 第二行包含 $n$ 个整数 $h_1, h_2, \ldots, h_n$（$0 \le h_i \le 10^9$），表示每个房屋的接待能力。 第三行包含 $n-1$ 个整数 $d_1, d_2, \ldots, d_{n-1}$（$1 \le d_i \le k$），表示每条道路修建的天数。 保证所有测试用例的 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一个整数，表示经过 $k$ 天后你可以获得的最大满意度。

在第一个测试用例中，以下是一个最优的移动方案： - 你起始于第 $x=3$ 号房屋，满意度初始为 $0$。 - 第 $1$ 天，还没有道路被修建，你只能停留在第 $3$ 号房屋。此时满意度为 $3$。 - 第 $2$ 天，道路 $3$ 被修建。你移动到第 $4$ 号房屋，并在第 $2$、$3$、$4$、$5$、$6$、$7$ 天都停留在这里。你的满意度变为 $33$。在这期间，道路 $2$ 和 $4$ 也陆续修建完成。 - 第 $8$ 天，你移动回第 $3$ 号房屋。此时满意度为 $36$。 - 第 $9$ 天，你移动到第 $2$ 号房屋。满意度变为 $38$。 - 第 $10$ 天，道路 $1$ 被修建。你移动到第 $1$ 号房屋。满意度变为 $52$。 可以证明，无法获得比 $52$ 更大的满意度。 在第二个测试用例中，你无法在 $8$ 天内到达第 $4$ 号房屋，所以最大满意度为 $0$。 在第三个测试用例中，你可以立刻到达第 $2$ 号房屋，并在此停留 $1\,000\,000\,000$ 天。 由 ChatGPT 5 翻译