Khu vườn của Bessie có \(N\) cây được đánh số từ \(1\) đến \(N\) (\(2\leq N\leq 5\cdot 10^5\)) theo thứ tự từ trái sang phải. Bessie biết rằng cây \(i\) cần ít nhất \(w_i\) (\(0\leq w_i \leq 10^6\)) đơn vị nước.

Bessie có một hệ thống tưới tiêu rất đặc biệt với \(N-1\) kênh dẫn nước, được đánh số từ \(1\) đến \(N-1\). Mỗi kênh \(i\) có một chi phí đơn vị tương ứng \(c_i\) (\(1\le c_i\le 10^6\)), sao cho Bessie có thể trả \(c_i k\) để cung cấp cho mỗi cây \(i\) và \(i+1\) đúng \(k\) đơn vị nước, trong đó \(k\) là một số nguyên không âm.

Bessie bận rộn và có thể không có thời gian sử dụng tất cả các kênh. Với mỗi \(2\leq i \leq N\), hãy tính chi phí nhỏ nhất cần thiết để tưới các cây từ \(1\) đến \(i\) chỉ sử dụng \(i-1\) kênh đầu tiên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên dương \(N\).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách \(w_1, \ldots, w_N\).

Dòng thứ ba chứa \(N-1\) số nguyên cách nhau bởi dấu cách \(c_1, \ldots, c_{N-1}\).

Dữ liệu ra

In \(N-1\) số nguyên, mỗi số trên một dòng. Số nguyên thứ \((i-1)\) phải chứa chi phí nhỏ nhất để tưới \(i\) cây đầu tiên bằng \(i-1\) kênh đầu tiên.

Ví dụ

3
39 69 33
30 29

2070
2127

3
33 82 36
19 1

1558
676

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

623
4099
4114
6269
6272
6827
8827

Phân nhóm

• Input 4: \(N \leq 200\), và mọi \(w_i \leq 200\).
• Inputs 5-6: Mọi \(w_i \leq 200\).
• Inputs 7-10: \(N \leq 5000\).
• Inputs 11-14: Mọi \(w_i\) và \(c_i\) được sinh độc lập và ngẫu nhiên đều.
• Inputs 15-19: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — Watering the Plants

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1478

Tác giả đề: Benjamin Qi