Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | plicuri.in, plicuri.out | Sursă | FMI No Stress 4 |
| Autor | Dragos Oprica | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Plicuri
Se da un sir cu 2*N numere, reprezentand lungimea L si latimea W a N plicuri. PalanRit vrea sa puna plicurile unul intr-altul si sa obtina un astfel de sir de plicuri, care intra unul intr-altul, cat mai mare. El poate sa puna un plic i intr-un plic j daca si numai daca: L[i] < L[j] si W[i] < W[j] sau L[i] < W[j] si W[i] < L[j]. Voi trebuie sa determinati lungimea maxima a unui astfel de sir de plicuri, pentru ca PalanRit nu este instare.
h2. Date de intrare
Pe prima linie a fisierului de intrare plicuri.in se afla N, reprezentand numarul de plicuri. Pe urmatoarele N linii se afla cate doua numere L[i] si W[i], separate printr-un spatiu, reprezentand lungimea si latimea plicului i.
Date de ieşire
In fisierul de iesire plicuri.out veti afisa un singur numar, reprezentand lungimea maxima a unui sir de plicuri care respecta conditia din enunt.
Restricţii
- 1 ≤ N ≤ 100 000
- Pentru 40% din teste, 1 ≤ N ≤ 2 500
- 1 ≤ L[i], W[i] ≤ 100 000, 1 ≤ i ≤ N
- ATENTIE! Cea dea doua conditie din enunt spune defapt ca plicurile se pot roti.
Exemplu
| plicuri.in | plicuri.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
