Fişierul intrare/ieşire:perle2.in, perle2.outSursăAlgoritmiada 2010, Runda 1
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Perle2

Laura a primit un colier cu N perle. Ea a reprezentat într-un vector A de numere întregi cât de mult îi place fiecare perlă din colier. Mai exact, valoarea de pe poziţia i din vector ne spune cât de mult îi place Laurei cea de a i-a perlă. Ea şi-ar dori să păstreze o subsecvenţă de perle din colier care să-i placă cât mai mult, dar este conştientă că şi lungima subsecvenţei alese afectează frumuseţea colierului cu un factor K cunoscut. De aceea, fata vă roagă să găsiţi o subsecvenţă [i, j] care maximizează valoarea (Ai + Ai+1 + ... + Aj) - K*(j-i+1).

Cerinta

Determinaţi valoarea maximă posibilă a unei subsecvenţe din şirul dat. Pe următoarele N linii se găseşte câte un număr întreg din vectorul A.

Date de intrare

Fişierul de intrare perle2.in conţine pe prima linie două numere întregi N şi K. Pe următoarele N linii se află câte un număr întreg reprezentând câte un element din vectorul A.

Date de ieşire

În fişierul de ieşire perle2.out conţine un singur număr întreg ce corespunde valorii cerute.

Restricţii

  • 1 ≤ N ≤ 100 000
  • -10 000 ≤ K ≤ 10 000
  • -10 000 ≤ Ai ≤ 10 000
  • Dacă valoarea maximă posibilă este negativă, atunci Laura va prefera sa nu aleagă nici o perlă.
  • Pentru 30% din teste, N ≤ 1 000.

Exemplu

perle2.inperle2.out
6 3
2
6
7
1
4
-5
7

Explicaţie

Subsecvenţa de valoare maximă este [2, 3].

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content