cs225 RENTING Cho thuê máy

Tại thời điểm 0, ông chủ cho thuê máy tính nhận được đơn đặt hàng thuê sử dụng máy của N khách hàng. Các khách hàng được đánh số từ 1 đến N.

Khách hàng i cần sử dụng máy từ thời điểm di đến thời điểm ci (di và ci là các số nguyên, 0 < di < ci <= 1.000.000.000) và sẽ trả tiền sử dụng máy là pi (pi là số nguyên, 0 < p_i <= 100.000.000).

Hãy xác định những khách hàng cần được phục vụ sao cho khoảng thời gian sử dụng máy tính của hai khách hàng bất kỳ được phục vụ không giao nhau và tổng tiền thu được là lớn nhất.

DỮ LIỆU VÀO (RENTING.INP)

• Dòng đầu ghi số N (0 < N <= 1000).
• Dòng thứ i trong N dòng tiếp theo ghi ba số di, ci, p_i, cách nhau bởi dấu cách (i = 1, 2, ..., N).

KẾT QUẢ (RENTING.OUT)

• Dòng đầu ghi hai số nguyên: số lượng khách hàng được phục vụ và tổng tiền thu được.
• Dòng tiếp theo ghi chỉ số các khách hàng được phục vụ.

VÍ DỤ 1 RENTING.INP 3 150 500 150 1 200 100 400 800 80

RENTING.OUT 2 180 2 3

VÍ DỤ 2 RENTING.INP 4 400 821 800 200 513 500 100 325 200 600 900 600

RENTING.OUT 2 1100 2 4

Ghi chú: Hai khoảng thời gian được xem là không giao nhau khi thời điểm kết thúc của khoảng trước không lớn hơn thời điểm bắt đầu của khoảng sau (ci <= dj).