Fişierul intrare/ieşire:cover.in, cover.outSursăBaraj ONI 2007
AutorAdrian VladuAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.incover.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

  1. 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.
  2. Se construieste acoperirea {1, 4, 7} care are costul 5.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content