1408 Calancea

[•a_h1926]

Aici puteti discuta despre problema Calancea.

Multumim lui Eugenie Daniel Posdarascu pentru adaugarea problemei.

[•ctlin04]

Mai dati inca putina memorie ( macar 4 Mb ) ca nu ma pot incadra nicidecum in limita curenta. 

[•a_h1926]

Aceasta este limita de memorie din timpul concursului. Tu nu ai solutia optima (ai complexitate N * logN). Foloseste un deque pentru a obtine complexitate O(N) si atunci vei consuma mai putina memorie.
De exemplu, solutia mea cu un deque se incadreaza in 4 Mb.
Spor!

[•vendetta]

Cum pot scapa de MLE ?

[•a_h1926]

In solutia mea am parcurs sirul de la dreapta la stanga, iar in deque tineam doua informatii: i, pozitia elementului, si next, pozitia primului element din dreapta care e mai mare (in cazul in care nu exista un element mai mare ca el in secventa curenta, retin capatul din dreapta al secventei). Astfel, nu mai am nevoie sa folosesc sume partiale sau alte precalculari care consuma multa memorie.

Totusi, acum am observat ca in concurs, limita de memorie era de 64 MB. Cand a fost adaugata problema la lot nu am observat ca nu corespunde limita de memorie si am presupus ca este corecta. Ne cerem scuze.