{"problem":{"name":"[CCO 2022] Rainy Markets","description":{"content":"有 $N$ 个公交车站，标号为 $1, \\ldots, N$。第 $i$ 个公交车站可以容纳 $B_{i}$ 个人。 对于每个 $i \\in\\{1, \\ldots, N-1\\}$，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_{i}$ 把雨伞出售，每把雨伞的价格为 $1$。 现在，有 $P_{i}$ 个人在第 $i$ 个市场里面，所有","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10051"},"statements":[{"statement_type":"Markdown","content":"有 $N$ 个公交车站，标号为 $1, \\ldots, N$。第 $i$ 个公交车站可以容纳 $B_{i}$ 个人。\n\n对于每个 $i \\in\\{1, \\ldots, N-1\\}$，有一条人行道连接公交车站 $i$ 和公交车站 $i+1$，中间有一个露天市场。第 $i$ 个市场有 $U_{i}$ 把雨伞出售，每把雨伞的价格为 $1$。\n\n现在，有 $P_{i}$ 个人在第 $i$ 个市场里面，所有的公交车站都是空的。\n\n突然，天开始下雨，市场 $i$ 的每个人都必须在三种方案中选择一种：\n\n- 去公交车站 $i$；\n- 去公交车站 $i+1$；\n- 留下来买一把雨伞。\n\n如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。\n\n你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。\n\n## Input\n\n第一行包含一个整数 $N$。\n\n第二行包含 $N$ 个用空格分隔的整数 $B_{i}\\ (1 \\leq i \\leq N)$，表示公交车站 $i$ 的容量。\n\n第三行包含 $N-1$ 个用空格分隔的整数 $P_{i}\\ (1 \\leq i \\leq N-1)$，表示市场 $i$ 的人数。\n\n第四行包含 $N-1$ 个用空格分隔的整数 $U_{i}\\ (1 \\leq i \\leq N-1)$，表示市场 $i$ 出售的雨伞的数量。\n\n## Output\n\n如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行：\n\n- 第一行输出一行 `YES`。\n- 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。\n- 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i\\ (1\\leq i \\leq N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。\n\n如果有多种合法方案，你可以输出任意一种。\n\n否则，输出一行 `NO`。\n\n[samples]\n\n## Background\n\n## 由于数据包过大，本题无法上传全部数据。\n\n## Note\n\n## 样例 1 解释\n\n公交车站有 $35$ 个空位，没有雨伞出售，但市场有 $40$ 个人，所以答案是 `NO`。\n\n## 样例 2 解释\n\n市场 $1$ 中的 $10$ 个人会去公交车站 $1$，没有人会买雨伞，$10$ 个人会去公交车站 $2$。\n\n市场 $2$ 中的 $5$ 个人会去公交车站 $2$，$5$ 个人会留下来买雨伞，$10$ 个人会移动到公交车站 $3$。\n\n总共购买了 $5$ 把雨伞，花费了 $5$。\n\n## 数据范围\n\n对于所有的数据，有 $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\n子任务编号|分值|\t$N$|\t$B$|\t$P$|\t$U$\n:-:|:-:|:-:|:-:|:-:|:-:\n|$1$|\t$20$|\t$2 \\leq N \\leq 10^{6}$|\t$0 \\leq B_{i} \\leq 2 \\cdot 10^{9}\t$|$0 \\leq P_{i} \\leq 10^{9}$\t|$U_{i}=0$\n$2$|$20$|$2 \\leq N \\leq 2000$|\t$0 \\leq B_{i} \\leq 400$|$\t0 \\leq P_{i} \\leq 200$|\t$0 \\leq U_{i} \\leq 200$\n$3$|\t$24$|\t$2 \\leq N \\leq 4000$\t|$0 \\leq B_{i} \\leq 4000$|\t$0 \\leq P_{i} \\leq 2000$|\t$0 \\leq U_{i} \\leq 2000$\n$4$|\t$36$|\t$2 \\leq N \\leq 10^{6}$\t|$0 \\leq B_{i} \\leq 2 \\cdot 10^{9}$|\t$0 \\leq P_{i} \\leq 10^{9}$|\t$0 \\leq U_{i} \\leq 10^{9}$","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10051","tags":["动态规划 DP","贪心","2022","Special Judge","CCO（加拿大）"],"sample_group":[["3\n10 15 10\n20 20\n0 0","NO"],["3\n10 15 10\n20 20\n0 11","YES\n5\n10 0 10\n5 5 10"]],"created_at":"2026-03-03 11:09:25"}}