Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | purification.in, purification.out | Sursă | Lot Măgurele 2016 - Baraj 4 Seniori |
| Autor | Andrei Heidelbacher | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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!
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.
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.
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
Exemplu
| purification.in | purification.out |
|---|---|
| 6 1 5 3 2 1 50 -1 0 0 1 1 -1 | 95 |
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.
