1078 : รวมอนุภาค MAX (atom_max)
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

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

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