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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้