Fişierul intrare/ieşire:heavymetal.in, heavymetal.outSursăpreONI 2008, Runda 4
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Heavy metal

Miruna a intrat de curand in afacerea cu muzica buna. Ea s-a decis sa organizeze un festival de heavy metal si a cumparat o sala de concerte. La festival a invitat N formatii, insa fiecare formatie poate sa cante un anumit interval fixat de timp. Deoarece fanii sunt scandalagii, Miruna doreste sa selectioneze formatiile ce vor canta astfel incat timpul total in care cineva concerteaza sa fie cat mai mare. In alegerea formatiilor trebuie sa aiba grija sa nu existe 2 formatii care sa concerteze in acelasi timp.

Date de intrare

Prima linie a fisierului de intrare heavymetal.in contine un numar natural N, avand semnificatia din enunt. Urmeaza N linii pe care se vor gasi cate doua valori Ai si Bi, reprezentand intervalele de timp in care pot canta formatiile.

Date de iesire

In fisierul de iesire heavymetal.out se va gasi un singur numar reprezentand suma maxima a intervalelor de timp in care vor canta formatiile.

Restrictii

  • 1 ≤ N ≤ 100000
  • 1 ≤ Ai, Bi ≤ 109
  • Ai < Bi
  • Pentru 40% din teste 1 ≤ N, Ai, Bi ≤ 1000

Exemplu

heavymetal.inheavymetal.out
4
3 5
5 10
3 4
1 2
8

Explicatie

Vor canta formatiile 1, 2 si 4, iar timpul total va fi 2 + 5 + 1 = 8.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content