Fișierul intrare/ieșire kds.in, kds.out Sursă Lot II Juniori 2016
Autor Ionel-Vasile Piț-Rada | Mihail-Cosmin Piț-Rada Adăugată de avatar Tiberiu02 Tiberiu Musat Tiberiu02
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in kds.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii