#PU1478. USACO 2025 January Contest, Platinum — Problem 3. Watering the Plants

    ID: 1565 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan25来源:usaco.orgscoring:equal_test_cases动态规划

USACO 2025 January Contest, Platinum — Problem 3. Watering the Plants

USACO 2025 January Contest, Platinum — Problem 3. Watering the Plants

题目描述

Bessie's garden has NN plants labeled 11 through NN (2≤N≤5⋅1052\leq N\leq 5\cdot 10^5) from left to right. Bessie knows that plant ii requires at least wiw_i (0≤wi≤1060\leq w_i \leq 10^6) units of water. Bessie has a very peculiar irrigation system with N−1N-1 canals, numbered 11 through N−1N-1. Each canal ii has an associated unit cost cic_i (1≤ci≤1061\le c_i\le 10^6), such that Bessie can pay cikc_i k to provide plants ii and i+1i+1 each with kk units of water, where kk is a non-negative integer. Bessie is busy and may not have time to use all the canals. For each 2≤i≤N2\leq i \leq N compute the minimum cost required to water plants 11 through ii using only the first i−1i-1 canals .

输入格式

The first line contains a single positive integer NN. The second line contains NN space-separated integers w1,…,wNw_1, \ldots, w_N. The third line contains N−1N-1 space-separated integers c1,…,cN−1c_1, \ldots, c_{N-1}.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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$.

样例 2

3
33 82 36
19 1
1558
676

样例 3

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49
623
4099
4114
6269
6272
6827
8827