Advertisement
Mirbek

E (ODS)

Jan 28th, 2022
649
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e5;
  6. const long long inf = 2e18;
  7.  
  8. int n;
  9. long long T, d[N];
  10.  
  11. int main(){
  12.     cin >> n >> T;
  13.  
  14.     vector < pair <int, long long> > vec;
  15.     for (int i = 1; i <= n; i++) {
  16.         long long p, v;
  17.         cin >> p >> v;
  18.         vec.push_back(make_pair(p, p + v * T));
  19.     }
  20.  
  21.     d[0] = -inf;
  22.     for (int i = 1; i < N; i++) {
  23.         d[i] = inf;
  24.     }
  25.  
  26.     sort(vec.rbegin(), vec.rend());
  27.  
  28.     for (int i = 0; i < vec.size(); i++) {
  29.         long long finish = vec[i].second + i;
  30.         int j = upper_bound(d, d + n, finish) - d;
  31.         if (d[j - 1] < finish && d[j] > finish) {
  32.             d[j] = finish;
  33.         }
  34.     }
  35.  
  36.     for (int i = N - 1; i >= 0; i--) {
  37.         if (d[i] != inf) {
  38.             cout << i << endl;
  39.             return 0;
  40.         }
  41.     }
  42. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement