Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2006-11-11 11:23:53.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:sequencequery.in, sequencequery.outSursăBursele Agora 2006
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.insequencequery.outExplicatie
8 37[ -1 2 3 -2 4 ] -3 8 -3
-1 2 3 -2 4 -3 8 -39-1 2 3 [ -2 4 -3 8 -3 ]
1 5-3-1 2 3 -2 4 [ -3 ] 8 -3
4 8
6 6
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?