Nu aveti permisiuni pentru a descarca fisierul grader_test7.in

 

Fişierul intrare/ieşire:climbers.in, climbers.outSursăRMI 2018
AutorCatalin FrancuAdăugată delaurageorgescuLaura Georgescu •laurageorgescu
Timp execuţie pe test0.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Climbers

Un munte poate fi reprezentat ca o linie frântă care începe şi se termină la nivelul mării (altitudine 0) şi are altitudini strict pozitive între cele două capete (acestea se numesc altitudini interioare). Alice începe să urce muntele dintr-un capăt, iar Bob îl urcă din celălalt. Ei se pot mişca în lungul muntelui, în faţă sau în spate, dar cei doi trebuie să stea la aceeaşi altitudine (între ei).

Efortul făcut de către Alice pe un drum este suma absolută a schimbării de altitudine din acesta. Mai exact, dacă drumul făcut de Alice începe la h1 = 0, schimbă direcţia de mers la altitudinile h2, h3, ..., hp-1 şi se termină la hp, atunci efortul este |h2 - h1| + |h3 - h2| + ... + |hp - hp-1| (Bob va depune acelaşi efort).

Date de intrare

Muntele este codificat ca un vector de N numere întregi care reprezintă altitudinile capetelor segmentelor. Prima linie din fişierul de intrare climbers.in îl conţine pe N. Pe a doua linie sunt cele N numere. Se garantează că h1 = hn = 0.

Date de ieşire

În fişierul de ieşire climbers.out, afişaţi un singur întreg: efortul minim necesar (depus de Alice) pentru ca Alice şi Bob să se întâlneasca. Dacă cei doi nu se pot întâlni, afişaţi NO.

Restricţii

  • 3 ≤ N ≤ 5 000
  • Altitudinile interioare sunt între 1 si 1 000 000.
  • Pentru 25% din punctaj, toate altitudinile interioare sunt distincte.
  • Pentru 30% din punctaj, N * H < 45 000, unde H este altitudinea maximă.

Exemplu

climbers.inclimbers.out
5
0 4 2 7 0
11
7
0 10 1 20 5 10 0
48

Explicaţii

În primul exemplu, Alice pleaca din capătul stânga, iar Bob din capătul dreapta. Alice şi Bob înaintează unul spre celălalt până la altitudinea 4. Apoi, Alice merge în faţa până la altitudinea 2, în timp ce Bob merge în spate. În final, cei doi merg unul spre celălalt până se întâlnesc la altitudinea 7.
Efortul făcut este |4-0| + |2-4| + |7-2| = 4 + 2 + 5 = 11.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?