Fişierul intrare/ieşire:secvbest.in, secvbest.outSursăInfoarena Cup 2013
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.4 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Secvbest

Se dau 3 numere naturale N, K, S si un sir de N numere naturale. Acesta trebuie impartit in maxim K subsecvente astfel incat suma costurilor subsecventelor sa fie minima. Costul unei subsecvente este diferenta in modul dintre S si suma elementelor subsecventei.

Date de intrare

Fişierul de intrare secvbest.in va contine pe prima linie 3 numere naturale N, K si S. Pe linia a doua vor fi N numere naturale reprezentand sirul dat.

Date de ieşire

Fişierul de ieşire secvbest.out va contine K valori separate printr-un spatiu. Valoarea i reprezinta costul minim daca sirul trebuie impartit in fix i subsecvente.

Restricţii

  • 1 ≤ K ≤ N ≤ 100.000
  • 1 ≤ K ≤ 30
  • valorile sirului si S vor fi cuprinse in intervalul [1, 1.000.000.000]

Exemplu

secvbest.insecvbest.out
5 3 10
5 5 2 9 8
19 9 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?