inundatii

Inundatii

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

Poveste si cerinta...

Anul acesta este foarte posibil ca in orasul lui Zaharel sa aiba loc inundatii. Zaharel trebuie sa se gandeasca la un plan prin care sa protejeze cele $N$ cladiri din orasul sau de inundatii. Pentru a simplifica problema vom considera o cladire ca fiind un punct in spatiu. In plus, cladirile din orasul lui Zaharel au niste proprietati interesante:
 
* sunt numerotate cu numere distincte intre $1$ si $N$
* coordonatele sunt numere intregi
* cladirea cu numarul $i$ *domina* cladirea cu numarul $i+1$ pentru orice $1 &le; i < N$; formal, asta inseamna ca $X{~i~} > X{~i+1~}$, $Y{~i~} > Y{~i+1~}$ si $Z{~i~} > Z{~i+1~}$, unde $(X{~i~}, Y{~i~}, Z{~i~})$ reprezinta pozitia cladirii cu numarul $i$
 
Dupa o lunga analiza, Zaharel a ajuns la concluzia ca cel mai sigur mod de a evita inundatiile este mutarea cladirilor astfel incat cladirea $i$ sa domine cladirea $i-1$ pentru orice $1 < i &le; N$. Desigur, mutarea unei cladiri nu este o treaba usoara, asa ca Zaharel vrea sa minimize suma distantelor cu care se muta fiecare cladire.

h2. Date de intrare

Fisierul de intrare $inundatii.in$ ...

Fisierul de intrare $inundatii.in$ contine pe prima linie numarul $N$, iar pe urmatoarele $N$ linii cate $3$ numere intregi $X{~i~} Y{~i~} Z{~i~}$ separate prin spatii, reprezentand pozitiile cladirilor.

h2. Date de iesire

In fisierul de iesire $inundatii.out$ ...

In fisierul de iesire $inundatii.out$ se va scrie un singur numar natural, reprezentand suma distantelor cu care se muta fiecare cladire, in cazul cel mai favorabil.

h2. Restrictii
* $1 ≤ N ≤ 50.000$

* $0 ≤ X{~i~}, Y{~i~}, Z{~i~} ≤ 10^8^$
* Coordonatele la care se muta casele trebuie sa fie numere intregi
* Se considera ca distanta dintre doua puncte $(x{~1~},y{~1~},z{~1~})$ si $(x{~2~},y{~2~},z{~2~})$ este $|x{~1~}-x{~2~}|+|y{~1~}-y{~2~}|+|z{~1~}-z{~2~}|$

h2. Exemplu

| 2
8 5 10
5 4 7

| 10 |

| 10 |

h3. Explicatie
O solutie posibila este:

$(6,4,8)$
$(7,5,9)$

Se muta prima cladire de la $(8,5,10)$ la $(6,4,8)$, distanta fiind de $|8-6|+|5-4|+|10-8|=2+1+2=5$.
Se muta a doua cladire de la $(5,4,7)$ la $(7,5,9)$, distanta fiind de $|5-7|+|4-5|+|7-9|=2+1+1=5$.
Suma distantelor este $10$, iar solutia este valida deoarece a doua cladire domina prima cladire ({$7 > 6$}, $5 > 4$, $9 > 8$).

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

2603