Untitled
unknown
plain_text
a year ago
948 B
1
Indexable
Never
class Solution { public: int knapsack_recursion( vector<vector<int>>& offers, int pos, int n, vector<int>& dp) { if(pos >= n) return 0; if (dp[pos] != -1) return dp[pos]; auto compareSecondElement = [](int b, vector<int>& a) { return b < a[0]; }; auto upperBoundIt = upper_bound(offers.begin(), offers.end(), offers[pos][1], compareSecondElement); dp[pos] = max(offers[pos][2] + knapsack_recursion(offers, upperBoundIt - offers.begin(), n, dp), knapsack_recursion(offers, pos + 1, n, dp)); return dp[pos]; } int maximizeTheProfit(int n, vector<vector<int>>& offers) { sort(offers.begin(), offers.end()); vector<int> dp = vector<int>(offers.size() + 1,-1); int res = knapsack_recursion(offers, 0, offers.size(), dp); return res; } };