Fişierul intrare/ieşire:oneouts.in, oneouts.outSursăAlgoritmiada 2016 - Runda 4 - Seniors
AutorEugenie Daniel PosdarascuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 necesar al unui coechipier pentru 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 timpul de parcurgere al distantei 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.
  • Cand coechipierii isi alearga home-run-ul ei trebuie sa se deplaseze spre dreapta, astfel daca ei sa afla la un moment in punctul N, atunci ei se vor deplasa in directia punctului 1, iar daca se afla intr-un alt punct i se vor deplasa in directia punctului i+1.
  • Pentru teste in valoare de 20% din punctaj N ≤ 20, iar toate celelalte valori din input sunt din intervalul [1, 10.000].
  • Pentru teste in valoare de 40% din punctaj N ≤ 1500.

Exemplu

oneouts.inoneouts.out
5 2
3 1 2 3 2
3 3 1 2 4
8

Explicaţie

Toua isi va amplasa cei 2 coechipieri in varfurile 1 si 3. Coechipierul din varful 1 isi va executa home-run-ul in 3(timpul necesar pentru ca Toua sa-i arunce lui mingea) + 3 + 1(timpul necesar sa alerge pana la pozitia celuilalt coechipier) = 7. Coechipierul din varful 3 isi va executa home-run-ul in 1(timpul pana va ajunge mingea la el) + 2 + 3 + 2 = 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?