페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8266
서브태스크

운하 1초 1024MB

문제

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까지 물을 주기 위한 최소 비용을 계산하는 프로그램을 작성하시오.


입력

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

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

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


출력

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


부분문제

번호 점수 조건
#15점

N≤200, w_i≤200

#210점

w_i​≤200

#315점

N≤5000

#430점

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

#540점

추가 제약 조건 없음


예제1

입력
3
396933
3029
출력
2070
2127

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

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


예제2

입력
3
338236
191
출력
1558
676

예제3

입력
8
35894413536250
786946263949
출력
623
4099
4114
6269
6272
6827
8827

출처

USACO 2025 January Platinum

역링크