== include(page="template/taskheader" task_id="kds") ==
Se consideră un șir de numere naturale a[~1~],a[~2~],…,a[~n~] așezate circular. Acest lucru înseamnă că a[~1~] are ca vecini numerele a[~n~] și a[~2~], iar an are ca vecini pe a[~n-1~] și a[~1~]. Se consideră de asemenea un număr natural **K**.
Se consideră un șir de numere naturale $a[~1~],a[~2~],…,a[~n~]$ așezate circular. Acest lucru înseamnă că $a[~1~]$ are ca vecini numerele $a[~n~]$ și $a[~2~]$, iar an are ca vecini pe $a[~n-1~]$ și $a[~1~]$. Se consideră de asemenea un număr natural [$K$].
h2. Cerință
Să se determine suma maximă care se poate obține din exact **K** secvențe nevide, disjuncte și ne-vecine.
Să se determine suma maximă care se poate obține din exact $K$ secvențe nevide, disjuncte și ne-vecine.
h2. 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 a[~1~],a[~2~],...,a[~n~].
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 $a[~1~],a[~2~],...,a[~n~]$.
h2. 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.
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.
h2. Restricții
* 2 ≤ 2*K ≤ n ≤ 10 000
* 1 ≤ a[~i~] ≤ 10 000, i=1..n
* 2 ≤ $2*K$ ≤ $n$ ≤ 10 000
* 1 ≤ $a[~i~]$ ≤ 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.
table(example).
|_. kds.in |_. kds.out |_. Explicații |
| 7 2
3 7 2 1 2 4 5
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).
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).
|
== include(page="template/taskfooter" task_id="kds") ==
