레이팅 미적용베시의 정원에는 왼쪽에서 오른쪽으로 \(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\)개의 식물에 물을 주는 최소 비용이어야 한다.
3
39 69 33
30 292070
2127The 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\).
3
33 82 36
19 11558
6768
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49623
4099
4114
6269
6272
6827
8827riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > January > Platinum