HELP .
Neka ideja?
Izgleada kao dinamicko.....
Neka ideja?
Izgleada kao dinamicko.....
z-rastanak
I jeste dinamicko. Na pravom si putu
Kljucno je sledece :
Ako osoba A zivi na mestu a i osoba B zivi na mestu b i pritom je a < b,
nikad ti se nece desiti da osobu A poshaljes na neko mesto c a osobu
B na neko mesto d tako da je d < c.
Razmisli o tome.. I trebalo bi da dobijes ideju.
Ako osoba A zivi na mestu a i osoba B zivi na mestu b i pritom je a < b,
nikad ti se nece desiti da osobu A poshaljes na neko mesto c a osobu
B na neko mesto d tako da je d < c.
Razmisli o tome.. I trebalo bi da dobijes ideju.
A moze li da neka osoba ode dalje od svoe kuce, pa da onda treba da se vraca nazad? Cini mi se da moze ali ipak da pitam.
Moze.
Pise mi na svim test primjerima Prekoraceno vremensko ogranicenj ili Memory limit.
Ja sam smislio cisto dinamicko slozenosti O(M*M) (M je najudaljenija kuca, tj, M <= 1000) a sama konstanta je svega par operacija.
Meni na kompu 1.83 Ghz s gxx-om bude vrijeme najvise 0.035 a sa -O2 optimizacijom 0.015 s i program mi uvijek zauzima 4 MB. U ovom zadatku pise ogranicenja 0.1 s i 16 MB. Iz iskustva znam da su mi znali proc programi koji su mi imali 0.6*dopusteno vrijeme na mom kompu tj. da je moj komp duplo brzi bez optimizacije kod kompilanja (po toj logici se tu izvodi 0.07 s u najgorem slucaju, tj. 0.03 s optimizacijom).
Kako je to moguce?
Ak nije TLE onda jel moguce da je opisu zadatka stavljen krivi Memory limit pa nije zapravo dopusteno koristit ni tih 4 MB???
Ja sam smislio cisto dinamicko slozenosti O(M*M) (M je najudaljenija kuca, tj, M <= 1000) a sama konstanta je svega par operacija.
Meni na kompu 1.83 Ghz s gxx-om bude vrijeme najvise 0.035 a sa -O2 optimizacijom 0.015 s i program mi uvijek zauzima 4 MB. U ovom zadatku pise ogranicenja 0.1 s i 16 MB. Iz iskustva znam da su mi znali proc programi koji su mi imali 0.6*dopusteno vrijeme na mom kompu tj. da je moj komp duplo brzi bez optimizacije kod kompilanja (po toj logici se tu izvodi 0.07 s u najgorem slucaju, tj. 0.03 s optimizacijom).
Kako je to moguce?
Ak nije TLE onda jel moguce da je opisu zadatka stavljen krivi Memory limit pa nije zapravo dopusteno koristit ni tih 4 MB???
Da bi video da li je do memorije, prosto izbaci iz main-a pozive
precompute();
solve_dp();
pa ako ti i onda bude pravilo probleme, zali se i dalje.
precompute();
solve_dp();
pa ako ti i onda bude pravilo probleme, zali se i dalje.
Cudno, stavio sam jedan if tak da ne pristupam polju na mjestu -1 i sad je proslo... Bila je sistemska greska zbog toga iako mi nije jasno zasto.
Pa najverovatnije zato sto mesto -1 ne postoji. Nisam siguran, ali moguce je da cak -1 = 2^16 ili 2^32, ako prima unsigned, mada to je samo nagadjanje. No, kako god bilo, moralo je da puca jer ti -1 ne postoji u memoriji, mislim kao referenca na deo niza.