Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | easyvect.in, easyvect.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Easyvect
Comisia AGM mai avea nevoie de o problema usoara. Stiind ca Elf nu a fost in stare sa treaca de OJI, se gandesc sa-i dea lui responsabilitatea. El stie cel mai bine vectori din toata informatica, asa ca se gandeste sa dea o problema usoara cu ei.
Aveti un vector a cu n elemente pozitive si q query-uri. Un query este dat de un numar x. Initial porniti din pozitia 1 a vectorului. Trebuie sa va plimbati x unitati de timp. Din pozitia 1, puteti ajunge doar in pozitia 2. Din pozitia n, puteti ajunge doar in pozitia n - 1. Altfel, din pozitia i se poate ajunge atat in pozitia i - 1, cat si in pozitia i + 1. Cand Elf este intr-o casuta, el aduna in sacul de valoare numarul scris acolo. Care este suma maxima pe care-o poate obtine dupa x timp? Si numarul aflat pe pozitia 1 intra in tolba de valoare!
Date de intrare
Fişierul de intrare easyvect.in contine pe prima linie numerele n si q. Pe urmatoarele q linii sunt descrise numerele x, corespunzatoare query-urilor.
Date de ieşire
În fişierul de ieşire easyvect.out se vor afisa q linii, cate una pentru fiecare query.
Restricţii
- 2 ≤ n ≤ 10^5
- 1 ≤ q ≤ 10^5
- 1 ≤ a[i] ≤ 10^5
- 1 ≤ x ≤ 10^9, pentru fiecare query din cele q
- Atentie! Rezultatul poate depasi numere pe 32 de biti.
Exemplu
| easyvect.in | easyvect.out |
|---|---|
| 1 3 2 5 2 1 1 2 | 7 12 |
Explicaţie
Pentru primul query, traseul ales este 5->2 si are suma 7.
Pentru al doilea query, traseul ales este 5->2->5 si are suma 12.
