Fişierul intrare/ieşire:calancea.in, calancea.outSursăLot Deva 2013 - Baraj 1 Seniori
AutorAndrei GrigoreanAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.incalancea.out
3 6
10 5 1
5

Explicaţie

Cu excepţia subsevenţei (1, 3), toate subsecvenţele respectă proprietatea cerută.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content