879 Praslea

[•DITzoneC]

Aici puteţi discuta despre problema Praslea.

[•Florian]

Lipseste inceputul enuntului, cred. Textul incepe direct cu

evenimentele ce urmează să aibă loc în gradină.

[•andrei-alpha]

Da, am modificat 

[•zbarni]

Putin offtopic: codul urmator,

Cod:

for (int i=1;i<=1000000;++i)
		for (int j=1;j<=1000000;++j)
			for (int k=1;k<=1000000;++k);

de ce nu rezulta TLE?

[•wefgef]

Pentru ca e destept compilatorul si se prinde ca nu faci nimic in forurile alea, asa ca le ignora.

[•zbarni]

Inteleg. Mersi

[•Florian]

Iau 80 de puncte si 2 TLE. Sortez crescator dupa timpii de intrare. Apoi, imi tin intr-un heap zmeii aflati in gradina la un moment dat. Iau in ordine evenimentele ( intrare sau iesire, eliminand sau adaugand in heap ), si pt fiecare stare a heapului fac o dinamica ( dp[ i ][ j ]  =  forta maxima pe care o am, daca ma bat cu zmei din primii i zmei din heap, asumand un risc de fix j ), iar rezultatul dinamicii o inmultesc cu intervalul de timp pt care e valabila starea respectiva. Complexitatea este O(N^3) amortizat ( fiecare zmeu e introdus/scos o singura data ). Cum ar trebui optimizata? Multumesc.

[•repp4radu]

Cred ca ar trebui marita limita de timp. Pentru a intra in timp a trebuit sa imi pun 3/4 din variabile short sau unsigned short si sa parsez citirea.
Totusi iau un incorect avand variabilele declarate astfel desi pe testele oficiale iau corect si pe testul 10. S-au schimbat testele?

PS Am complexitate O(N^2 * R)