| Fişierul intrare/ieşire: | metrou.in, metrou.out | Sursă | Infoarena Monthly 2012, Runda 10 |
| Autor | Teodor Plop | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Metrou
Traim intr-o lume ciudata, in care statiile de metrou sunt si mai ciudate. Iar pe cat de ciudat, pe atat de aglomerat. Fiind multa imbulzeala, avem nevoie de ajutorul vostru pentru a face ordine prin multime.
Un metrou are N usi. In momentul in care ajunge metroul in statie, stim ca la fiecare usa i, plasata in pozitia x[i] a axei Ox (1 ≤ i ≤ N) sunt a[i] oameni care doresc sa intre in metrou si b[i] oameni care doresc sa iasa din metrou. Singura problema este ca, din cauza noilor reguli, printr-o usa se poate fie intra, fie iesi, una dintre aceste actiuni fiind intotdeauna interzisa. Niciunul dintre oamenii care fie vor sa intre in metrou, fie vor sa iasa nu stiu daca usa la care sunt amplasati este de deschidere sau de inchidere. Asa ca, de exemplum daca usa i din pozitia x[i] (1 ≤ i ≤ N) este de intrare, cei b[i] oameni amplasati la aceasta usa vor fi nevoiti sa se mute la cea mai apropiata usa de iesire pentru a cobori la aceasta statie. Se mai stie ca efortul unui om de a se deplasa de la usa i la usa j este |x[i] - x[j]| (1 ≤ i, j ≤ N).
Avand la dispozitie numarul N de usi, pozitia acestora pe axa Ox si numarul de oameni care doresc sa intre si sa iasa din metrou la fiecare usa in parte, sa se determine efortul minim depus de oameni pentru deplasare in urma intrarii si iesirii din metrou.
Date de intrare
In fisierul de intrare metrou.in se va afla pe prima linie numarul natural N, reprezentand numarul de usi ale metroului. Pe cea de-a doua linie se vor gasi valorile sirului x, unde x[i] reprezinta pozitia usii i. Pe liniile 3 si 4 se vor gasi valorile sirurilor a, respectiv b, reprezentand numarul de oameni care doresc sa intre, respectiv numarul de oameni care doresc sa iasa din metrou pe usile acestuia.
Date de ieşire
In fisierul de iesire metrou.out se va afla pe prima si singura linie un singur numar natural reprezentand efortul minim depus de oameni pentru a-si indeplini scopul (intra/iesi din metrou).
Restricţii
- 2 ≤ N ≤ 2000
- 0 ≤ x[i] ≤ 100.000
- 1 ≤ a[i], b[i] ≤ 1000
- Elementele sirului x sunt in ordine crescatoare.
- Se garanteaza ca raspunsul intra in 32 de biti cu semn.
Exemplu
| metrou.in | metrou.out |
|---|---|
| 4 1 3 4 5 1 2 3 5 2 3 3 1 | 9 |
Explicaţie
Prima si a treia usa for fi de iesire, iar a doua si a patra usa de intrare.
Efortul depus de oamenii care vor sa intre este 1*2 + 2*0 + 3*1 + 5*0 = 5
Efortul depus de oamenii care vor sa iasa este 2*0 + 3*1 + 3*0 + 1*1 = 4
Efortul total este 4 + 5 = 9
