| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 135 | 35 | 27 | 32.927% |
There are $N$ covered bus shelters, labelled 1,ドル \ldots, N$. The $i^\text{th}$ bus shelter can fit $B_i$ people inside.
For each $i \in \{1, \ldots, N - 1\},ドル there is a sidewalk connecting bus shelter $i$ to bus shelter $i + 1,ドル with an open-air market in the middle. The $i^\text{th}$ market has $U_i$ umbrellas for sale, each costing $\1ドル$.
Right now, the $i^\text{th}$ market has $P_i$ people inside, and every person is in a market so all the bus shelters are empty.
Suddenly, it starts raining, and everyone at market $i$ has to decide between three possibilities:
If a person is unable to find a place in a bus shelter or buy an umbrella, they will get wet.
If everyone coordinates optimally, can they all stay dry? If so, what is the least amount of money they need to spend, and which bus shelter should each person move to?
The first line of input contains an integer $N$.
The second line of input contains $N$ space-separated integers $B_i$ $(1 \le i \le N),ドル the capacity of bus shelter $i$.
The third line of input contains $N - 1$ space-separated integers $P_i$ $(1 \le i \le N - 1),ドル the number of people at market $i$.
The fourth line of input contains $N - 1$ space-separated integers $U_i$ $(1 \le i \le N - 1),ドル the number of umbrellas for sale at market $i$.
If every person can stay dry either under an umbrella or at a bus shelter, the output will be $N + 1$ lines:
YES.If not every person can stay dry, the output will be one line containing the word NO.
If there are multiple possible correct outputs, any correct output will be accepted.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | 2ドル \le N \le 10^6,ドル 0ドル \le B_i \le 2 \cdot 10^9,ドル 0ドル \le P_i \le 10^9,ドル $U_i = 0$ |
| 2 | 5 | 2ドル \le N \le 2,000円,ドル 0ドル \le B_i \le 400,ドル 0ドル \le P_i \le 200,ドル 0ドル \le U_i \le 200$ |
| 3 | 6 | 2ドル \le N \le 4,000円,ドル 0ドル \le B_i \le 4,000円,ドル 0ドル \le P_i \le 2,000円,ドル 0ドル \le U_i \le 2,000円$ |
| 4 | 9 | 2ドル \le N \le 10^6,ドル 0ドル \le B_i \le 2 \cdot 10^9,ドル 0ドル \le P_i \le 10^9,ドル 0ドル \le U_i \le 10^9$ |
3 10 15 10 20 20 0 0
NO
There are 35ドル$ spots available at bus shelters and no umbrellas available, but there are 40ドル$ people in the markets.
3 10 15 10 20 20 0 11
YES 5 10 0 10 5 5 10
Looking at market 1ドル,ドル 10ドル$ people will go to bus shelter 1ドル,ドル no one will buy an umbrella, and 10ドル$ people will go to bus shelter 2ドル$.
Looking at market 2ドル,ドル 5ドル$ people will go to bus shelter 2ドル,ドル 5ドル$ people will stay and buy an umbrella, and 10ドル$ people will move to bus shelter 3ドル$.
In total, 5ドル$ umbrellas were purchased, which costs $\5ドル$.