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

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int SIZEN=100010;
class miku
{
public:
	int x,y;//x为t*2，y为p
	int t,p,v;
}P[SIZEN];
int w,n;
void read()
{
	scanf("%d%d",&w,&n);
	P[0].t=-w;P[0].p=0;P[0].v=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&P[i].t,&P[i].p,&P[i].v);
		P[i].t*=2;
	}
	for(int i=0;i<=n;i++) P[i].x=P[i].t+P[i].p,P[i].y=P[i].t-P[i].p;//坐标变换
}
bool cmp(miku a,miku b)
{
	if(a.x==b.x) return a.y>b.y;
	return a.x<b.x; 
}
void prepare()
{
	sort(P,P+n+1,cmp);
	int Y[SIZEN];
	for(int i=0;i<=n;i++) Y[i]=P[i].y;
	sort(Y,Y+n+1);
	for(int i=0;i<=n;i++) P[i].y=lower_bound(Y,Y+n+1,P[i].y)-Y+1;
}
int tr[SIZEN]={0};//树状数组
int lowbit(int x)
{
	return x&(-x);
}
void add(int y,int x)
{
	for(int i=y;i<=n+1;i+=lowbit(i))
	{
		tr[i]=max(tr[i],x);
	}
}
int get(int x)
{
	int re=0;
	for(int i=x;i>0;i-=lowbit(i))
	{
		re=max(re,tr[i]);
	}
	return re;
}
int f[SIZEN]={0},ans=0;
void work()
{
	prepare();//离散化
	for(int i=1;i<=n;i++)
	{
		int p=get(P[i].y);
		f[i]=p+P[i].v;
		if(f[i]>ans) ans=f[i];
		add(P[i].y,f[i]);
	}
	printf("%d",ans);
}
int main()
{
	freopen("free.in","r",stdin);
	freopen("free.out","w",stdout);
	read();
	work();
	return 0;
}