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 | 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 |
Vezi soluțiile trimise | Statistici
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*K ≤ n ≤ 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). |