Kế hoạch thuê nhân công
View as PDF
Submit solution
Points:
400.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Một dự án phần mềm cần triển khai trong 𝑛 tháng đánh số từ 1 tới 𝑛.
Biết rằng: Bắt đầu vào một tháng, dự án có quyền thuê thêm nhân công. Để thuê mỗi nhân công cần một khoản chi phí 𝐻 (trả cho nhà tuyển dụng). Mỗi nhân công được thuê sẽ được trả một khoản lương 𝑆 mỗi tháng kể cả khi không làm việc. Kết thúc một tháng, dự án có quyền sa thải nhân công. Để sa thải mỗi nhân công cần trả một khoản chi phí 𝐷. Không có nhân công nào trước khi dự án bắt đầu. Mỗi tháng 𝑖 cần tối thiểu ~𝑎_𝑖~ nhân công. Kết thúc tháng thứ 𝑛, toàn bộ nhân công phải bị sa thải.
Yêu cầu: Hãy giúp ông giám đốc dự án xây dựng kế hoạch thuê nhân công để dự án được hoàn thành với chi phí thuê nhân công ít nhất có thể.
Dữ liệu vào:
- Dòng 1 chứa số tháng 𝑛 (1 ≤ 𝑛 ≤ 4.~10^5~)
- Dòng 2 chứa ba số nguyên dương 𝐻, 𝑆, 𝐷 (𝐻, 𝑆, 𝐷 ≤ ~10^6~)
- Dòng 3 chứa 𝑛 số nguyên dương ~𝑎_1~, ~𝑎_2~, … , ~𝑎_𝑛~ (∀𝑖: ~𝑎_𝑖~ ≤ ~10^6~)
Kết quả:
- Dòng 1: Ghi chi phí tối thiểu tìm được
- Dòng 2: Ghi 𝑛 số, số thứ 𝑖 là số nhân công làm trong dự án tại tháng thứ 𝑖
Ví dụ:
INPUT
3
4 5 6
10 9 11
OUTPUT
265
10 10 11
Comments
it's a piece of cake :)))
=)) gvs