Problem type : Batch
Time limit : 0.4 second(s)
Memory limit : 64 megabyte(s)
อนุภาคแบบสั่งทำพิเศษจำนวน N อนุภาควางเรียงกัน (โดยที่ N เป็นจำนวนเต็มคู่) เราจะเรียกอนุภาคดังกล่าวว่าอนุภาคที่ 1, 2, ..., ถึง อนุภาคที่ N ตามลำดับ อนุภาคแต่ละอนุภาคจะมีค่าพลังงานสะสมอยู่ กล่าวคืออนุภาคที่ i จะมีพลังงานสะสมเท่ากับ Xi หน่วย
อนุภาค สองอนุภาคใด ๆ ที่อยู่ติดกันเมื่อนำมาชนกัน จะสลายตัวและปล่อยพลังงานออกมา โดยพลังงานที่ปล่อยออกมานั้น มีค่าเท่ากับผลต่างของพลังงานสะสมของอนุภาคทั้งสอง สังเกตว่าเมื่ออนุภาคชนกันแล้วจะสลายไปทั้งคู่ ทำให้อนุภาคคู่อื่น ๆ ที่เมื่อเริ่มต้นไม่ได้มีตำแหน่งติดกัน มีลำดับอยู่ติดกันได้
ตัวอย่างการดำเนินการเป็นดังนี้ สมมติมีอนุภาค 6 อนุภาคที่มีพลังงานสะสมดังนี้
1 2 4 3 1 2
คุณเลือกชนอนุภาคที่ 2 กับ 3 ได้พลังงาน 2 หน่วย หลังจากนั้นเราจะเหลืออนุภาค 5 อนุภาค
1 3 1 2
เลือกคู่อนุภาค 1 กับอนุภาค 4 ได้พลังงาน 2 หน่วย
1 2
เลือกคู่อนุภาค 5 กับอนุภาค 6 ได้พลังงาน 1 หน่วย รวมแล้วได้พลังงานทั้งหมด 5 หน่วย
หัวหน้าห้องปฏิบัติการวานให้คุณหาวิธีนำอนุภาคทั้ง N อันมาชนกัน โดยให้คุณหาวิธีการชนที่ทำให้พลังงานรวมสุดท้ายมากที่สุด
งานของคุณ
รับข้อมูลพลังงานสะสมของอนุภาค จากนั้นคำนวณหาพลังงานรวมสูงสุดที่สามารถทำได้จากการชนอนุภาค
ข้อมูลนำเข้า
บรรทัดแรก ระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000) แทนจำนวนอนุภาค
อีก N บรรทัด ระบุพลังงานสะสมของแต่ละอนุภาค กล่าวคือ บรรทัดที่ 1 + i จะระบุจำนวนเต็ม Xi (1 ≤ Xi ≤ 1,000,000,000) แทนพลังงานสะสมของอนุภาคที่ i
ข้อมูลส่งออก
มีบรรทัดเดียว คือพลังงานรวมทั้งหมดที่ได้รับ
การให้คะแนน
50% ของชุดข้อมูลทดสอบมีค่า 1 ≤ N ≤ 300
80% ของชุดข้อมูลทดสอบมีค่า 1 ≤ N ≤ 100,000
100% ของชุดข้อมูลทดสอบมีค่า 1 ≤ N ≤ 1,000,000
ทีมา: โจทย์ข้อสอบ สสวท. ค่ายที่ 2 ระยะที่ 1 ปี 2552 โดย ดร.จิตร์ทัศน์ ฝักเจริญผล และแนวคิดของพศิน มนูรังษี
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| 6 1 2 4 3 1 2 | 5 |
| 4 20 17 15 12 | 10 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้