【題解】CSES 1140 Projects

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct project{
    int a, b, p;
    bool operator <(const project &x) const{
        return a < x.a;
    }
};
 
int n, a, b, p;
long long dp[400005];
project arr[200005];
vector <int> v;
 
int getid(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a >> b >> p;
        v.push_back(a);
        v.push_back(b);
        arr[i] = {a, b, p};
    }
    sort(arr, arr+n);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int ptr = 0;
    long long ans = 0;
    for (int i = 0; i < n; i++){
        while (ptr < getid(arr[i].a)-1){
            ptr++;
            dp[ptr] = max(dp[ptr], dp[ptr-1]);
        }
        dp[getid(arr[i].b)] = max(dp[getid(arr[i].b)], dp[getid(arr[i].a)-1] + arr[i].p);
        ans = max(ans, dp[getid(arr[i].b)]);
    }
    cout << ans << "\n";
}