4.5

Idee de rezolvare:
	Parcurgem cele n-1 căsuțe și sunt 2 cazuri:
		1. Întâlnim un dragon, astfel că adăugăm într-un heap perechea formată din -1 * numărul de monezi din comoară și poziția dragonului. Pentru a obține soluția cea mai bună, avem nevoie de valorile cele mai mari, deci vom folosi un heap pe care îl adaptăm pentru max_heap, punând valorile cu minus (astfel, minimul extras din heap va fi de fapt maximul de care avem nevoie).
		2. Întâlnim o prințesă și se disting încă 2 cazuri:
			i. Prințesa nu este ultima, astfel că trebuie să fim atenți câți dragoni eliminăm pentru a nu ne opri acolo. Dar știm că putem elimina maxim (bi) - 1 dragoni, adică (bi) - câți dragoni am eliminat anterior - 1 = t. Extragem așadar din heap primele t perechi și le adăugăm la soluție, având grijă să adăugăm la sumă -monezi (deoarece în heap le-am adăugat cu minus). În continuare trebuie să eliminăm din heap perechile care rămân, dacă există, deoarece nu mai avem ce face cu ele.
			ii. Prințesa este ultima (suntem pe poziția n), deci putem elimina toți dragonii rămași în heap și colecta monezile. Dacă numărul de dragoni uciși este mai mare sau egal decât (bn) (frumusețea ei) și prințesa consideră cavalerul „neînfricat”, afișăm soluția obținută; în caz contrar, afișăm -1.

Pseudocod:
	citim n - numărul de căsuțe
	citim cele n-1 căsuțe și reținem datele într-o listă de tupluri
	inițializăm counter (căsuța la care ne aflăm), sum (câte monede s-au adunat),
dragons (câți dragoni am eliminat), heap-ul și lista sol în care se vor găsi locațiile dragonilor
	pentru fiecare căsuță:
		incrementăm counter-ul
		dacă întâlnim un dragon:
			adăugăm în heap un tuplu format din -numărul de monede din comoară și poziția dragonului
		altfel: (dacă întâlnim o prințesă)
			dacă nu am ajuns la ultima:
				calculăm în allowed câți dragoni putem elimina
				cât timp avem voie să omorâm dragoni:
					incrementăm dragons
					reținem în pop tuplul cel mai convenabil extras din heap
					adăugăm la sum -numărul de monezi
					decrementăm allowed
					adăugăm la sol poziția dragonului
				eliminăm tuplurile rămase în heap
			altfel: (am ajuns la ultima prințesă)
				eliminăm toți dragonii din heap și adăugăm la soluție
				dacă dragons este mai mare decât „frumusețea” ultimei prințese:
					afișăm sum
					afișăm dragons
					afișăm sol
				altfel:
					afișăm -1

Implementare Python: https://pastebin.com/eX7afWEj

Exemplu: https://pastebin.com/tckV77C0