rompetrol

Rompetrol

== include(page="template/taskheader" task_id="rompetrol") ==

La ONI 2006, firma Petrom a avut nevoie de ajutorul dumneavoastra pentru a amenaja $K$ depozite de combustibil in $K$ dintre cele $N$ benzinarii amplasate de-a lungul autostrazii Soarelui, in asa fel incat suma distantelor de la fiecare benzinarie la depozitul cel mai apropiat sa fie minima. Un an (si ceva) mai tarziu, principalul concurent, Rompetrol, s-a extins si are de rezolvat o problema similara, dar la o scara mai mare. Rompetrol are $N$ benzinarii amplasate de-a lungul autostrazii Soarelui. Pozitiile benzinariilor sunt cunoscute, fiind specificate prin distantele $d{~1~}, d{~2~}, ... , d{~N~}$ ( $d{~i~}$ reprezinta distanta de la sediul firmei Rompetrol pana la benzinaria $i$). Sediul firmei Rompetrol este amplasat la intrarea pe autostrada Soarelui (chiar langa cel al firmei Petrom). De asemenea, pentru fiecare benzinarie se cunoaste cantitatea de combustibil $c{~i~}$ necesara pentru a satisface cerintele clientilor ce utilizeaza benizaria respectiva. In $K$ dintre aceste benzinarii firma doreste sa amenajeze depozite de combustibil, care sa alimenteze benzinaria respectiva, precum si, posibil, alte benzinarii invecinate. Fiecare benzinarie va fi alimentata de la depozitul cel mai apropiat. Pentru fiecare benzinarie se cunoaste costul ai ce trebuie platit pentru amenajarea unui depozit de combustibil in cadrul benzinariei. Costul de transport al benzinei de la un depozit $X$ la o benzinarie $Y$ este egal cu produsul dintre cantitatea de combustibil necesara la benzinaria $Y$ si distanta dintre $X$ si $Y$. Costul de transport pentru o amplasare a depozitelor data va fi egal cu suma costurilor de transport ale tuturor benzinariilor. Costul total este egal cu suma dintre costul total de transport si costurile de amenajare ale depozitelor in $K$ dintre benzinarii.

Firma Rompetrol are $N$ benzinarii amplasate de-a lungul autostrazii Soarelui. Pozitiile benzinariilor sunt cunoscute, fiind specificate prin distantele $d{~1~}, d{~2~}, ... , d{~N~}$ ( $d{~i~}$ reprezinta distanta de la sediul firmei Rompetrol pana la benzinaria $i$). Sediul firmei Rompetrol este amplasat la intrarea pe autostrada Soarelui. De asemenea, pentru fiecare benzinarie se cunoaste cantitatea de combustibil $c{~i~}$ necesara pentru a satisface cerintele clientilor ce utilizeaza benzinaria respectiva. In $K$ dintre aceste benzinarii firma doreste sa amenajeze depozite de combustibil, care sa alimenteze benzinaria respectiva, precum si, posibil, alte benzinarii invecinate. Fiecare benzinarie va fi alimentata de la depozitul cel mai apropiat. Pentru fiecare benzinarie se cunoaste costul $a{~i~}$ ce trebuie platit pentru amenajarea unui depozit de combustibil in cadrul benzinariei. Costul de transport al benzinei de la un depozit $X$ la o benzinarie $Y$ este egal cu produsul dintre cantitatea de combustibil necesara la benzinaria $Y$ si distanta dintre $X$ si $Y$. Costul de transport pentru o amplasare a depozitelor data va fi egal cu suma costurilor de transport ale tuturor benzinariilor. Costul total este egal cu suma dintre costul total de transport si costurile de amenajare ale depozitelor in $K$ dintre benzinarii.

h2. Cerinta

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ N$

* $1 ≤ N*K ≤ 10 000 000$

* $1 ≤ N*K ≤ 5 000 000$

* $1 ≤ d{~1~} < d{~2~} < ... < d{~N~} ≤ 10 000 000$
* $1 ≤ c{~i~} ≤ 1000$
* $0 ≤ a{~i~} ≤ 1 000 000 000$

* 40% din teste vor avea $N ≤ 500$ si $K ≤ 300$

* Cel putin 40% din teste vor avea $N ≤ 500$ si $K ≤ 300$

h2. Exemplu

h3. Explicatie

Depozitul 1 va fi construit in benzinaria 2 si alimenteaza benzinariile 1, 2, 3. (Cost: 1*1+0*1+6*1=7)
Depozitul 2 va fi construit in benzinaria 4 si alimenteaza benzinariile 4, 5. (Cost: 0*1+1*1=1)
Depozitul 3 va fi construit in benzinaria 6 si alimenteaza benzinaria 6. (Cost: 0*1).
Costul total de transport este 7+1+0. Costul amplasarii celor 3 benzinarii este 0+0+0=0. Costul total este 8+0=8.

Depozitul 1 va fi construit in benzinaria 2 si alimenteaza benzinariile 1, 2, 3. (Cost: $1*1+0*1+6*1=7$)
Depozitul 2 va fi construit in benzinaria 4 si alimenteaza benzinariile 4, 5. (Cost: $0*1+1*1=1$)
Depozitul 3 va fi construit in benzinaria 6 si alimenteaza benzinaria 6. (Cost: $0*1$).
Costul total de transport este $7+1+0$. Costul amplasarii celor 3 benzinarii este $0+0+0=0$. Costul total este $8+0=8$.

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

2128