Fişierul intrare/ieşire:sao.in, sao.outSursăAlgoritmiada 2015 Runda Finala
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Sword Art Online

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

Exemplu

sao.insao.out
10 2 10
-3 2 3 -2 8 8 6 4 3 3
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?