记录编号	601503	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	100
用户昵称	徐诗畅	是否通过	通过
代码语言	C++	运行时间	0.238 s
提交时间	2025-06-25 15:31:03	内存使用	4.16 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int w,n,f[N],c[N];
void up(int x,int y){for(;x<=n;x+=x&-x) c[x]=max(c[x],y);}
int ask(int x){
	int y=0;
	for(;x;x-=x&-x) y=max(c[x],y);
	return y;
}
struct str{
	int t,p,v,x;
}a[N];
bool cmp(str x,str y){
	return x.p-2*x.t>=y.p-2*y.t;
}
int b[N];
int main(){
	freopen("free.in","r",stdin);
	freopen("free.out","w",stdout);
	scanf("%d%d",&w,&n);
	for(int i = 1;i<=n;i++){
		scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].v);
		b[i]=a[i].p+2*a[i].t;
	}
	sort(b+1,b+1+n);
	for(int i = 1;i<=n;i++)
	a[i].x=lower_bound(b+1,b+1+n,a[i].p+2*a[i].t)-b;
	sort(a+1,a+1+n,cmp); int ans=0;
	for(int i = 1;i<=n;i++){
		f[i]=ask(a[i].x)+a[i].v;
		up(a[i].x,f[i]);
		ans=max(ans,f[i]);
	}
	printf("%d",ans);
}