Guest User

Untitled

a guest
Sep 10th, 2020
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define MAX 1000000000
  6. #define N 100005
  7. #define mod 1000000007
  8. #define pb push_back
  9. #define mp make_pair
  10. #define F first
  11. #define S second
  12. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);
  13. #define endl "\n"
  14. #define ms(x,v) memset(x,v,sizeof(x))
  15.  
  16.  
  17.  
  18. struct s1{
  19.     ll a,b,p;
  20. };
  21.  
  22. bool comp(s1 a, s1 b){
  23.     if(a.b!=b.b){
  24.         return a.b<b.b;
  25.     }
  26.     else{
  27.         if(a.p!=b.p)
  28.             return a.p>b.p;
  29.         else return a.a>b.a;
  30.     }
  31.    
  32. }
  33.  
  34. ll solve(vector<ll>&dp, int i, int n, ll last,vector<s1>&v1){
  35.  
  36.     // last denotes the end time of the last project which was included.
  37.     if(i>=n){
  38.         return 0;
  39.     }
  40.     if(last>=v1[i].a){
  41.         return solve(dp,i+1,n,last,v1);
  42.     }
  43.     else{
  44.         if(dp[i]!=-1){
  45.             return dp[i];
  46.         }
  47.         ll res = max(solve(dp,i+1,n,last,v1),solve(dp,i+1,n,v1[i].b,v1)+v1[i].p);
  48.         dp[i]=res;
  49.         return res;
  50.     }
  51.  
  52. }
  53.  
  54. int main()
  55. {
  56.     fastio;
  57.     int n,i,j;
  58.     cin>>n;
  59.     vector<s1>v1(n);
  60.     for(i=0;i<n;i++){
  61.         ll x,y,z;
  62.         cin>>x>>y>>z;
  63.         v1[i].a=x;
  64.         v1[i].b=y;
  65.         v1[i].p=z;
  66.     }
  67.     sort(v1.begin(), v1.end(),comp);
  68.  
  69.     vector<ll>dp(n+1,-1);
  70.     cout<<solve(dp,0,n,-1,v1)<<endl;
  71.     return 0;
  72. }
Add Comment
Please, Sign In to add comment