Fişierul intrare/ieşire:purification.in, purification.outSursăLot Măgurele 2016 - Baraj 4 Seniori
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test1 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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 Wi 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 Wi, semnificând numărul de zerglingi produşi de cuibul i într-o oră. Pe linia următoare se vor afla alte N numere Fi, 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 ≤ Wi ≤ 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.inpurification.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?