This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int nbObjets, nbCadres;
vector<pair<int, int>> objets;
vector<int> cadres;
bool estPossible(int premier) {
int iCadre = premier;
for(int iObjet = 0;iObjet < nbObjets;iObjet++) {
if(iCadre != nbCadres && objets[iObjet].second <= cadres[iCadre]) {
iCadre++;
}
}
return (iCadre == nbCadres);
}
int main() {
ios_base::sync_with_stdio(false);
cin >> nbObjets >> nbCadres;
for(int iObjet = 0;iObjet < nbObjets;iObjet++) {
int taille, valeur;
cin >> taille >> valeur;
objets.push_back({valeur, taille});
}
sort(objets.begin(), objets.end());
for(int iCadre = 0;iCadre < nbCadres;iCadre++) {
int taille;
cin >> taille;
cadres.push_back(taille);
}
sort(cadres.begin(), cadres.end());
int deb = -1, fin = nbCadres + 1;
while(fin - deb > 1) {
int mil = (deb + fin) / 2;
if(estPossible(mil))
fin = mil;
else
deb = mil;
}
cout << nbCadres - fin << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |