Z-paradajz

Vajda e dinamicko, no kako?Moze malce pomos?

Ja mislim da je greedy sasvim ok. Mada, ako imas DP u br O(n log n), moze i to.

Moze detalji?

Koristio sam heap da strpam cene paradajza (usput sam cuvao i kad sam ga strpao - dan kupovanja). Heap je sortiran, naravno, po ceni. Najmanji el. u heapu je ono sto mi treba za i-ti dan (ako paradajzu sa vrha nije istekao rok trajanja).
Jel' ok sada?

    for( int i = 0; i < N; i++ ) {
        S.insert(make_pair( C[i], i ));
        while( i - S.begin()->second >= D ) S.erase( S.begin() );
        sol += S.begin()->first;
    }

Za ovo imam prekoračena vremenska ograničenja u zadnja 6 test primjera. Kako da ubrzam?

Rješenje sa set<>-om je presporo jer ima previše ubacivanja i brisanja elemenata ( a svako je u O( log n ) ).

Uspio sam riješiti pomoću tournament treea.  :)

Najjednostavnije je koristiti heap ili u stl-u prority_queue.