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 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 si le dadea tarcoale celor trei dand senzatia ca e in cautare 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ă in alta 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ă daca 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, si anume costul maxim al unei parantezari corecte.
Subtaskuri
- Subtask Omul este o persoana umana - 4 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 - 24 de puncte: N ≤ 750
- Subtask Noi... vedete; de la inceput pana la sfarsit... nu pot sa inteleg ce s-a intamplat - 52 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
...
