cover

Cover

h2. 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 $c{~1~} c{~2~} ... c{~L~}$ 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.

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

h2. Restrictii

h2. Restrictii si precizari

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 60 000$
* $1 ≤ L ≤ 1 000 000$
* $0 ≤ c{~i~} ≤ 1024$, pentru orice $1 ≤ i ≤ L$
* Pentru @40%@ din teste $N ≤ 1 000$ si $L ≤ 10 000$

h2. Exemplu

 
h2. Exemple

table(example). |_. cover.in |_. cover.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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

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

== include(page="template/taskfooter" task_id="cover") ==

== SmfTopic(topic_id="...") ==

1847