Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define MAX 1000000000
- #define N 100005
- #define mod 1000000007
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cerr.tie(NULL);
- #define endl "\n"
- #define ms(x,v) memset(x,v,sizeof(x))
- struct s1{
- ll a,b,p;
- };
- bool comp(s1 a, s1 b){
- if(a.b!=b.b){
- return a.b<b.b;
- }
- else{
- if(a.p!=b.p)
- return a.p>b.p;
- else return a.a>b.a;
- }
- }
- ll solve(vector<ll>&dp, int i, int n, ll last,vector<s1>&v1){
- // last denotes the end time of the last project which was included.
- if(i>=n){
- return 0;
- }
- if(last>=v1[i].a){
- return solve(dp,i+1,n,last,v1);
- }
- else{
- if(dp[i]!=-1){
- return dp[i];
- }
- ll res = max(solve(dp,i+1,n,last,v1),solve(dp,i+1,n,v1[i].b,v1)+v1[i].p);
- dp[i]=res;
- return res;
- }
- }
- int main()
- {
- fastio;
- int n,i,j;
- cin>>n;
- vector<s1>v1(n);
- for(i=0;i<n;i++){
- ll x,y,z;
- cin>>x>>y>>z;
- v1[i].a=x;
- v1[i].b=y;
- v1[i].p=z;
- }
- sort(v1.begin(), v1.end(),comp);
- vector<ll>dp(n+1,-1);
- cout<<solve(dp,0,n,-1,v1)<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment