Watering the Plants | Code Joint

Bessie's garden has $N$ plants labeled $1$ through $N$ ( $2 \leq N \leq 5 \cdot 1 0^{5}$ ) from left to right. Bessie knows that plant $i$ requires at least $w_{i}$ ( $0 \leq w_{i} \leq 1 0^{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 \leq c_{i} \leq 1 0^{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 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$ .

SCORING:

Input 4: $N \leq 200$ , and all $w_{i} \leq 200$ .
Inputs 5-6: All $w_{i} \leq 200$ .
Inputs 7-10: $N \leq 5000$ .
Inputs 11-14: All $w_{i}$ and $c_{i}$ are generated independently and uniformly at random.
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The first line contains a single positive integer $N$ .

The second line contains $N$ space-separated integers $w_{1}, \dots, w_{N}$ .

The third line contains $N - 1$ space-separated integers $c_{1}, \dots, c_{N - 1}$ .

Output Format

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.

Sample Input 1

3 39 69 33 30 29

Sample Output 1

2070 2127

Sample Input 2

3 33 82 36 19 1

Sample Output 2

1558 676

Sample Input 3

8 35 89 44 1 35 3 62 50 7 86 94 62 63 9 49

Sample Output 3

623 4099 4114 6269 6272 6827 8827

Submit

Language