Hội trường 3
Xem dạng PDF
Gửi bài giải
Điểm:
14,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ ~a_i~ đến ~b_i~ và trả tiền thuê là ~c_i~.
Yêu cầu: Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).
Input
- Dòng đầu tiên chứa một số nguyên dương n (~n \le 10^4~)
- Mỗi dòng trong số n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ~a_i, b_i, c_i (0 \le a_i < b_i \le 10^5, 1 \le c_i \le 10^5)~
Output
Gồm một dòng duy nhất là tổng số tiền thu được lớn nhất
Examples
Input
3
4 11 10
1 5 4
5 10 5
Output
10
Input
4
4 11 1
1 5 1
5 10 1
1 100 1
Output
2
Bình luận
Test 2 output bị sai kìa Admin, ra 1 thì đúng hơn!
Không sai mô em. Kết thúc của kíp trước <= bắt đầu của kíp sau là được. Test này mình chọn: (1 5) và (5 10) với tổng giá trị là 2.
kp đề bảo là ko giao nhau à anh
Giao ở đây là chồng lên nhau em nhé. Kết thúc của mối tình này đôi khi là bắt đầu của mối tình kia. Kết thúc để bắt đầu!
thấm chưa e Minh_positive09