Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | sequencequery.in, sequencequery.out | Sursă | Bursele Agora 2006 |
Autor | Cosmin Silvestru Negruseri | Adăugată de | |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
SequenceQuery
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
Sequencequery
Se considera un sir A = (a1, a2, ... , a[N]) format din N numere intregi, precum si M perechi de numere ( x, y ). Pentru fiecare pereche de indici (x, y) (1 <= x <= y <= N) trebuie determinata subsecventa de suma maxima a subsirului a[x], a[x+1], ..., a[y] .
Date de Intrare
Fisierul sequencequery.in va contine pe prima linie doua numere intregi N si M . Urmatoarea linie va contine N numere intregi separate prin cate un spatiu. Acestea vor reprezenta numerele a1, a2, ... , a[N] . Urmatoarele M linii vor contine fiecare cate o pereche de doua numere separate prin cate un spatiu. Acestea vor indica perechile de indici pentru care trebuie determinate sumele maxime ale subsecventelor.
Date de Iesire
Fisierul sequencequery.out va contine M linii. Fiecare dintre acestea va contine cate un numar intreg care reprezinta suma elementelor din subsecventa considerata optima dupa criteriile exprimate in enuntul problemei.
Restrictii si precizari
. 1 <= N,M <= 100.000
. -100.000 <= a[i] <= 100.000
. subsecvetele alese trebuie sa contina cel putin un element.
Exemplu
sequencequery.in | sequencequery.out | Explicatie |
8 3 | 7 | [ -1 2 3 -2 4 ] -3 8 -3 |
-1 2 3 -2 4 -3 8 -3 | 9 | -1 2 3 [ -2 4 -3 8 -3 ] |
1 5 | -3 | -1 2 3 -2 4 [ -3 ] 8 -3 |
4 8 | ||
6 6 |