Fişierul intrare/ieşire:panza.in, panza.outSursăAlgoritmiada 2019 Runda PreOJI
AutorAlexandru PetrescuAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.4 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Panza

Se considera o panza de paianjen. Pentru ca e vorba de paianjenul lui Marcel, panza este intr-atat de bine organizata ca este supusa unei simetrii exceptionale: N segmente (numerotate de la 1 la N) pleaca din centrul panzei spre exterior, formand intre ele unghiuri egale. Intre fiecare 2 segmente consecutive se afla M punti curbe de lungimi A1 A2 ... AM, in asa fel incat puntea Ai sa uneasca punctele de pe cele doua segmente aflate la distanta i de centru.

Cerinta

Pe fiecare segment i de la 1 la N se afla bobite cu vitamina i, de la punctul aflat la distanta Xi de centru la cel aflat la distanta Yi. Paianjenul porneste la punctul aflat la distanta S de centru de pe segmentul 1, culege succesiv (in exact aceasta ordine) macar un bob cu vitamina 1, apoi 2, apoi 3, ..., iar la final N, ca la final sa ajunga la punctul aflat la distanta F de centru de pe segmentul N. Astfel, el se poate plimba alternativ pe segment si pe punti. Care e distanta minima pe care o parcurge paianjenul?

Date de intrare

Fişierul de intrare panza.in contine, pe prima linie, numerele naturale N, M, S si F. Pe urmatoarea linie sunt M numere naturale Ai. Pe urmatoarele N linii sunt cate doua numere naturale Xi si Yi.

Date de ieşire

În fişierul de ieşire panza.out se afla distanta minima parcursa de paianjen.

Restricţii

  • 1 ≤ S, F ≤ M
  • 1 ≤ N, M ≤ 100.000
  • 1 ≤ Ai ≤ 1.000.000
  • 1 ≤ N * M ≤ 1.000.000
  • 1 ≤ Xi ≤ Yi ≤ M
  • Pentru 30 de puncte, 1 ≤ N, M ≤ 50
  • Pentru alte 40 de puncte, 1 ≤ N, M ≤ 300
  • Paianjenul nu poate trece prin centrul panzei sale pentru ca daca ajunge acolo, intr-un loc asa de odihnitor si plin de armonie, nu se va mai putea mobiliza sa plece pentru a se hrani
  • Veţi primi rezultatele evaluării doar pe fişierul de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.

Exemplu

panza.inpanza.out
4 5 2 3
1 2 3 4 5
1 2
2 3
1 4
4 5
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?