2175: Прибирання

Перегляд у форматі PDF
Надіслати розв'язок
Бали: 20,00 (partial)
Time limit: 4.0s
Memory limit: 1G
Input: stdin
Output: stdout
Problem type

У розпал заходів зі збору сміття, улюблена вулиця Леді була заповнена величезною кількістю листя від типового осіннього листопада.

Оскільки Леді дуже любить чистоту, вона поставила собі завдання прибрати тротуар на вулиці.

Точніше, тротуар має ~N~-метрову довжину, розділений на ~N~ однометрові секції, пронумеровані відповідно до їхнього положення зліва направо вздовж вулиці, де на ~i~–й секції зібрано ~V_i~ кубічних метрів листя. Кожен кубічний метр листя важить 1 кілограм. За 1 метр ліворуч від першої секції тротуару знаходиться колекція з ~K~ сміттєвих пакетів, відповідно, кожен з них міг би вмістити всю кількість листя на тротуарі. Кожен пакет має свою вагу ~C~. Для спрощення позначимо джерело пакетів як позицію 0.

Спочатку Леді знаходиться поруч із джерелом пакетів. Щоб очистити тротуар, вона може виконати кілька дій. Нехай вона знаходиться в секції ~X~ і несе ~W~ кілограмів (загальна вага пакета та листя). Тоді вона може:

  • зібрати 1 кілограм листя з поточної секції, в якій вона знаходиться (~V_X → V_X - 1~), та покласти їх у свій пакет. Вона повинна мати ~X > 0~ та ~V_X > 0~, що коштуватиме їй 0 одиниць зусиль.
  • переміститися на одну секцію ліворуч (~X → X - 1~), якщо ~X > 0~. Це коштуватиме їй ~W~ одиниць зусиль.
  • переміститися на одну клітинку праворуч (~X → X + 1~). Вона повинна мати ~X < N~ та ~V_X = 0~, інакше їй буде важко пройти крізь листя. Це коштуватиме їй ~W~ одиниць зусиль.
  • залишити поточний пакет для листя біля джерела. Вона повинна мати ~X = 0~ і залишити собі пакет для листя, що коштуватиме їй 0 одиниць зусиль.
  • взяти пакет для листя біля джерела. Вона повинна мати ~X = 0~ і не залишати пакет для листя, що коштуватиме їй 0 одиниць зусиль.

Мета Леді – зібрати все листя на тротуарі в пакети, і кожен пакет має бути на початку після завершення прибирання.

Напишіть програму, яка знаходить мінімальну кількість зусиль для прибирання тротуару.

Формат вхідних даних:

Перший рядок містить три цілих числа ~N, K, C~ (~1 ≤ K ≤ N ≤ 10^6~) – довжина тротуару, кількість пакетів та вага кожного пакета.

Другий рядок вхідних даних містить ~N~ додатних цілих чисел ~V_1~ ~V_2~ … ~V_N~ (~1 ≤ V_i ≤ 10^{12} ,~ ~\sum_{i=1}^{N}V_i \le 10^{12}~- кількість листя на ділянках.

Формат вихідних даних:

Виведіть одне ціле число – мінімальні зусилля для очищення тротуару.

Система оцінювання:

Бали за кожну підзадачу нараховуються за умови проходження усіх тестів підзадачі, залежності від підзадач немає.

Приклади вхідних даних:

7 4 1
4 3 6 8 2 10 1

Приклади вихідних даних:

199

Приклади вхідних даних:

8 2 1
2 1 1 3 1 2 1 4

Приклади вихідних даних:

133

Приклади вхідних даних:

8 2 100
2 1 1 3 1 2 1 4

Приклади вихідних даних:

1765

Коментарі

Please read the guidelines before commenting.


  • 1
    pcheloveks69  commented on Гру. 4, 2025, 9:44 до полудня

    Чи правильний третій приклад ? Бо якщо пакет важить 100 банальне дійти і повернутися до останього елемента має коштувати >= 1600 зусилля.


    • 0
      judge  commented on Гру. 4, 2025, 9:54 до полудня

      так, правильний


      • 0
        pcheloveks69  commented on Гру. 4, 2025, 10:01 до полудня

        І чому коли відправляю код який виводить приклад він дає Wa на ньому?


      • 0
        pcheloveks69  commented on Гру. 4, 2025, 9:59 до полудня

        Тоді як там отримати 1008?


        • 0
          zvit  commented on Гру. 4, 2025, 10:47 до полудня

          так, дійсно, відповідь у цьому прикладі - 1765, виправив


        • -5
          BabaYaga  commented on Гру. 4, 2025, 10:36 до полудня

          This comment is hidden due to too much negative feedback. Show it anyway.