Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
เรื่องเริ่มต้นเมื่อวันหนึ่งคุณได้ข่าวมา ว่า มีอัญมณีอันล้ำค่ายิ่งกว่าที่เคยมีใครพบเจอถูกซ่อนอยู่... ได้เวลาปลุกความเป็นนักล่าสมบัติของคุณแล้ว! แต่กลับมีอุปสรรคสำคัญมาขวางคุณซะได้... เพราะการสำรวจทางโบราณคดีใดๆนั้นต้องใช้งบประมาณอยู่มาก คุณจึงตัดสินใจที่จะเอาเงินที่คุณมีไปลงทุนในตลาดหุ้น
เนื่องจากราคาหุ้นของบริษัทต่างๆ ขึ้นอยู่กับข่าวสารที่จะมาชี้ชะตาอนาคตของบริษัท และบางครั้งคุณก็ไม่ได้รู้ข่าวพวกนี้พร้อมกับคนอื่น ทำให้คุณอาจเสียเปรียบคนอื่นได้ แต่ด้วยสมองอันปราดเปรื่องของคุณ คุณได้สร้างเครื่องทำนายราคาหุ้นล่วงหน้ามา
สมมติว่า เครื่องให้ข้อมูลราคาหุ้นในวันต่างๆ เป็นดังนี้
วันที่ 1 ราคา 10
วันที่ 2 ราคา 20
วันที่ 3 ราคา 15
วันที่ 4 ราคา 12
วันที่ 5 ราคา 21
วันที่ 6 ราคา 30
ในช่วงวันที่ 1-6 คุณจะสามารถทำกำไรได้ 28 บาท โดยซื้อวันที่ 1 ขายวันที่ 2 และ ซื้อวันที่ 4 ขายวันที่ 6 (เริ่มต้นคุณมีเงินไม่จำกัด)
คุณมีข้อมูลราคาหุ้นอยู่ n วัน และคุณต้องการตอบคำถาม q คำถาม โดยแต่ละคำถามจะถาม
ว่า ในช่วงการลงทุนตั้งแต่วันที่ aj ถึงวันที่ bj ที่กำหนดให้ คุณจะสามารถทำการซื้อและขายหุ้นในช่วง
เฉพาะในช่วงวันดังกล่าว (หรือก็คือช่วง [aj, bj]) ให้ได้กำไรสูงสุดเท่าไร
เนื่องจากคุณไม่ต้องการให้เครื่องทำนายราคาหุ้นของคุณเป็นที่จับตามองของนักลงทุนคนอื่น ๆ
คุณจึงถือหุ้นในมือ ณ ขณะใด ๆ ไม่เกินหนึ่งหน่วยเท่านั้น (การถือหุ้นต้องถือเป็นจำนวนเต็มหน่วย
เท่านั้น)
เนื่องจากคุณไม่ต้องการให้เครื่องทำนายราคาหุ้นของคุณเป็นที่จับตามองของนักลงทุนคนอื่น ๆ
คุณจึงถือหุ้นในมือ ณ ขณะใด ๆ ไม่เกินหนึ่งหน่วยเท่านั้น (การถือหุ้นต้องถือเป็นจำนวนเต็มหน่วย
เท่านั้น)
งานของคุณ
จงเขียนโปรแกรมรับราคาหุ้นที่เครื่องของคุณทำนายออกมา และช่วงการลงทุนที่คุณต้องการทราบกำไร จากนั้นให้แสดงผลกำไรสูงสุดที่คุณสามารถทำได้สำหรับแต่ละช่วงที่กำหนด
ข้อมูลนำเข้า
บรรทัดที่ 1 มีจำนวนเต็มบวก n (1<=n<=1,000,000) แทนจำนวนวันที่คุณมีข้อมูลราคาหุ้น
บรรทัดที่ 2 มีจำนวนเต็มบวกอยู่ n ตัว ตัวที่ i แทนราคาของหุ้นในวันที่ i โดยราคาหุ้นในแต่ละวันจะมีค่าไม่เกิน 7,000
บรรทัดที่ 3 มีจำนวนเต็มบวก q (1<=q<=1,000,000) แทนจำนวนช่วงการลงทุนที่คุณต้องการทราบกำไร
บรรทัดที่ 4…q+3 มีจำนวนเต็มบวก 2 ตัว a b (1<=a, b<=n) แทนวันเริ่มต้นและวันสิ้นสุดของแต่ละช่วงการลงทุน
ข้อมูลส่งออก
มี q บรรทัด บรรทัดที่ i มีจำนวนเต็มบวกหนึ่งตัว แทนกำไรที่มากที่สุดที่คุณสามารถทำได้ในช่วงที่ i
โจทย์โดย: วรภัทร บุญญฤทธิพงษ์
ที่มา: TOI.CPP:03-2009
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 6 10 20 15 12 21 30 3 1 6 2 4 3 5 | 28 0 9 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้