Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | benzina.in, benzina.out | Sursă | Junior Challenge 2018 |
| Autor | Alexandru Petrescu, Bogdan Pop | Adăugată de |  Junior Challenge •JuniorChallenge2018 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Benzina
Textul problemei sta sub influenta noului curent literar numit umorul absent
Marcel se plimba linistit cu blatomobilul cand, deodata, ii auzi pe Dl IOI, Nry si Semicerc vorbind ca la coltul strazii. Pentru ca erau la coltul strazii. Spirit santajist, Marcel s-a gandit ca poate subtiliza informatii relevante daca sta si ii asculta. Pentru a nu parea suspect, a coborat din blatomobil si le dadea tarcoale celor trei dand senzatia ca e in cautare de benzina. In sensul de motivat. A aflat ca cei trei puneau la cale o aparitie in Azerbaidjan sub noile nume de scena Dl IOIT, Nrz, respectiv Demicerc. Realizand ca numai in romanele politiste si in scrisori pierdute poti afla informatii suficient de prestigioase tragand cu urechea, Marcel a plecat sa caute benzina in alta parte. Adica motivat.
Cerinta
Se da un numar N si doua siruri A si B de cate 2N numere naturale. Sa consideram o parantezare corecta de lungime 2N careia vrem sa ii calculam costul. Pentru fiecare paranteza i, daca e deschisa adaugam Ai iar daca e inchisa adaugam Bi. Gasiti costul maxim al unei parantezari corecte!
O parantezare este corecta daca este construita conform urmatoarelor reguli:
- <sirul vid> = <parantezare corecta>
- <parantezare corecta> + <parantezare corecta> = <parantezare corecta>
- "(" + <parantezare corecta> + ")" = <parantezare corecta>
Date de intrare
Fişierul de intrare benzina.in (adica motivat.in) contine numarul N pe prima linie, sirul A pe a doua linie sirul B pe a treia linie. Un sir apare sub forma a 2N numere naturale mai mici ca 109 separate prin cate un spatiu.
Date de ieşire
În fişierul de ieşire benzina.out (adica motivat.out) se va afla un singur numar, si anume costul maxim al unei parantezari corecte.
Subtaskuri
- Subtask Omul este o persoana umana - 5 puncte: N ≤ 10
- Subtask Sa fie bine ca sa nu fie rau - 20 de puncte: N ≤ 50
- Subtask Am marcat goluri, asa si asa, multe, dar nu prea multe - 25 de puncte: N ≤ 750
- Subtask Noi... vedete; de la inceput pana la sfarsit... nu pot sa inteleg ce s-a intamplat - 50 de puncte: N ≤ 50.000
Exemplu
| benzina.in | benzina.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
