== include(page="template/taskheader" task_id="kds") ==
Poveste și cerință...
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.
h2. Date de intrare
Fișierul de intrare $kds.in$ ...
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
În fișierul de ieșire $kds.out$ ...
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
* 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.
h2. Exemplu
table(example).
|_. kds.in |_. kds.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. 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).
|
== include(page="template/taskfooter" task_id="kds") ==
