CSES-Projects

struct job
{
    int s;
    int e;
    int p;

    friend bool operator<(const job &a, const job &b)
    {
        if (a.e == b.e)
        {
            return a.s < b.s;
        }

        return a.e < b.e;
    }
};

vector<int> dp(200005, -1);
vector<job> jobs;

int f(int i)
{
    if (i == 0)
    {
        return dp[i] = jobs[i].p;
    }
    if (dp[i] != -1)
    {
        return dp[i];
    }

    int ans = 0;
    ans = f(i - 1);
    job cur = {0, jobs[i].s, 0};
    // need to find the last job j such that job[j].e < job[i].s
    auto j = lower_bound(jobs.begin(), jobs.end(), cur) - jobs.begin();
    if (j == 0)
    {
        ans = max(ans, jobs[i].p);
    }
    else
    {
        j--;
        ans = max(ans, jobs[i].p + f(j));
    }
    return dp[i] = ans;
}

void solve()
{
    int n;
    cin >> n;
    jobs.resize(n);
    for (int i = 0; i < n; i++)
    {
        cin >> jobs[i].s >> jobs[i].e >> jobs[i].p;
    }

    sort(jobs.begin(), jobs.end());
    cout << f(n - 1) << "\n";
}