Revizia anterioară Revizia următoare
| 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
...
Restrictii
- ... ≤ ... ≤ ...
Exemplu
| cover.in | cover.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
