ในข้อนี้ เราต้องการเลือกจุดสามจุดบนเส้นจำนวน ที่ผลรวมค่าความอร่อยของขนมที่สัมผัสกับจุดสามจุดนี้มีค่ามากที่สุด (ขนมมีทั้งหมด $N$ เส้น เส้นที่ $i$ วางอยู่ ณ ตำแหน่ง $a_i$ ถึง $b_i$)

เราจะใช้ Dynamic Programming ในการแก้ข้อนี้ โดยกำหนดให้ $dp(i, j)$ เป็นผลรวมค่าความอร่อยของขนมที่สัมผัสกับจุดบนเส้นจำนวนที่ได้เลือกเอาไว้ $j$ จุด โดยจุดที่ $j$ จะอยู่ที่ตำแหน่ง $i$ (ส่วนจุดอื่น ๆ อยู่ก่อนหน้าตำแหน่ง $i$)

หากเรากำหนดให้ Recurrence Formula เป็น

$dp(i, j) = \max \limits_{k < i} \{dp(k, j - 1)\} + \sum \limits_{a_l \leq i \leq b_l} c_l$

กล่าวคือคำนวณ $dp(i, j)$ โดยนำผลรวมค่าความอร่อยที่มากที่สุดเมื่อเลือกไปแล้ว $j - 1$ บวกกับขนมที่สัมผัสตำแหน่ง $i$ วิธีนี้จะเกิดปัญหาเพราะขนมที่สัมผัสกับ $i$ นั้น อาจสัมกับจุดที่ได้เลือกไว้ $j - 1$ จุดก่อนหน้าแล้ว ทำให้คำนวณค่าความอร่อยของขนมชิ้นนั้นซ้ำ เราจึงต้องแก้ปัญหาโดยคำนวณค่าของ $dp(i, j)$ ด้วยวิธีดังต่อไปนี้

1. กำหนดให้ $dp(0, 0) = 0$ ซึ่งเป็น Base Case
2. พิจารณา $i = 1, 2, ..., 10^9$ ตามลำดับ
3. สำหรับแต่ละ $i$ เราจะทำ Operation ดังต่อไปนี้

$dp(k, j) := dp(k, j) + c_l$ เมื่อ $1 \leq j \leq 3, b_l = i - 1$ และ $a_l \leq k \leq b_l$

4. กำหนดให้ $dp(i, j) = \max \limits_{0 \leq k < i} \{dp(k, j - 1)\}$ เมื่อ $1 \leq j \leq 3$
5. คำตอบของข้อนี้จะเป็น $\max \limits_{0 \leq i \leq 10^9} dp(i, 3)$

วิธีการด้านบนนี้ จะแก้ปัญหาการคิดค่าความอร่อยของขนมซ้ำซ้อน ด้วยการเพิ่มค่าความอร่อยของขนมหลังจากการคำนวณค่า $dp$ เป็นที่เรียบร้อยแล้ว และการที่ทำขั้นตอนที่ 3 เฉพาะขนมที่ตำแหน่งของขอบด้านขวาน้อยกว่าตำแหน่งปัจจุบันอยู่ 1 จะทำให้ขนมเหล่านั้นไม่ถูกนำไปคิดซ้ำในตำแหน่งถัดๆ ไป เนื่องจากหากเลือกตำแหน่งที่ $i$ เป็นต้นไปแล้ว จะไม่สัมผัสกับขนมชิ้นนั้นอีก

วิธีการดังกล่าวนี้ สามารถลดเวลาการทำงานโดยสังเกตว่าเซตของ $i$ ที่มีความจำเป็นสำหรับการคำนวณ $dp(i, j)$ จะเป็น $\{0, a_1, a_2, ..., a_n, b_1 + 1, b_2 + 1, ..., b_N + 1\}$ เท่านั้น ทำให้เราสามารถใช้การ Coordinate Compression ลดจำนวนของ $dp(i, j)$ ที่ต้องคำนวณเหลือเพียง $\mathcal{O}(N)$ เท่านั้น นอกจากนี้ ขั้นตอนที่ 3 และ 4 สามารถลดเวลาการทำงานด้วยการใช้ Segment Tree และ Lazy Propagation ที่รองรับการหาค่าที่น้อยที่สุดในช่วง และการบวกค่าเป็นช่วง ทำให้สองขั้นตอนนี้ ใช้เวลาการทำงานเพียง $\mathcal{O}(\log N)$

Time Complexity: $\mathcal{O}(N \log N)$