Poate nu-ti mai iese din memorie daca folosesti o coada circulara...

Pei dupa ce am pus in coada primele N - 1 elem si am facut sume partiale...in deque o sa-mi bag suma partiala minima la un pas astfel incat secventa sa nu-mi depaseasca N elemente...si la fiecare pas i aleg si smax = MAX(S[ i ] - St[s1], smax) (unde St este deque-ul meu iar s1 primul pivot, pozitia sumei partiale minime, iar S este vectorul de sume partiale). In ce priveste constructia deque-ului ar trebui sa incerci pe o foaie sa vezi cum sta treaba. 

Ca sfat ti-as zice sa lucrezi problema Secventa...

Ca sa mearga mai repede tin minte ca eu am setat un bufer de o anumita dimensiune, ca sa se produca citirea mai repede.    Puteti sa va uitati in sintaxa de C++ la "setbuf" si sa testati si metoda asta.

Ai putea sa faci si deque intradevar (eu asa am facut  ). Dublezi sirul, defapt mai adaugi primele N - 1 elemente la coada, faci sume partiale si astfel poti calcula secventa de suma maxima de lungime <= N (care reprezinta si raspunsul problemei). 

am o nelamurire: de ce merge mai repede scanf("%s", s) decat scanf("%d", &d) ??
pt trecerea de la 80 (in caz ca faci hash iar ultimele 2 teste iau cam ~1.530 ms) la 100 am parsat citirea dar nu am folosit gets() pt ca luam WA pe ult 2 teste (nush de ce??  ) si am folosit scanf("%s", s) , iar spre uimirea mea a intrat in timp! ceva opinii?   

Si eu am avut o problema asemanatoare...luam 60p (4 TLE) si aveam variabile de tip double (cautare pe double, comparare pe double)...cand am schimbat in float am luat 85...si cand am schimbat si ABS-ul de mana cu fabs am luat 100...
Aveti vreo idee de ce s-a intamplat asta?

Imi poate explica si mie cineva mai pe indelete sol. a doua din articol de la Radiatie? Din cate stiu eu, chiar daca nu folosesti comprimare de drumuri, arborele partial de cost minim tot va fi un arbore degenerat. Daca ai face o simpla parcurgere pe acest arbore ar putea sa te duca la un raspuns gresit pt. ca ai putea avea nevoie de o muchie X - Y pe care nu o ai in arborele respectiv , dar caruia i-ai introdus capetele unindu-le cu un reprezentant Z ...si o sa ai muchie de la X la Z si de la Y la Z, muchii carora poate nici macar nu le sti costul. 

Multumesc!   

ok...dar tot as dori sa stiu ce afiseaza sursa mea pe testele 3-4 ca sa ma pot prinde makr unde gresesc...pt ca am testat si pe Win/Linux si testele imi merg...   

am o problema...am testat testul 4 (care este pe forum) si imi da acelasi rezultat (ca output-ul) si pe Win si pe Linux ...cred ca este o problema cu evaluatorul  ?!?! Ma poate ajuta cineva si sa-mi spuna ce afiseaza sursa mea pe cele 2 teste (3 si 4)...ca nu ma prind dak as fi gresit niste indici sau altceva! Eu rezolv cu forma poloneza post fixata si folosesc numai stive implementate manual...si am testat sa vad dak imi depaseste indicele pt stiva! 
Am mai testat si pe alte exemple pe Linux/Win si nu am probleme...

foloseam dinamica inainte dar m-am prins de niste chesti care imi buseau matricea respectiva si am mai si optimizat....am inlocuit modulo cu scadere (e mult mai rapid in cazul acesta) si desi am folosit memorie dinamica a fost ok  !  mersi oricum pt sfaturi guys !

PaulDB:
Mocke: Eu nu inteleg o chestie la rezolvarea ta: cum ai redus memoria la dinamica fara sa sortezi? Sau ce intelegi tu prin faptul ca"ai optimizat memoria la dinamica"?

RE:am optimizat folosind memorie dinamica....nu memoria la dinamica! 

Pt filipb: ai dreptate cu dinamica inainte asa si facusem ... dak faceai dinamica inapoi foloseai mai multa memorie iar complexitatea putea sa ajunga si la n^2*(nr de scanduri teleportatoare) care nu se prea amortiza

am si eu o nedumerire!??!?!  complexitatea oficiala e O(M+N*K), unde K presupun ca e maximul de pasi din lista de query-uri. Eu aveam o complexitate care ajungea maxim la O(4001*4001) pe fiecare test...si luam TLE la ultimele 6 teste . Bun. Am optimizat in O(M+N*K), memorie dinamica,etc. tot iau TLE la aceleasi teste. Poate cineva sa-mi dea o alta idee de optimizare. Totusi mi se pare cam ciudat ca O(16 mil) nu intra in 1s?! 

ma poate lamuri si pe mine cineva DE CE NU este centrul de greutate acel punct....multi oameni mi-au spus ca este....printre ei se numara si olimpici la mate....!!!   ...as dori o demonstratie dak se poate , in caz ca nu este....ori poate are problema o chichita...poate distanta nu se masoara normal....nu mai stiu ce sa zic... :cry:  

Am si eu o nelamurire...dak aleg punctul ca centru de greutate suma distantelor de la centru la pctele din exemplu este mai mica decat suma distantelor de la pct ales corect si pctele din exemplu....am gresit eu la calcul sau e adevarat ce spun?  

puteti sa-mi dati si mie un hint la problema aceasta pls ....nu ma prind cum ar veni formula....?!  

d c e afisata matricea asa de ciudat?....chestia aia m-a indus in eroare! am crezut ca trebuie sa fac o afisare identica ! uitati-va la coloana cu numere pozitive si observati ca e mai in stanga!  

incearca sa pregenerezi intr-o matrice solutiile...mat[nrdiv]=i
unde nrdiv=numarul de div ai lui i....copiezi in mat[j]->mat[i-1][j] dupa care actualizezi cu mat[nrdiv]=i! o sa ai raspuns pt test in O(1).
-nrdiv il calculezi folosindu-te de divizorii primi si de multiplii lui  

am luat 100....am pus vect de ct in main pana la 320 si a mers...mersi de ajutor!

iau intr-una la testul 9 - 0 pcte....restul imi merg! poate sa ma ajute cineva?
este singurul care imi iese din timp si nush de ce?! :cry:
...si sunt sigur ca nu e din cauza ciurului ca am observat ca testele sunt km mici si merge sa scoti un ciur si pana la 9000 ...ma poate ajuta cineva sa imi dau seama de vreo greseala pe care o fac?  

cum se face problema aceasta in O(n^6)....parcurgand sirul de la capat e acelasi lucru cu a-l parcurge de la inceput...nu e nici o diferenta si tot iese din timp nu am idee cum s-au luat 95 de puncte sau chiar 100 folosindu-se complexitatea asta