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 |
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 ...
Date de ieşire
În fişierul de ieşire easyvect.out ...
Restricţii
- 1 ≤ 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 |
---|---|
This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...