P10051 [CCO 2022] Rainy Markets

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

There are $N$ bus stops, numbered $1, \ldots, N$. The $i$-th bus stop can hold $B_{i}$ people. For each $i \in \{1, \ldots, N-1\}$, there is a sidewalk connecting bus stop $i$ and bus stop $i+1$, with an open-air market in between. Market $i$ sells $U_{i}$ umbrellas, and each umbrella costs $1$. Currently, there are $P_{i}$ people in market $i$, and all bus stops are empty. Suddenly, it starts to rain. Each person in market $i$ must choose one of the following three options: - Go to bus stop $i$. - Go to bus stop $i+1$. - Stay and buy an umbrella. If a person cannot get into a bus stop or cannot buy an umbrella, they will get wet. You need to determine whether, under an optimal arrangement, it is possible to ensure that nobody gets wet. If it is possible, you must output the minimum total money that needs to be spent, and where people from each market should go.

The first line contains an integer $N$. The second line contains $N$ space-separated integers $B_{i}\ (1 \leq i \leq N)$, representing the capacity of bus stop $i$. The third line contains $N-1$ space-separated integers $P_{i}\ (1 \leq i \leq N-1)$, representing the number of people in market $i$. The fourth line contains $N-1$ space-separated integers $U_{i}\ (1 \leq i \leq N-1)$, representing the number of umbrellas sold in market $i$.

If everyone can end up either under an umbrella or in a bus stop, output $N+1$ lines: - The first line should be `YES`. - The second line should be an integer, the minimum total money spent on umbrellas. - The next $N-1$ lines should each contain three space-separated integers. For market $i\ (1 \leq i \leq N-1)$, they represent: the number of people who move to bus stop $i$, the number of people who buy umbrellas, and the number of people who move to bus stop $i+1$. If there are multiple valid solutions, you may output any one of them. Otherwise, output a single line `NO`.

## Explanation for Sample 1 There are $35$ empty spots in the bus stops and no umbrellas for sale, but there are $40$ people in the market, so the answer is `NO`. ## Explanation for Sample 2 The $10$ people in market $1$ go to bus stop $1$, nobody buys an umbrella, and $10$ people go to bus stop $2$. In market $2$, $5$ people go to bus stop $2$, $5$ people stay and buy umbrellas, and $10$ people move to bus stop $3$. In total, $5$ umbrellas are bought, costing $5$. ## Constraints For all testdata, $2 \leq N \leq 10^{6}$, $0 \leq B_{i} \leq 2 \cdot 10^{9}$, $0 \leq P_{i}, U_{i} \leq 10^{9}$. Subtask ID | Points | $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}$ Translated by ChatGPT 5