Una benzinera massa llunyana P23800


Statement
 

pdf   zip

html

Les n+1 ciutats c0, …, cn estan connectades consecutivament per una única carretera. Voleu anar des de c0 fins a cn, parant com a molt p vegades per omplir el dipòsit del cotxe. Només hi ha betzineres a les ciutats, no en els trams intermedis. La longitud de cadascun dels n trams és ℓ0, …, ℓn−1. Quina autonomia mínima ha de tenir el vostre cotxe? Suposeu que comenceu amb el dipòsit ple.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i p, seguits de n naturals ℓ0, …, ℓn−1. Suposeu 1 ≤ n ≤ 105, 0 ≤ p ≤ n − 1, i 1 ≤ ℓi ≤ 104.

Sortida

Per a cada cas, escriviu l’autonomia mínima que ha de tenir un cotxe per poder arribar fins a cn sortint de c0 fent com a màxim p parades per omplir el dipòsit.

Pista

Considereu una versió decisional d’aquest problema.

Public test cases

  • Input

    5 0
100 300 500 200 400
5 1
100 300 500 200 400
5 2
100 300 500 200 400
5 3
100 300 500 200 400
5 4
100 300 500 200 400

    Output

    1500
900
600
500
500
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python
    User solutions
    C++ Python