Page not loading? Try clicking here.
Placeholder

#8266
Subtask

운하 1s 1024MB

Problems

N개의 식물이 왼쪽에서 오른쪽으로 배치되어 있다. 각 식물 i는 최소 w_i 단위의 물이 필요하다.

N-1개의 운하가 있으며, 각 운하는 k 단위의 물을 공급하기 위해 c_i 금액을 지불해야 한다.

  • 여기서 k는 0 이상의 정수다.

  • 즉, 운하 i는 식물 i와 i+1에 각각 k 단위의 물을 공급하는데 c_i⋅k 비용이 든다.

모든 운하를 사용할 수 없을 수도 있다. 각 2 ≤ i ≤ N에 대해, 첫 번째 i-1개의 운하만을 사용하여 식물 1부터 i까지 물을 주기 위한 최소 비용을 계산하는 프로그램을 작성하시오.


Input

첫 번째 줄에는 N이 주어진다.

두 번째 줄에는 N개의 공백으로 구분된 정수 w_1, ..., w_N이 주어진다.

세 번째 줄에는 N-1개의 공백으로 구분된 정수 c_1, ..., c_{N-1}이 주어진다.


Output

각각의 i-1번째 값에 대해, 첫 번째 i개의 식물에 대해 첫 번째 i-1개의 운하만을 사용하여 물을 주는 최소 비용을 계산하고 출력다.


Subtask

# Score Condition
#15

N≤200, w_i≤200

#210

w_i​≤200

#315

N≤5000

#430

모든 w_i​와 c_i​는 독립적으로 균등하게 무작위로 생성됨.

#540

추가 제약 조건 없음


Example #1

3
39 69 33
30 29
2070
2127

첫 번째 식물과 두 번째 식물에 물을 주는 최소 비용은 첫 번째 운하를 69번 사용하고, 비용은 30⋅69 = 2070입니다.

세 번째 식물까지 물을 주는 최소 비용은 첫 번째 운하를 39번 사용하고 두 번째 운하를 33번 사용하여, 비용은 39⋅30 + 29⋅33 = 2127입니다.


Example #2

3
33 82 36
19 1
1558
676

Example #3

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

Source

USACO 2025 January Platinum

You must sign in to write code.