| Fişierul intrare/ieşire: | picazo.in, picazo.out | Sursă | Summer Challenge 2019 |
| Autor | Alexandru Luchianov | Adăugată de |  Alex Luchianov •AlexandruLuchianov1 |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Picazo
Picazo, un artist mandru de arta sa, insa mai mandru de baut lapte cald si-a dat seama ca a ramas fara bani asa ca este nevoit sa se intoarca la pasiunea sa secundara. La inceput, are numai un tablou complet alb compus din N celule 1 * 1 dispuse adiacent. Pentru K bani el isi poate cumpara o canistra de vopsea cu care poate picta una din celulele tabloului complet. Clientul sau il va plati in functie de frumusetea tabloului. Frumusetea tabloului este determinata de suma frumusetilor a Q intervale alese de client. Frumusetea unui interval este determinata de numarul de culori distincte prezente in acel interval, inclusiv albul initial.
Date de intrare
Fişierul de intrare picazo.in va contine pe prima linie numerele N, K si Q cu semnificatiile din enunt.
Urmeaza pe fiecare din urmatoarele Q randuri cate 2 numere care reprezinta capatele intervalelor alese de client.
Date de ieşire
Fişierul de ieşire picazo.out va avea pe prima linie profitul maxim obtinut de Picazo in urma vanzarii tabloului.
Restricţii
- Exista cel putin 100.000 de culori distincte.
- 1 ≤ N, K, Q ≤ 100.000
- Pentru 20 de puncte, N, Q ≤ 20
- Pentru alte 40 de puncte, N, Q ≤ 2.000
- Pentru restul de 40 de puncte, N, Q ≤ 100.000
Exemplu
| picazo.in | picazo.out |
|---|---|
| 5 1 6 1 2 2 3 2 3 3 4 3 4 4 5 | 10 |
| 5 1 3 1 5 1 5 1 5 | 11 |
Explicaţie
In primul exemplu vom colora celulele 2 si 4 cu albastru respectiv rosu. Costul de colorare va fi 2, iar bani primiti pe tablou vor fi 2 + 2 + 2 + 2 + 2 + 2 = 12 => Profitul total este 12 - 2 = 10
In al doilea exemplu vom colora toate celulele, astfel vom avea profitul 5 + 5 + 5 - 4 = 11
