Fişierul intrare/ieşire:kds.in, kds.outSursăLot II Juniori 2016
AutorIonel-Vasile Pit-Rada, Mihail Cosmin Pit-RadaAdăugată deTiberiu028A Tiberiu Musat Tiberiu02
Timp execuţie pe test0.5 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Kds (Lot Juniori)

Se consideră un şir de numere naturale a1,a2,…,an aşezate circular. Acest lucru înseamnă că a1 are ca vecini numerele an şi a2, iar an are ca vecini pe an-1 şi a1. Se consideră de asemenea un număr natural K.

Cerinţă

Să se determine suma maximă care se poate obţine din exact K secvenţe nevide, disjuncte şi ne-vecine.

Date de intrare

Fişierul kds.in conţine pe prima linie numerele naturale n şi K, iar pe linia a doua, separate prin câte un spaţiu, numerele a1,a2,...,an.

Date de ieşire

Fişierul kds.out conţine un singur număr natural reprezentând suma maximă care se poate obţine din K secvenţe nevide, disjuncte şi ne-vecine.

Restricţii

  • 2 ≤ 2*Kn ≤ 10 000
  • 1 ≤ ai ≤ 10 000, i=1..n
  • Două secvenţe sunt disjuncte dacă nu au niciun element comun.
  • Două secvenţe sunt ne-vecine dacă sunt separate prin cel puţin un element care nu aparţine nici uneia din cele două secvenţe.

Exemplu

kds.inkds.outExplicaţii
7 2
3 7 2 1 2 4 5
20
Cele două secvenţe sunt 1 şi 4 5 3 7
Atenţie, nu se pot alege secvenţele 3 7 2 şi 2 4 5 pentru că ele sunt vecine (5 este vecin cu 3).
Trebuie sa te autentifici pentru a trimite solutii. Click aici