Fişierul intrare/ieşire:benzina.in, benzina.outSursăJunior Challenge 2018
AutorAlexandru Petrescu, Bogdan PopAdăugată deJuniorChallenge2018Junior Challenge JuniorChallenge2018
Timp execuţie pe test0.15 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Benzina

Textul problemei stă sub influenţa noului curent literar numit umorul absent

Marcel se plimba liniştit cu blatmobilul când, deodată, îi auzi pe Dl. IOI, Nry şi Semicerc vorbind ca la colţul străzii. Pentru că erau la colţul străzii. Spirit şantajist, Marcel s-a gândit că poate subtiliza informaţii relevante dacă stă şi îi ascultă. Pentru a nu părea suspect, a coborât din blatmobil şi le-a dat târcoale celor trei, dând senzaţia că e în căutare de benzină. În sensul de motivat. A aflat că cei trei puneau la cale o apariţie în Azerbaidjan sub noile nume de scenă Dl. IOIT, Nrz, respectiv Demicerc. Realizând că numai în romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase trăgând cu urechea, Marcel a plecat să caute benzină în altă parte. Adică motivat.

Cerinţă

Se dă un număr N şi două şiruri A şi B de câte 2 * N numere naturale. Să considerăm o parantezare corectă de lungime 2 * N căreia vrem să îi calculăm costul. Pentru fiecare paranteză i, dacă e deschisă adăugam Ai iar dacă e închisă adăugăm Bi. Găsiţi costul maxim al unei parantezări corecte!

O parantezare este corectă dacă este construită conform următoarelor reguli:

  • <şirul vid> = <parantezare corectă>
  • <parantezare corectă> + <parantezare corectă> = <parantezare corectă>
  • "(" + <parantezare corectă> + ")" = <parantezare corectă>

Date de intrare

Fişierul de intrare benzina.in (adică motivat.in) conţine numărul N pe prima linie, şirul A pe a doua linie şi şirul B pe a treia linie. Un şir apare sub forma a 2 * N numere naturale mai mici ca 109 separate prin câte un spaţiu.

Date de ieşire

În fişierul de ieşire benzina.out (adica motivat.out) se va afla un singur număr, şi anume costul maxim al unei parantezări corecte.

Subtaskuri

  • Subtask Omul este o persoană umană - 4 puncte (testele 1 şi 2): N ≤ 10
  • Subtask Să fie bine ca să nu fie rău - 20 de puncte (testele 3-12): N ≤ 50
  • Subtask Am marcat goluri, aşa şi aşa, multe, dar nu prea multe - 24 de puncte (testele 13-24): N ≤ 750
  • Subtask Noi... vedete; de la început până la sfârşit... nu pot să înţeleg ce s-a întâmplat - 52 de puncte (testele 25-50): N ≤ 50.000

Exemplu

benzina.inbenzina.out
3
5 1 4 8 7 5
3 7 7 8 5 2
33
5
7 4 7 7 4 4 4 7 7 7
4 7 4 4 7 7 7 4 4 4
61

Explicaţie

Pentru primul exemplu, o parantezare optimă este ()()().
Pentru al doilea exemplu, câteva dintre parantezările optime sunt (((()))()), (((())))() şi ()(()()()).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?