제출 #109981

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
109981		Arturgo	Exhibition (JOI19_ho_t2)	C++14	100 / 100	128 ms	5072 KiB

joi2019_ho_t2

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50