Untitled
unknown
plain_text
a year ago
1.9 kB
4
Indexable
class Solution { public: long long dp[100001]; static bool compare(vector<int> &a, vector<int> &b) { if(a[0]<b[0]) { return true; } else if (a[0]> b[0]) { return false; } else { if(a[1]<b[1]) { return true; } else if(a[1]>b[1]) { return false; } else { return a[2]<b[2]; } } } int find(int dest, int n , vector<vector<int>> &rides) { int low = 0; int high = n-1; int ans = -1; while(low<=high) { int mid = low + (high-low)/2; if(rides[mid][0]>=dest) { ans = mid; high = mid-1; } else { low = mid+1; } } return ans; } long long recur(int index, int n, vector<vector<int>>& rides) { if(index==n) return 0; if(index==-1) return 0; if(dp[index]!=-1) return dp[index]; int dest = find(rides[index][1], n, rides); //cout<<"dest:"<< dest<<endl; long long skipCur = recur(index+1, n, rides); long long withCur = rides[index][1]-rides[index][0]+rides[index][2] + recur(dest, n, rides); dp[index]= max(skipCur, withCur); return dp[index]; } long long maxTaxiEarnings(int n, vector<vector<int>>& rides) { sort(rides.begin(), rides.end()); memset(dp, -1, sizeof(dp)); // for(auto it: rides) { // cout<<it[0]<<" "<<it[1]<<" "<<it[2]<<endl; // } return recur(0, rides.size(), rides); return 0; } };
Editor is loading...
Leave a Comment