Thuê Kho Lạnh Lưu Trữ Nông Sản Theo Mùa
Đề bài
Một hợp tác xã nông nghiệp hoạt động trong $N$ tuần liên tiếp. Tuần thứ $i$ thu hoạch thêm $A_i$ tấn nông sản tươi và phải xuất bán đúng $B_i$ tấn cho siêu thị (tổng $\sum A_i = \sum B_i$). Nếu nông sản thu hoạch ở tuần $i$ chưa xuất bán hết, hợp tác xã có thể gửi tối đa $Cap_i$ tấn sang tuần $i+1$ với chi phí cấp đông $Hold_i$ mỗi tấn. Ngoài ra có $M$ hợp đồng chuyển kho nhanh: hợp đồng thứ $k$ cho phép chuyển tối đa $U_k$ tấn từ tuần $x_k$ sang tuần $y_k$ ($x_k < y_k$) với chi phí $Cost_k$ mỗi tấn. Hãy tìm tổng chi phí lưu trữ nhỏ nhất để đáp ứng đủ lượng xuất bán của mọi tuần.
Dữ liệu vào
Dòng 1 gồm hai số nguyên $N, M$ ($2 \le N \le 50, 0 \le M \le 100$). Dòng 2 gồm $N$ số nguyên $A_i$. Dòng 3 gồm $N$ số nguyên $B_i$. Dòng 4 gồm $N-1$ số nguyên $Cap_i$. Dòng 5 gồm $N-1$ số nguyên $Hold_i$. $M$ dòng tiếp theo, mỗi dòng gồm 4 số nguyên $x, y, U, Cost$.
Dữ liệu ra
In ra tổng chi phí nhỏ nhất, hoặc -1 nếu không thể đáp ứng lịch xuất bán.
Ví dụ
| Input | Output |
|---|---|
| 4 1 5 2 1 2 2 3 2 3 3 2 2 2 3 2 1 4 2 4 |
11 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion