Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | calancea.in, calancea.out | Sursă | Lot Deva 2013 - Baraj 1 Seniori |
| Autor | Andrei Grigorean | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Calancea
Miruna a ajuns în faţa unei noi provocări: în cetatea Devei a găsit N calănci aşezate în linie, fiecare calance avînd o anumită înălţime exprimată în centimetri. Înălţimea unei calănci poate fi crescută cu 1 centimetru, însă această operaţie o costă exact 1 leu. Operaţia de creştere poate fi aplicată aceleiaşi calănci de oricîte ori. Avînd un buget de B lei la dispoziţie, Miruna se întreabă cîte subsecvenţe ale şirului de calănci pot fi transformate astfel încît să devină monoton crescătoare.
Date de intrare
Pe prima line a fisierului calancea.in se vor afla numerele N şi B, cu semnificaţia din enunţ. Următoarele N linii vor conţine câte un şir de lungime N valori reprezentând înălţimile calăncilor.
Date de ieşire
În fişierul calancea.out se vor afişa un singur număr întreg reprezentând numărul de subsecvenţe care pot fi transformate în şiruri monoton crescătoare avînd la dispoziţie bugetul B.
Restricţii
- 1 ≤ N ≤ 1.000.000
- 1 ≤ B ≤ 10^15
- Înălţimile iniţiale ale calăncilor vor fi din intervalul [0, 10^9]
Exemplu
| calancea.in | calancea.out |
|---|---|
| 3 6 10 5 1 | 5 |
Explicaţie
Cu excepţia subsevenţei (1, 3), toate subsecvenţele respectă proprietatea cerută.
