VOI 22 Bài 4 - Đoạn số

View as PDF
Submit solution
Points: 0.50 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: SSEQ.INP
Output: SSEQ.OUT
Problem source:
Kỳ thi Học sinh giỏi Quốc gia 2022 - Ngày 2
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Là 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]~.

Comments

Please read the guidelines before commenting.


  • -12
    t_huynn93  commented on Nov. 23, 2023, 4:31 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -4
      Shogun  commented on Dec. 14, 2023, 10:37 a.m.

      Bài này hay thế mà spoil sol rồi :((


    • -7
      thethethe  commented on Nov. 24, 2023, 6:35 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -14
    buivietthanh  commented on Sept. 25, 2023, 6:17 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -6
      Pitomon  commented on Jan. 3, 2024, 2:17 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -12
    neptune_170_nt  commented on Jan. 24, 2023, 2:54 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.