Fişierul intrare/ieşire:plicuri.in, plicuri.outSursăFMI No Stress 4
AutorDragos OpricaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.15 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/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.inplicuri.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content