დროის ლიმიტი: 2 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: პოლონეთი, ოლიმპიადა 15, ეტაპი 1
გიორგის პატარაობაში სამშენებლო ბლოკებით თამაში უყვარდა. თავიდან ის ბლოკებს სვეტებში შემთხვევითი სიმაღლით აწყობდა, შემდეგ კი ცდილობდა ისისნი შემდეგნაირად დაელაგებინა: გიორგი ირჩევდა რაღაც k რიცხვს და ცდილობდა ბლოკები დაეწყო ისე, რომ რომელიმე თანმიმდევრობით განლაგებული k სვეტი თანაბარი სიმაღლის ყოფილიყო. გარდა ამისა, ის ცდილობდა მიეღწია ამ მიზნისთვის სვლების მინიმალური რაოდენობით, სადაც ერთ სვლად ითვლება:
თუმცა გიორგი არასოდეს იყო დარწმუნებული იმაში, იყო თუ არა მისი სვლების თანმიმდევრობა ოპტიმალური, ამიტომ მან გთხოვათ თქვენ ისეთი პროგრამის დაწერა, რომელიც მას ამ პრობლემის გადაჭრაში დაეხმარება.
დაწერეთ პროგრამა, რომელიც:
შესატანი მონაცემები:
პირველ სტრიქონში შემოდის სფეისით გამოყოფილი ორი ინთეჯერი, n და k , სადაც (1 <= k <= n <= 100000) . მომდევნო n სტრიქონი შეიცავს რომელიღაც სვეტის სიმაღლეს; i+1-ე სტრიქონი შეიცავს ერთ ინთეჯერს 0 <= hi <= 1000000 - i-ური სვეტის სიმაღლე, ანუ იმ ბლოკების რაოდენობა, რომლებიც ამ სვეტის შემადგენლობაში შედის.
გამოსატანი მონაცემები:
უნდა გამოვიტანოთ ოპტიმალური ამოხსნა, ბლოკების ისეთი განლაგება, რომელიც:
ყოველი n+1 გამოსატანი ხაზი უნდა შეიცავდეს ერთ ინთეჯერს. პირველ სტრიქონში უნდა გამოვიტანოთ მინიმალური სვლების რაოდენობა, რომელიც დაგვჭირდა სასურველი შედეგის მისაღებად. i+1-ე სტრიქონი, სადაც (1<= i <= n), უნდა შეიცავდეს რიცხვს - hi, რომელიც არის i-ური სვეტის საბოლოო სიმაღლე. თუ არსებობს ერთზე მეტი ოპტიმალური ამოხსნა გამოიტანეთ ნებისმიერი მათგანი.
შესატანი მონაცემები
5 3 3 9 2 3 1 დაკოპირება
გამოსატანი მონაცემები
2 3 9 2 2 2 დაკოპირება