记录编号	253916	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1841.[国家集训队2011]免费的馅饼(加强版)	最终得分	100
用户昵称	小一米	是否通过	通过
代码语言	C++	运行时间	0.205 s
提交时间	2016-04-23 15:01:54	内存使用	3.00 MiB

#include<bits/stdc++.h>
#define M 100002
#define low(x) (x&(-x))
using namespace std;
int W,n,ans;
int d[M],f[M],Y[M];
struct os
{
	int id,x,y,t,p,v;
}a[M];
int cmp(os xx,os yy)
{
	if (xx.x==yy.x) return xx.y>yy.y;
	return xx.x<yy.x;
}
int get(int x)
{
	int ans=0;
	for (;x;x-=low(x)) ans=max(ans,d[x]);
	return ans;
}
void add(int x,int data)
{
	for (;x<=n+1;x+=low(x)) d[x]=max(d[x],data);
}
main()
{
	freopen("free.in","r",stdin);
	freopen("free.out","w",stdout);
	scanf("%d%d",&W,&n);
	a[0].t=-W;
	a[0].x=a[0].t+a[0].p;
	a[0].y=a[0].t-a[0].p; 
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&a[i].t,&a[i].p,&a[i].v);
		a[i].t<<=1;
		a[i].x=a[i].t+a[i].p;
		a[i].y=a[i].t-a[i].p;
	}
	
	sort(a,a+n+1,cmp);
	for (int i=0;i<=n;i++) Y[i]=a[i].y;
	sort(Y,Y+n+1);
	for (int i=0;i<=n;i++) a[i].y=lower_bound(Y,Y+n+1,a[i].y)-Y+1;
	
	for	(int i=1;i<=n;i++)
	{
		f[i]=a[i].v+get(a[i].y);
		add(a[i].y,f[i]);
	}
	for (int i=1;i<=n;i++) ans=max(ans,f[i]);
	printf("%d",ans);
}