Advertisement
LoopyMango

D.D.1.

Jul 18th, 2023
690
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | Source Code | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define uint unsigned long long
  5. #define hayai ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
  6. const int MAX = 2000005;
  7. #define yes cout << "YES" <<"\n"
  8. #define no cout << "NO" << "\n"
  9. const long long mod=1e9+7;
  10. int fb(vector<int> &ep ,int val)
  11. {
  12.   auto it = lower_bound(ep.begin(),ep.end(),val);
  13.   if(it==ep.begin())
  14.    return 0;
  15.   else it--;
  16.    return it-ep.begin()+1;
  17.  
  18. }
  19. int32_t main() {
  20.     hayai;
  21.     int t =1;
  22.     // cin >> t;
  23.  
  24.     while(t--)
  25.     {
  26.       int  n;
  27.       cin >> n ;
  28.       vector<pair<int,pair<int,int>>>v(n);
  29.       for(int i =0;i<n;i++)
  30.       {
  31.         cin >> v[i].second.first >> v[i].first >> v[i].second.second ;
  32.       }
  33.       sort(v.begin(),v.end());
  34.       int dp[n+1];
  35.       dp[0]=0;
  36.       vector<int> end;
  37.       for(int i=0;i<n;i++)
  38.        {
  39.         end.push_back(v[i].first);
  40.        }
  41.        for(int i =0;i<n;i++)
  42.        {
  43.          int op1 = dp[i];
  44.          int op2  = v[i].second.second;
  45.          int j = fb(end,v[i].second.first);
  46.          op2+=dp[j];
  47.          dp[i+1]=max(op1,op2);
  48.        }
  49.        cout << dp[n] << "\n";
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement