COINS - balkanijade

Test 1 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 6 Pogresno resenje vreme izvrsavanja programa 0.23 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.06 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 9 Sistemska greska ili prekoracen memorijski limit
Test 10 Sistemska greska ili prekoracen memorijski limit


7.000.000 je organicenje!!! To je previse i pada na memoriski limit.

Radio sam slicno kao bankomati sa nekim dodatcima i proveravam samo do 1.000.000 , pa sam siguran da zato 6ti primer daje "Pogresno resenje "

Pomoc molim od onih koji su ga resili .
Hvala

u checkeru za taj zadatak postoji jedan bug.
no, necu vam reci koji :).
A, sto se resenja tice..
Pa, ja sam ga uradio bfs-om..
Inace, sigran sam da se za moje resenje moze naci
test primer koji bi ga oborio na vremenu..
ali za sve sa z-treninga prolazi..i to prilicno brzo..
ono sto sam radio je kada nadjem neko vreme stizanja
bfs-a koje je manje od greedy-a za tu vrednost i ako
je ta vrednost najvise za (recimo) 20 veca od A
onda prekidam bfs i ispisem resenje..

Mozes da mi pises na private za taj bug, ili da mi das neki hint ??? PLSSS ne vidim drugi izlaz

za bug ti necu reci..
a za ideju..pa eto, rekao sam..
ako znas sta je bfs( breadth-first search ), onda bi trebalo da je skontas.
U sustini, umesto dinamickog, za racunanje minimalnog broja
potrebnih novcica da se isplati neka suma, moze se "pustiti" bfs..

Znam sta je bfs .
Aj probacu da skontam pa cu te pitat ponovo

Jos uvek se drzim moje ideje. Dinamicko. I malo samo napredovao

Test 1 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 2 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 3 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 4 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 5 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 6 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 7 Tacno resenje vreme izvrsavanja programa 0.02 sekunde
Test 8 Tacno resenje vreme izvrsavanja programa 0.03 sekunde
Test 9 Sistemska greska ili prekoracen memorijski limit
Test 10 Sistemska greska ili prekoracen memorijski limit


Dali mogu nekako ovo da smanjim da bi proslo?

int M;
    unsigned long int i,j;
    long int m[101];
    vector<long int> G;  //greedy
    vector<long int> DP;   //dinamicko
    long int x,y;
    long int ispisi[1000001];    //Pomaze mi da ispisem vrednosti 
    long int C[1000001];     // ovde pamtim parice koje sam upotrebio u DP
    
    long int max=0,s;
    

sumnjam..
cisto dinamicko ne moze proci ( bar ja tako mislim )..
9. i 10. test su jedino komplikovani..ovi ostali su lagani..