| 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
Tanarul nobil Naelav doreste sa cucereasca inima prea frumoasei si priceputei Adnana, fata regelui Arpsod, stapanul regatului Valores. El se gandeste sa o impresioneze facand niste armuri cu totul si cu totul din haur pentru dragonii ei. Tatal sau refuza insa sa cheltuiasca atat de multi bani pentru o pasiune adolescentina asa ca Naelav paraseste regatul amenintand oamenii cu catapulta sa, care arunca blaturi tari ca piatra.
Regatul Valores este alcatuit din N orase dispuse in linie. Astfel din orasul i se poate ajunge in orasele i+1 si i-1, exceptie facand orasele 1 si N. Urmeaza o lunga serie de x episoade. In fiecare episod, Naelav asediaza un anume oras i, sustrage din visteria acestuia vi monezi de haur si porneste catre unul din orasele adiacente. El poate ataca un oras de mai multe ori pentru aceeasi suma, dar nu in episoade consecutive. Stim ca primul oras ce a fost deja asediat este chiar orasul sau natal, orasul cu numarul 1.
Pentru a putea da cat mai multe spoilere prietenilor tai, te gandesti sa aflii care ar fi valoarea maxima pe care ar putea-o colecta Naelav in urmatoarele x episoade, in Q astfel de scenarii.
Date de intrare
Fişierul de intrare easyvect.in contine pe prima linie numarul T, numarul de teste. Fiecare test va contine numerele N si Q numarul de orase, respectiv numarul de intrebari si un sir de N numere pe linia urmatoare, reprezentand cantitatea de monezi care se pot obtine vi din fiecare oras intr-un episod. Pe urmatoarele Q linii sunt descrise numerele x, reprezentand numarul de episoade pe care le-ar putea avea serialul.
Date de ieşire
În fişierul de iesire easyvect.out se vor afisa T*Q linii, cate una pentru fiecare query.
Restricţii
- 1 ≤ T ≤ 10
- 2 ≤ N ≤ 10^5
- 1 ≤ Q ≤ 10^5
- 1 ≤ vi ≤ 10^5
- 1 ≤ x ≤ 10^9, pentru fiecare query din cele Q
- Atentie! Rezultatul poate depasi numere pe 32 de biti.
- Naelav este mai mult taran decat nobil
- Suparat ca nu o poate cuceri pe Adnana, Naelav se inchide in camera sa si se joaca cu dragonul sau micut.
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.
