Sword Art Online SAO

by

Dupa ce a intrat in noul joc: Sword Art Online, Kirito s-a decis sa isi masoare puterile in ultimul quest aparut. Initial, Kirito are un HP (viata) si K potiuni magice. El are de infruntat N monstrii foarte puternici. Din moment ce acesti monstrii sunt bossi la fiecare nivel din joc, Kirito este obligat sa se lupte cu cei N inamici in ordinea aparitiei lor (monstrul 1, monstrul 2, etc.). Pentru fiecare monstru Kirito stie cat HP pierde pentru a il omora. In lupta cu monstrul i pierde damagei HP. Kirito poate la un anumit moment sa foloseasca una din cele K potiuni pentru a distruge un monstru fara sa piarda viata. Ajutati-l pe Kirito sa aleaga pe ce monstrii sa foloseasca cele K potiuni pentru a reusi sa omoare cat mai multi dintre inamicii sai (daca Kirito se bate cu un monstru si il bate numai daca are cel putin ataga HP cat si-ar lua damage de la un monstru. Atunci cand ajunge cu HP-ul 0 sau mai putin atunci automat moare si nu mai poate continua).

Date de intrare

Fişierul de intrare sao.in va contine pe prima linie 3 numere naturale N, K si HP. Pe linia 2 vor fi N elemente, elementul i reprezentand valoarea damagei

Date de ieşire

Fişierul de ieşire sao.out va contine un singul numar natural reprezentand numarul maxim de monstrii pe care poate Kirito sa ii omoare

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ HP ≤ 1.000.000.000
  • 1 ≤ |damagei| ≤ 1.000.000.000
  • 1 ≤ K ≤ N
  • Daca un monstru are damage negativ inseamna ca jucatorul castiga hp luptandu-se cu el, insa daca jucatorul are deja 0 sau mai putin atunci nu se va putea bate oricum cu acel monstru.
  • Pentru 50% din punctaj 1 ≤ damagei

sao.in

10 2 10
-3 2 3 -2 8 8 6 4 3 3

sao.out

8

using namespace std;

ifstream f(“sao.in”);
ofstream g(“sao.out”);

long long n, k, hp, i, d, nr;
priority_queue damage;

int main()
{
f >> n >> k >> hp;
for (i = 1; i <= n; i++) { f >> d;
hp -= d;
damage.push(d);
if (hp > 0) {
nr++;
}
else if (hp == 0) {
nr++;
if (k > 0) {
hp += damage.top();
k–;
damage.pop();
}
else {
i = n + 1;
}
}
else {
if (k > 0) {
hp += damage.top();
k–;
damage.pop();
nr++;
}
else {
i = n + 1;
}
}
}
g << nr;
f.close();
g.close();
return 0;
}