2035 : GARAGE
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

โรงจอดรถแห่งหนึ่งมี N ที่ว่างสำหรับจอดรถซึ่งที่ว่างเหล่านี้ถูกนับเป็นหมายเลขตั้งแต่ 1 ถึง N   โรง จอดรถแห่งนี้จะเปิดเป็นโรงจอดรถที่ว่างเปล่าเพื่อให้บริการในทุก ๆ เช้าและในตลอดทั้งวันมันจะดำเนินการตามวิธีการที่จะกล่าวถึง ดังนี้   เมื่อใดก็ตามที่มีรถยนต์มาถึงที่โรงจอดรถแห่งนี้   ผู้ดูแลจะตรวจสอบว่ามีที่ว่างสำหรับจอดรถหรือไม่   ถ้าไม่มี   ให้รถยนต์คันนั้นรอที่ทางเข้าเสียก่อนจนกว่าจะมีที่ว่างสำหรับจอดรถ   แต่ถ้าเกิดมีที่ว่างพอสำหรับจอดรถหรือทันทีที่มีที่ว่างแค่เพียง 1 ที่ที่สามารถจอดได้   ก็จะให้รถยนต์คันนั้นจอดในที่ว่างที่มีอยู่นั้น   และถ้ามีที่ว่างสำหรับจอดรถมากกว่า 1 ที่   ก็จะให้รถยนต์คันนั้นจอดในที่ว่างที่มีจำนวนหมายเลขน้อยที่สุด   แล้ว ถ้ามีรถยนต์คันอื่นมาถึงที่โรงจอดรถแห่งนี้ในขณะที่ยังมีรถยนต์บางคันกำลัง รอเพื่อเข้าจอดอยู่ ให้รถยนต์ทุกคันที่รออยู่เข้าคิวกันตรงทางเข้าของโรงจอดรถแห่งนี้เรียงตาม ลำดับการมาก่อน-หลังกัน   จากนั้น เมื่อมีที่ว่างสำหรับจอดรถ  ก็จะให้รถยนต์คันแรกของคิว (รถยนต์คันที่มาถึงก่อนที่สุด)  ได้จอดตรงที่ว่างนั้น

 

ค่า จอดรถในหน่วยดอลลาร์ จะมีค่าเท่ากับค่าน้ำหนักของรถยนต์ในหน่วยกิโลกรัมคูณกับอัตราค่าบริการที่ กำหนดสำหรับที่ว่างที่รถยนต์คันนั้นเข้าจอด   โดยค่าจอดรถนี้จะไม่ขึ้นกับระยะเวลาที่รถยนต์จอดอยู่ในโรงจอดรถแห่งนี้

 

ผู้ดำเนินกิจการโรงจอดรถแห่งนี้จะทราบว่า   วันนี้จะมีรถยนต์เข้ามาจอดจำนวน M คันและเขาก็ยังทราบลำดับการมาถึงและออกจากโรงจอดรถแห่งนี้ของรถยนต์เหล่านี้อีกด้วย   เรามาช่วยเขาคำนวณหารายได้ในหน่วยดอลลาร์ที่เขาจะได้รับในวันนี้กันเถอะ

 

งานของคุณ

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

 

เงื่อนไข

1 N 100           คือ จำนวนของที่ว่างสำหรับจอดรถ

1 M 2 000       คือ จำนวนรถยนต์

1 Rs 100          คือ อัตราค่าบริการของที่ว่างหมายเลขที่ s   ในหน่วยดอลลาร์ต่อกิโลกรัม

1 Wk 10 000    คือ น้ำหนักของรถยนต์คันที่ k   ในหน่วยกิโลกรัม

 

ข้อมูลนำเข้า

โปรแกรมของคุณจะต้องรับข้อมูลเข้ามาทางคีย์บอร์ด   ดังนี้

  • ในบรรทัดแรก    จะประกอบด้วยเลขจำนวนเต็ม N และ M   แยกกันด้วยช่องว่าง 1 ช่อง
  • N บรรทัดถัดมา  ให้อธิบายอัตราค่าบริการของที่ว่างสำหรับจอดรถหมายเลขต่าง ๆ   โดยบรรทัดที่ s ของบรรทัดเหล่านี้จะประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวคือ  Rs  แสดงอัตราค่าบริการของที่ว่างสำหรับจอดรถหมายเลขที่ s   ในหน่วยดอลลาร์ต่อกิโลกรัม
  • M บรรทัดถัดมา        ให้อธิบายน้ำหนักของรถยนต์แต่ละคันตั้งแต่คันที่ 1 ถึง M     โดยบรรทัดที่ k ของ M บรรทัดเหล่านี้จะประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวคือ Wk   แสดงน้ำหนักของรถยนต์คันที่ k    ในหน่วยกิโลกรัม
  • 2 * M บรรทัดถัดมา   ให้อธิบายการมาถึงและออกจากโรงจอดรถแห่งนี้ของรถยนต์ทุกคันเรียงตามลำดับเวลา   เลขจำนวนเต็มบวก i ให้แสดงการมาถึงโรงจอดรถแห่งนี้ของรถยนต์คันที่ i    ส่วนเลขจำนวนเต็มลบหรือ –i  ให้แสดงการออกจากโรงจอดรถแห่งนี้ของรถยนต์คันที่ i   ไม่มีรถยนต์คันไหนที่ออกจากโรงจอดรถแห่งนี้ก่อนที่มันจะมาถึงที่นี่และรถยนต์ทุกคันตั้งแต่คันที่ 1 ถึง M  จะปรากฏเพียงแค่ 2 ครั้งในลำดับนี้เท่านั้นคือ ครั้งแรกเมื่อมันมาถึงและครั้งที่ 2 เมื่อมันออกจากโรงจอดรถแห่งนี้   นอก จากนี้ ไม่มีรถยนต์คันไหนที่จะออกจากโรงจอดรถแห่งนี้ก่อนที่มันจะได้จอดรถที่นี่ (ยกตัวอย่างเช่น ไม่มีรถยนต์คันไหนที่จะออกจากโรงจอดรถแห่งนี้ในขณะที่มันกำลังรอคิวเพื่อ เข้าจอด)

 

ข้อมูลส่งออก

โปรแกรมของคุณจะต้องแสดงผลออกมาทางจอภาพในบรรทัดเดียว   ซึ่งประกอบด้วยเลขจำนวนเต็มเพียงค่าเดียวคือ   จำนวนเงินทั้งหมดในหน่วยดอลลาร์ที่ผู้ดำเนินกิจการโรงจอดรถแห่งนี้จะได้รับในวันนี้

 


การให้คะแนน

สำหรับชุดทดสอบ   จะมีค่า 40 คะแนน   เมื่อมีที่ว่างสำหรับจอดรถอย่างน้อย 1 ที่สำหรับรถยนต์ทุกคันที่เข้ามาที่โรงจอดรถแห่งนี้   ซึ่งในกรณีนี้จะไม่มีรถยนต์คันไหนที่จะต้องรอที่ว่างเลย

ที่มา: 21st International Olympiad In Informatics August 8 - 15, 2009 (Day 2)

 


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3 4
2
3
5
200
100
300
800
3
2
-3
1
4
-4
-2
-1
5300

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 18 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)