P10051 [CCO 2022] Rainy Markets

## 由于数据包过大，本题无法上传全部数据。

有 $N$ 个公交车站，标号为 $1, \ldots, N$。第 $i$ 个公交车站可以容纳 $B_{i}$ 个人。 对于每个 $i \in\{1, \ldots, N-1\}$，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_{i}$ 把雨伞出售，每把雨伞的价格为 $1$。 现在，有 $P_{i}$ 个人在第 $i$ 个市场里面，所有的公交车站都是空的。 突然，天开始下雨，市场 $i$ 的每个人都必须在三种方案中选择一种： - 去公交车站 $i$； - 去公交车站 $i+1$； - 留下来买一把雨伞。 如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。 你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格分隔的整数 $B_{i}\ (1 \leq i \leq N)$，表示公交车站 $i$ 的容量。 第三行包含 $N-1$ 个用空格分隔的整数 $P_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 的人数。 第四行包含 $N-1$ 个用空格分隔的整数 $U_{i}\ (1 \leq i \leq N-1)$，表示市场 $i$ 出售的雨伞的数量。

如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行： - 第一行输出一行 `YES`。 - 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。 - 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i\ (1\leq i \leq N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。 如果有多种合法方案，你可以输出任意一种。 否则，输出一行 `NO`。

## 样例 1 解释 公交车站有 $35$ 个空位，没有雨伞出售，但市场有 $40$ 个人，所以答案是 `NO`。 ## 样例 2 解释 市场 $1$ 中的 $10$ 个人会去公交车站 $1$，没有人会买雨伞，$10$ 个人会去公交车站 $2$。 市场 $2$ 中的 $5$ 个人会去公交车站 $2$，$5$ 个人会留下来买雨伞，$10$ 个人会移动到公交车站 $3$。 总共购买了 $5$ 把雨伞，花费了 $5$。 ## 数据范围 对于所有的数据，有 $2 \leq N \leq 10^{6}$，$0 \leq B_{i} \leq 2 \cdot 10^{9}$，$0 \leq P_{i},U_{i} \leq 10^{9}$。 子任务编号|分值| $N$| $B$| $P$| $U$ :-:|:-:|:-:|:-:|:-:|:-: |$1$| $20$| $2 \leq N \leq 10^{6}$| $0 \leq B_{i} \leq 2 \cdot 10^{9} $|$0 \leq P_{i} \leq 10^{9}$ |$U_{i}=0$ $2$|$20$|$2 \leq N \leq 2000$| $0 \leq B_{i} \leq 400$|$ 0 \leq P_{i} \leq 200$| $0 \leq U_{i} \leq 200$ $3$| $24$| $2 \leq N \leq 4000$ |$0 \leq B_{i} \leq 4000$| $0 \leq P_{i} \leq 2000$| $0 \leq U_{i} \leq 2000$ $4$| $36$| $2 \leq N \leq 10^{6}$ |$0 \leq B_{i} \leq 2 \cdot 10^{9}$| $0 \leq P_{i} \leq 10^{9}$| $0 \leq U_{i} \leq 10^{9}$