== include(page="template/taskheader" task_id="purification") ==
După ce a cucerit Tarsonis, Tassadar a trecut la purificarea planetei Zerus. Această planetă este infestată şi are $N$ cuiburi zerg. Cuiburile sunt numerotate de la $0$ la $N - 1$ şi, în fiecare oră, cuibul $i$ produce $W{~i~}$ zerglingi. Iniţial, pe planetă nu exista niciun zergling.
Un cuib este fie autonom, fie susţinut vital de un alt cuib. Dacă un cuib autonom este distrus, atunci producţia de zerglingi din acest cuib încetează şi toate cuiburile susţinute vital de acesta devin autonome. Dacă un cuib susţinut vital de un alt cuib este distrus, acesta se regenerează instantaneu, iar producţia de zerglingi rămâne neîntreruptă.
Tassadar poate distruge un cuib instantaneu folosind laserul de purificare de pe nava "Spear of Adun". Înainte să tragă, laserul trebuie să se încarce timp de o oră şi se descarcă de fiecare dată când trage. Iniţial, laserul este descărcat.
Tassadar vrea să distrugă permanent toate cuiburile, astfel încat la final să existe un număr minim de zerglingi.
Ajutaţi-l pe Tassadar să purifice planeta!
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $purification.in$ conţine pe prima linie numărul $N$ de cuiburi. Pe următoarea linie se vor afla $N$ numere $W{~i~}$, semnificând numărul de zerglingi produşi de cuibul $i$ într-o oră. Pe linia următoare se vor afla alte $N$ numere $F{~i~}$, reprezentând cuibul care susţine vital cuibul $i$, sau $-1$ în cazul în care cuibul $i$ este autonom.
Fişierul de intrare $purification.in$ ...
h2. Date de ieşire
Fişierul de ieşire $purification.out$ va conţine pe prima linie numărul minim de zerglingi rămaşi pe planetă după distrugerea permanentă a tuturor cuiburilor.
În fişierul de ieşire $purification.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 2000$
* $0 ≤ W{~i~} ≤ 500$
* Se garantează că pot fi distruse permanent toate cuiburile
* Pentru teste în valoare de $10$ puncte, $N ≤ 10$
* Pentru teste în valoare de alte $10$ puncte, $N ≤ 20$
* Pentru teste în valoare de alte $10$ puncte, $N ≤ 50$
* Pentru teste în valoare de alte $10$ puncte, $N ≤ 200$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. purification.in |_. purification.out |
| 6
1 5 3 2 1 50
-1 0 0 1 1 -1
| 95
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Ordinea optimă de distrugere a cuiburilor este $(5, 0, 1, 2, 3, 4)$. Cuibul $5$ (autonom) este distrus după o oră, deci produce $1 * 50$ zerglingi. Cuibul $0$ (autonom) este distrus după două ore, deci produce $2 * 1$ zerglingi. Cuibul $1$, iniţial, este susţinut vital de cuibul $0$, dar acum este autonom şi este distrus după trei ore, deci produce $3 * 5$ zerglingi. Cuibul $2$ este distrus după patru ore, deci produce $4 * 3$ zerglingi. Cuibul $3$ este distrus după cinci ore, deci produce $5 * 2$ zerglingi. Cuibul $4$ este distrus după şase ore, deci produce $6 * 1$ zerglingi. După ce toate cuiburile au fost distruse, iar producţia de zerglingi a încetat complet, numărul de zerglingi rămaşi este $1 * 50 + 2 * 1 + 3 * 5 + 4 * 3 + 5 * 2 + 6 * 1 = 95$.
...
== include(page="template/taskfooter" task_id="purification") ==
