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 ≤ pn − 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++
    User solutions
    C++