Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-04-21 08:43:06.
Revizia anterioară   Revizia următoare  

 

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$.

Exemplu

cover.incover.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content