Fişierul intrare/ieşire:metrou.in, metrou.outSursăInfoarena Monthly 2012, Runda 10
AutorTeodor PlopAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.4 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.inmetrou.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content