Fişierul intrare/ieşire:morcovi.in, morcovi.outSursăAlgoritmiada 2009, Runda Finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.4 secLimită de memorie24096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Morcovi

Fermierul Ion are o gradina formata din N zone patratice cu latura de 1 metru, asezate una dupa alta, in linie. In fiecare astfel de zona creste cate un morcov magic. Pentru fiecare morcov este cunoscuta valoarea sa energetica. Rila Iepurila, iepurele buclucas, a invadat gradina fermierului si a inceput sa manance morcovii. Iepurasul urmeaza un anumit traseu si mananca integral morcovii din zonele prin care trece. Dupa ce un morcov este mancat, creste altul in loc, de aceeasi valoare energetica (nu uitati ca morcovii sunt magici iar gradina este una imaginara). Gradul de satisfactie al lui Rila este dat de suma valorilor energetice ale morcovilor pe care ii mananca.
Pentru ca iepurele este un animal destept, traseul acestuia are anumite caracteristici. Rila incepe dintr-o zona oarecare si executa un numar P de salturi iepuresti, astfel incat prin salturile sale sa nu paraseasca niciodata gradina. Fermierul, dupa ce a studiat comportamentul iepurelui pentru o perioada lunga de timp, cunoaste acum lungimile celor P salturi ale iepurelui si stie ca acesta executa toate aceste salturi intr-o ordine oarecare.
Sa se determine gradul de satisfactie maxim pe care il poate obtine iepurele.

Date de intrare

Fisierul de intrare morcovi.in contine pe prima linie N, numarul de zone ale gradinii. Pe a doua linie din fisier se gasesc N numere naturale, al i-lea numar de pe aceasta linie indicand valoarea energetica a morcovilor ce cresc in zona a i-a. Cea de a treia linie din fisier contine numarul P, numarul de salturi pe care le face iepurele. Ultima linie contine P numere naturale, intr-o ordine oarecare, indicand lungimile salturilor iepurelui.

Date de iesire

Pe prima linie a fisierului de iesire morcovi.out se gaseste un singur numar natural, reprezentand gradul maxim de satisfactie ce poate fi obtinut de iepurele Rila in traseul sau prin gradina fermierului.

Restrictii

  • 2 ≤ N ≤ 1 000
  • 1 ≤ P ≤ 12
  • Valoarea energetica a unui morcov este un numar natural din intervalul [1, 100 000 000]
  • Fiecare lungime din cele P este mai mica decat N
  • Un salt din zona x in zona y are lungimea |x-y|

Exemplu

morcovi.inmorcovi.out
7
1 20 3 1 1 40 10
3
1 2 4
71

Explicatie

Iepurele porneste din casuta 4. De acolo executa un salt de lungime 2 spre stanga, pana in casuta cu morcovul de valoare 20. Apoi executa pe rand salturile de lungime 4 si 1 spre dreapta, mancand si morcovii cu valorile 40 si 10. Gradul de satisfactie este 1+20+40+10 = 71.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content