RiseOJ – 식물에 물 주기

설명

베시의 정원에는 왼쪽에서 오른쪽으로 $$1$$ 부터 $$N$$ 까지 번호가 매겨진 식물 $$N$$ 개( $2\leq N\leq 5\cdot 10^5$ )가 있다. 베시는 식물 $$i$$ 가 최소 $$w_i$$ ( $0\leq w_i \leq 10^6$ ) 단위의 물을 필요로 한다는 것을 알고 있다.

베시는 $$1$$ 부터 $$N-1$$ 까지 번호가 매겨진 수로 $$N-1$$ 개로 이루어진 매우 독특한 관개 시스템을 가지고 있다. 각 수로 $$i$$ 에는 단위 비용 $$c_i$$ ( $1\le c_i\le 10^6$ )가 있어서, 베시는 $c_i\ k$ 를 지불하고 식물 $$i$$ 와 $$i+1$$ 에 각각 $$k$$ 단위의 물을 공급할 수 있다. 여기서 $$k$$ 는 음이 아닌 정수이다.

베시는 바빠서 모든 수로를 사용할 시간이 없을 수도 있다. 각 $2\leq i \leq N$ 에 대해, 처음 $$i-1$$ 개의 수로만 사용하여 식물 $$1$$ 부터 $$i$$ 까지에 물을 주는 데 필요한 최소 비용을 계산하시오.

Problem credits: Benjamin Qi

제약

배점

입력 4: $N \leq 200$ 이고 모든 $w_i \leq 200$ .
입력 5-6: 모든 $w_i \leq 200$ .
입력 7-10: $N \leq 5000$ .
입력 11-14: 모든 $$w_i$$ 와 $$c_i$$ 는 독립적으로 균등하게 무작위로 생성된다.
입력 15-19: 추가 제약이 없다.

Problem credits: Benjamin Qi

입력 형식

첫째 줄에 양의 정수 $$N$$ 이 주어진다.

둘째 줄에 공백으로 구분된 정수 $$N$$ 개 $w_1, \ldots, w_N$ 이 주어진다.

셋째 줄에 공백으로 구분된 정수 $$N-1$$ 개 $c_1, \ldots, c_{N-1}$ 이 주어진다.

출력 형식

줄바꿈으로 구분된 정수 $$N-1$$ 개를 출력한다. $$(i-1)$$ 번째 정수는 처음 $$i-1$$ 개의 수로를 사용하여 처음 $$i$$ 개의 식물에 물을 주는 최소 비용이어야 한다.

예제 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

출력

문제 정보

riseoj 작성

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

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

태그

JudgeUSACO

식물에 물 주기

평가 및 의견

풀이 제출