[CCO 2022] Rainy Markets

Luogu

IDLGP10051

Time1500ms

Memory1024MB

DifficultyP4

动态规划 DP贪心2022Special JudgeCCO（加拿大）

有 $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$； - 留下来买一把雨伞。如果一个人无法在某个公交车站下或者买一把雨伞，他们就会淋湿。你需要回答如果在最优的安排方案下，能否确保每个人都能不被雨淋湿。如果是的话，你需要给出他们需要花费的最少的钱，以及每个人应该移动到哪个公交车站。 ## Input 第一行包含一个整数 $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$ 出售的雨伞的数量。 ## Output 如果每个人都能在雨伞或公交车站下，输出 $N+1$ 行： - 第一行输出一行 `YES`。 - 第二行输出一个整数，表示包含在雨伞上花费的最少的钱。 - 接下来的 $N-1$ 行，每行输出三个用空格分隔的整数分别表示市场 $i\ (1\leq i \leq N-1)$ 移动到公交车站 $i$ 的人数，市场 $i$ 买雨伞的人数，市场 $i$ 移动到公交车站 $i+1$ 的人数。如果有多种合法方案，你可以输出任意一种。否则，输出一行 `NO`。 [samples] ## Background ## 由于数据包过大，本题无法上传全部数据。 ## Note ## 样例 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}$

Samples

Input #1

Output #1

NO

Input #2

Output #2

API Response (JSON)

{
  "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$ 个市场里面，所有...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments