제출 #899322

#제출 시각아이디문제언어결과실행 시간메모리
899322stefanneaguAdvertisement 2 (JOI23_ho_t2)C++17
59 / 100
81 ms17460 KiB
// prea multe comentarii

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int nmax = 1e5 + 1;

struct str {
  int a, b;
  const bool operator < (str ult) const {
    if(b != ult.b) {
      return b < ult.b;
    }
    return a < ult.a;
  }
} v[nmax];

bool f[nmax];

int32_t main() {
  int n;
  cin >> n;
  set<str> ms;
  for(int i = 1; i <= n; i ++) {
    cin >> v[i].a >> v[i].b;
    //cout << "bag " << v[i].a << " " << v[i].b << endl;
    ms.insert({v[i].a, v[i].b});
  }
  int ans = 0;
  while(!ms.empty()) {
      //cout << endl;
    //cout << "la inceput:\n";
    //for(auto it : ms) {
      //cout << it.a << " " << it.b << "\n";
    //}
    auto it = ms.rbegin();
    ans ++;
    int ita = (*it).a, itb = (*it).b;
    //cout << "luam\n";
    //cout << ita << " " << itb << ":\n";
    for(int i = 1; i <= n; i ++) {
      if(!f[i] && abs(v[i].a - ita) <= itb - v[i].b) {
        f[i] = 1;
        if(ms.find({v[i].a, v[i].b}) != ms.end()) {
          //cout << "er\n";
          ms.erase({v[i].a, v[i].b});
        }
        //cout << v[i].a << " " << v[i].b << "\n";
      }
    }
    //cout << "\n";
  }
  //cout << "RASP: ";
  cout << ans;
  //cout << '\n';
  //for(int i = 1; i <= n; i ++) {
    //cout << i << ": " << f[i] << endl;
  //}
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...