Fişierul intrare/ieşire:bursa.in, bursa.outSursăInfoarena Monthly 2012, Runda 1
AutorCiprian MargineanAdăugată decezar305Mr. Noname cezar305
Timp execuţie pe test0.05 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bursa

Gigi are un pont la bursa. El stie pentru fiecare din urmatoarele N zile care va fi pretul P[i] al unei actiuni la compania X. Stiind ca a reusit sa stranga suma de bani S (de pe la rude si prieteni), afisati profitul maxim pe care il poate obtine Gigi. Presupuneti ca Gigi poate cumpara in fiecare zi oricate actiuni doreste, cu conditia sa ii ajunga banii pe care ii are. De asemenea, puteti presupune ca Gigi poate vinde in orice zi, oricate actiuni doreste, dintre cele pe care le detine. Transferul de bani / actiuni se realizeaza instantaneu.

Date de intrare

Fişierul de intrare bursa.in contine pe prima linie numarul de zile, N, si suma de bani detinuta de Gigi, S. Pe cea de-a doua linie, cel de-al i-lea numar reprezinta pretul de vanzare / cumparare al unei actiuni in ziua i.

Date de ieşire

Fişierul de ieşire bursa.out va contine pe prima linie profitul maxim pe care il poate obtine Gigi.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ S ≤ 10 000 000 000
  • 1 ≤ P[i] ≤ 500 000
  • Se garanteaza ca suma de bani detinuta de Gigi se va incadra pe un intreg cu 64 de biti, la orice moment de timp

Exemplu

bursa.inbursa.out
3 100
7 1 12
1100

Explicaţie

N = 3, S = 100. Actiunile vor costa 7 lei fiecare in prima zi, 1 leu in a doua si 12 lei in a treia zi. Pentru a obtine profit maxim, Gigi trebuie sa cumpere in a doua zi 100 de actiuni si sa le vanda in a treia zi pe toate, obtinand astfel un profit de 1100 lei.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content