/* 数组开大保平安. 查分约束： 输入的时候维护st和end 设每个点取元素di个 维护元素个数前缀和s Sbi-Sai-1>=ci 即：建立一条从ai-1到bi的边 权值为ci 表示ai到bi的最小取元素个数 然后跑st到end的最长路 （建边就已经保证了最优） 最后 dis[end] 即为end的前缀和 即为st到end 符合每一个约束的最小去元素值 同时查分约束也满足性质 Sai-Sai-1>=0 Sai-1-Sai>=-1 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #define maxn 500010 using namespace std; int m,num,st=maxn,end,head[maxn],dis[maxn],f[maxn]; struct node { int v,t,pre; }e[maxn]; int init() { int x=0;char s;s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add(int from,int to,int dis) { num++; e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num; } void SPFA() { queue<int>q; q.push(st); f[st]=1; dis[st]=0; while(!q.empty()) { int k=q.front(); q.pop(); f[k]=0; for(int i=head[k];i;i=e[i].pre) if(dis[e[i].v]<dis[k]+e[i].t) { dis[e[i].v]=dis[k]+e[i].t; if(f[e[i].v]==0) { q.push(e[i].v); f[e[i].v]=1; } } } } int main() { m=init(); int x,y,z; for(int i=1;i<=m;i++) { x=init();y=init();z=init(); Add(x,y+1,z); st=min(st,x);end=max(end,y+1); } for(int i=st;i<=end;i++) { Add(i,i+1,0); Add(i+1,i,-1); } memset(dis,-10,sizeof(dis)); SPFA(); printf("%d ",dis[end]); return 0; }