记录编号	601535	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	100
用户昵称	秋_Water	是否通过	通过
代码语言	C++	运行时间	0.396 s
提交时间	2025-06-25 17:39:30	内存使用	3.98 MiB

#include <bits/stdc++.h>
#define lowbit(x) x&-x 
using namespace std;
const int N=1e5+7;
struct node{
	int t,p,v,x; 
}a[N];
int w,n,f[N],prework[N],t[N],ans;
bool cmp(node x,node y){
	return x.p-2*x.t>=y.p-2*y.t;
}
void add(int x,int val){
	for(int i=x;i<=n;i+=lowbit(i)){
		t[i]=max(t[i],val); 
	}
}
int query(int x){
	int ans=0;
	for(int i=x;i;i-=lowbit(i)){
		ans=max(ans,t[i]);
	}
	return ans; 
}
int main(){
	freopen("free.in","r",stdin); 
	freopen("free.out","w",stdout);	
	cin>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].t>>a[i].p>>a[i].v; 
		prework[i]=a[i].p+2*a[i].t; 
	} 
	sort(prework+1,prework+n+1);
	for (int i=1;i<=n;i++){
		a[i].x=lower_bound(prework+1,prework+n+1,a[i].p+2*a[i].t)-prework;
	} 
	sort(a+1,a+n+1,cmp); 
	for(int i=1;i<=n;i++){
		f[i]=query(a[i].x)+a[i].v;
		add(a[i].x,f[i]); 
		ans=max(ans,f[i]); 
	}
	cout<<ans<<"\n";
	
	return 0;
}