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

Please read the guidelines before commenting.



  • -2
    nhat  commented on July 21, 2023, 11:19 p.m.

    it's a piece of cake :)))


    • -2
      MinhKhoi  commented on July 22, 2023, 2:24 a.m.

      =)) gvs