1107 : Jump
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

       ในโรงเรียนแห่งหนึ่ง นักเรียนที่นี่รักการโดดเรียนเป็นชีวิตจิตใจ อย่างไรก็ตาม โรงเรียนแห่งนี้มีกฎเหล็กคือ “นักเรียนคนหนึ่งสามารถโดดเรียนได้เพียงวันละ k ครั้งเท่านั้น โดยแต่ละครั้งจะต้องโดดเรียนไม่มากกว่า p คาบติดกัน แต่จะต้องเข้าเรียนอย่างน้อย 1 คาบในแต่ละวัน กล่าวอีกนัยหนึ่งได้ว่า นักเรียนสามารถเริ่มต้นโดดเรียนได้ k ครั้งโดยแต่ละครั้งจะโดดเรียนได้อย่างมาก p คาบติดกันแต่ไม่สามารถโดดเรียนทุกคาบเรียนได้

            Note การโดดเรียนแต่ละครั้งอาจกระทำต่อเนื่องกันได้ (พูดง่ายๆคือสามารถโดดเรียนติดกัน p*k คาบได้หากต้องการ)

            เป็นที่รู้กันในโรงเรียนว่าแต่ละคาบเรียนนั้น คาบเรียนมีความ “น่าเบื่อ” มากเพียงใด โดยคาบเรียนหนึ่งๆจะมีค่าความน่าเบื่อเฉพาะตัวแต่ละคาบ

            คุณก็เป็นนักเรียนคนหนึ่งในโรงเรียนแห่งนี้ซึ่งต้องการโดดเรียนอย่างคุ้มค่าที่สุด โดยในวันหนึ่งๆ จะมีคาบเรียนทั้งสิ้น n คาบ และคุณต้องการโดดเรียนโดยที่ ค่าของความน่าเบื่อของคาบที่เข้าเรียนที่น่าเบื่อมากที่สุดมีค่าน้อยที่สุด

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

บรรทัดแรกประกอบด้วยจำนวนนับ n, k และ p แทนจำนวนคาบ, จำนวนครั้งที่สามารถโดดได้ และความยาวนานของการโดดแต่ละครั้ง ( 1 < n < 1000 000 , 1 < k < 1000 000 , 1 < p < 1000 000 )

บรรทัดถัดมา n บรรทัดเป็นเลขจำนวนนับบรรทัดละ 1 จำนวน โดยบรรทัดที่ 1+i จะแสดงค่าความน่าเบื่อของคาบเรียนที่ i (1< ค่าความน่าเบื่อคาบที่ i < 1000 000 000 )

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

บรรทัดแรกและบรรทัดเดียวแสดงค่าของความน่าเบื่อที่มากที่สุด เมื่อคุณจัดการโดดเรียนแบบ ค่าของความน่าเบื่อของคาบที่เข้าเรียนที่น่าเบื่อมากที่สุดมีค่าน้อยที่สุด

โจทย์โดย : สรวิทย์  สุริยกาญจน์ ( PS.int )

ที่มา : ศูนย์ สอวน. โรงเรียนมหิดลวิทยานุสรณ์



ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
10 2 2
51
42
54
31
12
57
11
51
85
36
54
10 6 1
876035016
1354748
882042225
78564538
668028639
586686861
621124669
510077782
824111889
260600125
510077782

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

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