Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2018-06-10 15:22:10.
Revizia anterioară   Revizia următoare  

 

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 si Semicerc vorbind ca la colţul strazii. 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 blatomobil ş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 in romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase tragând cu urechea, Marcel a plecat să caute benzină în altă parte. Adică motivat.

Cerinta

Se dă un numar N şi doua siruri A şi B de câte 2N numere naturale. Să consideram o parantezare corectă de lungime 2N căreia vrem sa îi calculam costul. Pentru fiecare paranteza i, dacă e deschisă adăugam Ai iar dacă e închisa adaugă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 (adica motivat.in) conţine numarul N pe prima linie, sirul A pe a doua linie şi şirul B pe a treia linie. Un şir apare sub forma a 2N 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 numar, şi anume costul maxim al unei parantezari corecte.

Subtaskuri

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

Exemplu

table(example). |_. benzina.in |_. benzina.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

O parantezare optimă este ()()()

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?