paradox64ce

CSES-Projects

Jul 2nd, 2021
1,036
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct job
  2. {
  3.     int s;
  4.     int e;
  5.     int p;
  6.  
  7.     friend bool operator<(const job &a, const job &b)
  8.     {
  9.         if (a.e == b.e)
  10.         {
  11.             return a.s < b.s;
  12.         }
  13.  
  14.         return a.e < b.e;
  15.     }
  16. };
  17.  
  18. vector<int> dp(200005, -1);
  19. vector<job> jobs;
  20.  
  21. int f(int i)
  22. {
  23.     if (i == 0)
  24.     {
  25.         return dp[i] = jobs[i].p;
  26.     }
  27.     if (dp[i] != -1)
  28.     {
  29.         return dp[i];
  30.     }
  31.  
  32.     int ans = 0;
  33.     ans = f(i - 1);
  34.     job cur = {0, jobs[i].s, 0};
  35.     // need to find the last job j such that job[j].e < job[i].s
  36.     auto j = lower_bound(jobs.begin(), jobs.end(), cur) - jobs.begin();
  37.     if (j == 0)
  38.     {
  39.         ans = max(ans, jobs[i].p);
  40.     }
  41.     else
  42.     {
  43.         j--;
  44.         ans = max(ans, jobs[i].p + f(j));
  45.     }
  46.     return dp[i] = ans;
  47. }
  48.  
  49. void solve()
  50. {
  51.     int n;
  52.     cin >> n;
  53.     jobs.resize(n);
  54.     for (int i = 0; i < n; i++)
  55.     {
  56.         cin >> jobs[i].s >> jobs[i].e >> jobs[i].p;
  57.     }
  58.  
  59.     sort(jobs.begin(), jobs.end());
  60.     cout << f(n - 1) << "\n";
  61. }
RAW Paste Data