สมมติว่าในตารางของเรามีการทำงาน $i$ ต่อด้วยงาน $j$ เวลาที่งาน $i$ ทำเสร็จจะมีค่าเท่ากับ $T+A_i+B_i$ และเวลาที่งาน $j$ ทำเสร็จจะมีค่าเท่ากับ $T+A_i+A_j+B_j$ เมื่อ $T$ คือเวลาที่ใช้ก่อนหน้าจะทำงานที่ $i$

ดังนั้นคำตอบจะเป็นอย่างน้อย $max(T+A_i+B_i, T+A_i+A_j+B_j)$ ซึ่งมีค่าเท่ากับ $P = T + max(A_i+B_i, A_i+A_j+B_j)$

สมมติให้ $B_i \leq B_j$ เราจะลองสลับลำดับการทำงานของงาน $i$ และ $j$ โดยให้งาน $j$ ทำก่อนงาน $i$ คำตอบจะเป็นอย่างน้อย $P^* = T+max(A_j+B_j, A_j+A_i+B_i)$

เราจะพิสูจน์ว่า $P^* \leq P$

หาก $A_j+B_j > A_j+A_i+B_i$ นั่นคือ $P^* = T+A_j+B_j$ และ $B_j > A_i+B_i$ ดังนั้น $A_j+B_j > B_j > A_i+B_i > B_i$ ดังนั้น $P = T+A_i+A_j+B_j$ ซึ่งหมายความว่า $P^* \leq P$

หาก $A_j+B_j \leq A_j+A_i+B_i$ นั่นคือ $P^* = T+A_j+A_i+B_i$ และจาก $B_i \leq B_j$ จะได้ว่า $P^* = T+A_j+A_i+B_i \leq T+A_j+A_i+B_j = P$ นั่นเอง $\blacksquare$

สิ่งที่พิสูจน์ข้างต้นทำให้เราสรุปได้ว่า หากเรามีแผนการทำงานใด ๆ ที่เราทำ $i$ แล้วทำ $j$ แล้ว $B_i < B_j$ เราสามารถสลับให้เราทำงาน $j$ ก่อนแล้วทำ $i$ โดยไม่ทำให้คำตอบแย่ลง

ดังนั้นสมมติว่าเรามีแผนการทำงานที่มีคำตอบที่ดีสุดใด ๆ เราสามารถสลับลำดับของงานตามที่ได้กล่าวไปข้างต้นโดยไม่ทำให้คำตอบแย่ลงเช่นกัน ดังนั้นเมื่อสลับจนสลับต่อไม่ได้แล้ว จะได้คำตอบที่ดีที่สุดนั่นเอง

นั่นหมายความว่า เราควรทำงานตามลำดับ $B_i$ จากมากไปน้อย จึงจะได้คำตอบที่ดีที่สุด

สำหรับ subtask ที่ 1 เราสามารถตำนวณได้ตรง ๆ ใช้เวลา $\mathcal{O}(N^2)$

สำหรับ subtask ที่ 2 ให้เรารับ $B_i$ ทั้งหมดมาก่อน ขั้นตอนคำนวณคำตอบให้ใช้ segment tree with lazy propagation ในการหาคำตอบ เวลาที่ใช้จะมีค่าเท่ากับ $\mathcal{O}(N\log N)$

สำหรับ subtask ที่ 3 นั้นเป็นแบบ fully dynamic นั่นคือเราจะต้องรองรับการ "split" segment tree และ "insert" node เข้าไปตรงกลาง segment tree โครงสร้างข้อมูลที่สามารถใช้แก้ปัญหานี้ได้คือ implicit cartesian tree ซึ่งสามารถ implement ได้โดย treap นั่นเอง ในแต่ละโหนดเราจะเก็บ

• $A_i$ และ $B_i$
• คำตอบสำหรับช่วงนี้
• ผลรวมค่า $A_i$ สำหรับ node ที่มี key มากกว่า node นี้

เวลาที่ใช้จะมีค่าเท่ากับ $\mathcal{O}(N\log N)$