Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | oneouts.in, oneouts.out | Sursă | Algoritmiada 2016 - Runda 4 - Seniors |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
One Outs
Tokuchi Toua are un nou meci de baseball pe care trebuie sa il castige. Putem considera ca terenul de baseball este un poligon cu N varfuri in plan iar Toua (pitcherul) se afla intr-un punct din interiorul poligonului. Toua poate sa pozitioneze un coechipier in unul din cele N puncte. In momentul in care coechipierul primeste mingea, acesta incepe sa alerge pentru a realiza un home-run (incepe sa alerge de-alungul perimetrului poligonului pana ajunge in punctul altui coechipier). Scopul este sa pozitionam unul sau mai multi coechipieri astfel incat acestia sa acopere tot perimetrul poligonului intr-un timp cat mai scurt.
Pentru simplitate, consideram a fi cunoscute duratele de parcurgere ale muchiilor între oricare doua puncte consecutive de pe poligon, precum si timpul necesar pentru a arunca mingea in fiecare din cele N puncte. Timpul necesar al unui coechipier pentru a isi termina home-run-ul este calculat in felul urmator: timpul pana primeste mingea de la pitcher + timpul pe care acesta il parcurge din punctul in care se afla pana in punctul urmatorului coechipier. Toua poate sa pozitioneze maxim K coechipieri in K din cele N puncte. Voi trebuie sa il ajutati sa realizeze acest lucru astfel incat timpul maxim al unui coechipier in a isi realiza home-run-ul sa fie minim.
Date de intrare
Fişierul de intrare oneouts.in pe prima linie 2 numere naturale N si K. Pe urmatoarea linie vor fi N numere naturale reprezentand distanta intre oricare 2 puncte consecutive de pe poligon (punctul 1 cu 2, 2 cu 3, .... , N cu 1). Pe linia 3 vor fi alte N numere naturale, al i-lea reprezentand timpul necesar pentru ca Toua sa arunde mingea din punctul in care se afla pana in punctul cu indicele i de pe poligon
Date de ieşire
Fişierul de ieşire oneouts.out va contine un singur numar natural reprezentand timpul minim cerut.
Restricţii
- 1 ≤ K <= N ≤ 100.000
- Toate valorile din input sunt din intervalul [1, 1.000.000.000]
- Poligonul menţionat în enunţ este fictiv. În general nu există nicio relaţie geometrică între timpii descrişi în fişierul de intrare.
Exemplu
| oneouts.in | oneouts.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
