比赛 2026.1.8 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 区间价值 最终得分 100
用户昵称 汐汐很希希 运行时间 1.808 s
代码语言 C++ 内存使用 4.79 MiB
提交时间 2026-01-08 20:26:01
显示代码纯文本
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=0;
const int MOD=998244353;
const int MAXX=2e9;
int n,et[N],dp[N];
struct Interval{
	int l,r,w;
}s[N];
bool cmp(Interval a,Interval b)
{
	if(a.r==b.r) return a.l<b.l;
	return a.r<b.r;
}
int main()
{
	freopen("sum.in","r",stdin);
	freopen("sum.out","w",stdout);
	
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i].l>>s[i].r>>s[i].w;
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++) et[i]=s[i].r;
	dp[0]=0;
	for(int i=1;i<=n;i++){
        int l=s[i].l,w=s[i].w;
        int L=1,R=i-1,p=0;
        while(L<=R){
            int mid=(L+R)/2;
            if(et[mid]<l){
                p=mid;
                L=mid+1;
            }else R=mid-1;
        }
        dp[i]=max(dp[i-1],dp[p]+w);
    }
    cout<<dp[n]<<endl;
	return 0;
}