Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | placute.in, placute.out | Sursă | Infoarena Monthly 2012, Runda 11 |
| Autor | Mihai-Alexandru Dusmanu, Teodor Plop | Adăugată de |  Teodor Plop •Teodor94 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Placute
Se dau N placute colorate in K culori diferite. Pe fiecare placuta i din cele N este scris un numar natural a[i].
Trebuie sa aranjati cele N placute una langa cealalta, in linie, astfel incat sa nu existe doua placute vecine avand aceeasi culoare, iar numerele de pe acestea sa fie in ordine descrescatoare.
Sa se calculeze suma maxima care se poate obtine adunand numerele de pe placute in urma unei astfel de aranjari.
Date de intrare
În fişierul de intrare placute.in se vor gasi pe prima linie numerele naturale N si K. Pe urmatoarele N linii se vor gasi cate 2 numere naturale a[i] si c[i], reprezentand numarul inscriptionat si culoarea placutei i.
Date de ieşire
În fişierul de ieşire placute.out se va gasi un singur numar natural, reprezentand suma maxima obtinuta.
Restricţii
- 1 ≤ N ≤ 100000
- 1 ≤ K ≤ 1000
- 1 ≤ a[i] ≤ 1000
- 1 ≤ c[i] ≤ K
Exemplu
| placute.in | placute.out |
|---|---|
| 6 3 5 1 4 1 1 3 2 2 5 2 3 2 | 20 |
Explicaţie
...
