Fişierul intrare/ieşire:picazo.in, picazo.outSursăSummer Challenge 2019
AutorAlexandru LuchianovAdăugată deAlexandruLuchianov1Alex Luchianov AlexandruLuchianov1
Timp execuţie pe test1 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.
  • 1N, K, Q100.000
  • Pentru 20 de puncte, N, Q20
  • Pentru alte 40 de puncte, N, Q2.000
  • Pentru restul de 40 de puncte, N, Q100.000

Exemplu

picazo.inpicazo.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?