VOI 22 Bài 4 - Đoạn số
Xem dạng PDFLà sinh viên ngành Công nghệ thông tin, Nam thường xuyên rèn luyện tư duy và kĩ năng lập trình bằng các bài toán lập trình thi đấu. Một bài toán thú vị mà Nam đang suy nghĩ để giải như sau:
Cho ~n~ đoạn số nguyên trên trục số, đoạn thứ ~k~ (~1 \le k \le n~) có đầu mút bên trái là ~L_k~, đầu mút bên phải là ~R_k~ và có trọng số là ~w_k~. Với ~a, b~ là hai số nguyên, trọng số của cặp số ~(a, b)~ được tính bằng tổng trọng số của tất cả các đoạn ~t~ mà ~a \le L_t \le R_t \le b~ với ~1 \le t \le n~. Cần tìm cặp số nguyên ~(a, b)~ có trọng số là lớn nhất.
Yêu cầu: Cho ~n~ đoạn số, gọi ~S~ là trọng số của cặp số nguyên ~(a, b)~ có trọng số là lớn nhất, hãy giúp Nam xác định giá trị ~S~.
Dữ liệu
Vào từ file văn bản SSEQ.INP:
- Dòng đầu chứa số nguyên dương ~n~;
- Dòng thứ ~k~ (~1 \le k \le n)~ trong ~n~ dòng tiếp theo chứa ba số nguyên ~L_k, R_k, w_k~ mô tả đoạn thứ ~k~ (~1 \le L_k \le R_k \le 10^6~; ~|w_k| \le 10^6~).
Các số trên cùng một dòng cách nhau bởi dấu cách.
Kết quả
Ghi ra file văn bảng SSEQ.OUT một số nguyên ~S~ là trọng số lớn nhất xác định được.
- Có ~30\%~ số test ứng với ~30\%~ số điểm thỏa mãn: ~n \le 200~;
- ~30\%~ số test khác ứng với ~30\%~ số điểm thỏa mãn: ~n \le 2000~;
- ~20\%~ số test khác ứng với ~20\%~ số điểm thỏa mãn: ~R_1 - L_1 = R_2 - L_2 = \ldots = R_n - L_n~ và ~n \le 10^5~;
- ~20\%~ số test còn lại ứng với ~20\%~ số điểm thỏa mãn: ~n \le 10^5~.
Ví dụ
Input
4
1 2 -5
3 5 6
3 4 -1
4 6 3
Output
8
Giải thích
Trọng số lớn nhất là ~8~ bằng cách chọn cặp số ~(3, 6)~. Trọng số của cặp số ~(3, 6)~ bằng tổng trọng số của ba đoạn: ~[3, 5]~, ~[3, 4]~ và ~[4, 6]~.
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài này hay thế mà spoil sol rồi :((
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.