Fişierul intrare/ieşire:cuplaje.in, cuplaje.outSursăAlgoritmiada 2016 Runda 3 Seniori
AutorEugenie Daniel PosdarascuAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuplaje

Se spune ca in general dragostea e oarba. In cazul de fata in schimb nu este asa: dragostea este sistematica si bine definita din punct de vedere matematic. Mai exact, avem N baieti numerotati de la 1 la N. Acestia sunt ordonati dupa cat de bogati sunt ei ( 1 este cel mai bogat, N este cel mai sarac). De asemenea, avem M fete numerotate de la 1 la M. Acestea sunt ordonate dupa cat de frumoase sunt ( 1 este cea mai frumoasa, M este cea mai ur.... mai putin frumoasa).

Fiecare baiat respectiv fata au desigur preferintele lor, dar acestea determina o relatie de ordine foarte simpla. Daca un baiat este dispus sa se cupleze cu o fata X, atunci acesta este dispus sa se cupleze cu orice fata mai frumoasa ca ea (orice alta fata Y ≤ X). Asemanator, daca o fata este dispusa sa se cupleze cu un baiat X, atunci aceasta este dispusa sa se cupleze cu orice baiat mai bogat ca acesta (orice alt baiat Y ≤ X).

Dandu-se pentru fiecare baiat, respectiv fata, care este cea mai slaba preferinta cu care ar fi de acord sa se cupleze, sa se determine numarul maxim de cuplari ce pot fi realizate intre cei N baieti si M fete, ştiind că fiecare băiat, respectiv fată poate fi implicat/implicată într-un singur cuplu.

Date de intrare

Fişierul de intrare cuplaje.in va conţine pe prima sa linie numerele N şi M. A doua linie va conţine N numere, reprezentând preferinţa "worst-case" a fiecărui băiat. A treia linie va conţine M numere, reprezentând preferinţa "worst-case" a unei fete.

Date de ieşire

În fişierul de ieşire cuplaje.out se va afla un singur număr, reprezentând numărul maxim de cupluri care se pot forma.

Restricţii

  • 1 ≤ N, M ≤ 200.000
  • Elementele din primul şir au valori între 1 şi M, iar cele din al doilea şir au valori între 1 şi N.
  • Acest enunţ este un pamflet şi nu reflectă opinia noastră despre băieţi, fete, bogăţie sau frumuseţe.

Exemplu

cuplaje.incuplaje.out
3 4
2 3 1
3 1 1 1
2

Explicaţie

Primul băiat este de acord cu oricare din primele două fete. Al doilea băiat este de acord cu oricare din primele 3 fete, iar al treilea (deşi cel mai puţin bogat) este de acord să se cupleze doar cu prima fată. Se pot face două cupluri: prima fată cu al doilea băiat, respectiv a doua fată cu primul băiat. Nu putem obţine un număr mai mare de cupluri, deoarece cu excepţia celei mai frumoase fete, restul sunt destul de pretenţioase.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?