| Fişierul intrare/ieşire: | cover.in, cover.out | Sursă | Baraj ONI 2007 |
| Autor | Adrian Vladu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cover
Se considera N intervale inchise, avand extremitatile numere naturale cuprinse intre 1 si L. Fiecare numar natural i din intervalul [1, L] are asociata o pondere ci.
Numim acoperire o multime de numere naturale cuprinse intre 1 si L cu proprietatea ca fiecare interval contine cel putin un element al multimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Pentru un set de intervale dat sa se determine costul minim al unei acoperiri.
Date de intrare
Fisierul de intrare cover.in contine pe prima linie cele doua numere naturale N L separate printr-un spatiu. Pe urmatoarea linie se afla L numere naturale separate prin cate un spatiu c1 c2 ... cL reprezentand ponderile numerelor naturale din intervalul [1, L]. Urmatoarele N linii contin fiecare cate doua numere naturale a b (1 ≤ a ≤ b ≤ L) reprezentand extremitatile intervalelor.
Date de iesire
Fisierul de iesire cover.out va contine o singura linie pe care va fi scris un numar natural reprezentand costul minim al unei acoperiri.
Restrictii si precizari
- 1 ≤ N ≤ 60 000
- 1 ≤ L ≤ 1 000 000
- 0 ≤ ci ≤ 1024, pentru orice 1 ≤ i ≤ L
- Pentru
40%din teste N ≤ 1 000 si L ≤ 10 000
Exemple
| cover.in | cover.out |
|---|---|
| 2 5 100 5 9 6 90 1 3 3 5 | 9 |
| 4 10 1 3 6 4 5 1 0 1 3 2 1 3 3 5 6 9 4 4 | 5 |
Explicatie
- Se construieste acoperirea {3} care are costul 9. Elementul 3 apartine ambelor intervale date in fisierul de intrare.
Exista si alte acoperiri posibile de exemplu {2, 4} dar costul acesteia este 11 care nu este minim. - Se construieste acoperirea {1, 4, 7} care are costul 5.
