Una benzinera massa llunyana P23800
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.
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
- Author
- Salvador Roura
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++ Python
- User solutions
- C++ Python