Editorial for Bedao Mini Contest 14 - CAMPAIGN


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Đầu tiên ta sắp xếp lại các điểm tăng dần theo trục ~x~.

Dễ thấy ta có thể biến đổi phương trình đề bài lại thành ~\sum_{i \in S}y_i + min(x_i) - max(x_i)~. Vì ~y_i~ luôn dương nên ta gọi ~S[i] = max(\sum_{i \in S}y_i + min(x_i))~. Cụ thể với mỗi vị trí ~i~, ta cộng ~y_i~ lên đoạn ~S[1..i]~ và ~x_i~ lên ~S[i]~, ở phần này ta có thể ứng dụng tổng tiền tố. Kết quả của bài toán sẽ là ~max(max(S[1..i]) - x_i)~ với ~(1 \le i \le n)~

Độ phức tạp: ~O(n \times logn)~.


Comments

Please read the guidelines before commenting.



  • 8
    dangbesttoan24   commented on Nov. 10, 2022, 10:31 p.m.

    Mình nghĩ đã sort ban đầu thì đpt phải là O(nlogn) chứ nhỉ sao có thể giảm xuống O(n) đc :>


    • 6
      bedao   commented on Nov. 11, 2022, 10:57 a.m.

      Bọn mình đã sửa lại trong bài, cảm ơn bạn đã góp ý.