Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout).

Có ~n~ điểm trên con đường mà bạn đang lái taxi. ~n~ điểm trên đường được đánh số từ ~1~ đến ~n~ theo hướng bạn đang đi, và bạn muốn lái từ điểm ~1~ đến điểm ~n~ để kiếm tiền bằng cách đón khách. Bạn không thể đổi hướng đi của taxi.

Các hành khách được biểu diễn bằng mảng số nguyên hai chiều rides đánh số từ 0, trong đó rides[i] = [starti, endi, tipi] cho biết hành khách thứ ~i~ muốn đi từ điểm starti tới điểm endi và sẵn sàng boa tipi đô la.

Với mỗi hành khách ~i~ mà bạn chở, bạn kiếm được endi - starti + tipi đô la. Tại mỗi thời điểm bạn chỉ được chở nhiều nhất một hành khách.

Cho ~n~ và rides, hãy in ra số tiền lớn nhất bạn có thể kiếm được nếu chọn đón khách một cách tối ưu.

Lưu ý: bạn có thể trả một hành khách và đón một hành khách khác tại cùng một điểm.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ (~m~ là số hành khách, tức độ dài mảng rides).
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên starti, endi, tipi.

Kết quả

• In ra một số nguyên duy nhất là số tiền lớn nhất kiếm được.

Giới hạn

• ~1 \le n \le 10^5~.
• ~1 \le m \le 3 \cdot 10^4~.
• ~1 \le~ starti ~\lt~ endi ~\le n~.
• ~1 \le~ tipi ~\le 10^5~.

Sample Input 1

5 2
2 5 4
1 5 1

Sample Output 1

7

Giải thích

Ta có thể đón hành khách 0 để kiếm được 5 - 2 + 4 = 7 đô la.

Sample Input 2

20 6
1 6 1
3 10 2
10 12 3
11 12 2
12 15 2
13 18 1

Sample Output 2

20

Giải thích

Ta sẽ đón các hành khách sau:

• Chở hành khách 1 từ điểm 3 tới điểm 10, lời 10 - 3 + 2 = 9 đô la.
• Chở hành khách 2 từ điểm 10 tới điểm 12, lời 12 - 10 + 3 = 5 đô la.
• Chở hành khách 5 từ điểm 13 tới điểm 18, lời 18 - 13 + 1 = 6 đô la.

Tổng cộng kiếm được 9 + 5 + 6 = 20 đô la.

Nguồn: LeetCode 2008.