| 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 are timp deoarece este foarte preocupat cu meciul dintre Grecia si Romania si de pariurile puse, evident, in favoarea tricolorilor.
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 |
|---|---|
| 4 4 5 1 3 2 6 7 8 | 3 |
Explicaţie
Al doilea plic cu dimensiunile L = 1 si W = 3 intra in primul plic, cu dimensiunile L = 4 si W = 5, care la randul lui intra in ultimul plic cu dimensiunile L = 7 si W = 8. O alta solutie cu numar maximal de plicuri care intra unul in altul este sirul de plicuri 2, 3, 4, ambele avand lungimea 3.
