| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 6 | 4 | 3 | 100.000% |
Bessie's garden has $N$ plants labeled 1ドル$ through $N$ (2ドル\leq N\leq 5\cdot 10^5$) from left to right. Bessie knows that plant $i$ requires at least $w_i$ (0ドル\leq w_i \leq 10^6$) units of water.
Bessie has a very peculiar irrigation system with $N-1$ canals, numbered 1ドル$ through $N-1$. Each canal $i$ has an associated unit cost $c_i$ (1ドル\le c_i\le 10^6$), such that Bessie can pay $c_i k$ to provide plants $i$ and $i+1$ each with $k$ units of water, where $k$ is a non-negative integer.
Bessie is busy and may not have time to use all the canals. For each 2ドル\leq i \leq N$ compute the minimum cost required to water plants 1ドル$ through $i$ using only the first $i-1$ canals.
The first line contains a single positive integer $N$.
The second line contains $N$ space-separated integers $w_1, \ldots, w_N$.
The third line contains $N-1$ space-separated integers $c_1, \ldots, c_{N-1}$.
Output $N-1$ newline-separated integers. The $(i-1)$th integer should contain the minimum cost to water the first $i$ plants using the first $i-1$ canals.
3 39 69 33 30 29
2070 2127
The minimum cost to water the first 2ドル$ plants using the first canal is to pay 30ドル \cdot 69 = 2070$ by using the first canal 69ドル$ times.
The minimum cost to water the first 3ドル$ plants is to use the first canal 39ドル$ times and the second canal 33ドル$ times, paying 39ドル \cdot 30 + 29 \cdot 33 = 2127$.
3 33 82 36 19 1
1558 676
8 35 89 44 1 35 3 62 50 7 86 94 62 63 9 49
623 4099 4114 6269 6272 6827 8827