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.

Problem credits: Benjamin Qi

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

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.

riseoj 작성

출처 올림피아드 > USACO > 2024-2025 > January > Platinum