比赛 20120615 评测结果 AAAATTTTTT
题目名称 新打鼹鼠 最终得分 40
用户昵称 ZhouHang 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2012-06-15 17:51:25
显示代码纯文本
/**
*Prob	: strike
*Data	: 2012-6-15
*Sol	: 动归
*Author : ZhouHang
*/

#include <cstdio>
#include <algorithm>
#include <cstring>

#define MaxN 101000
#define MaxM 101000

using namespace std;

struct node
{
	int t,w,x;
} a[MaxN];
int n,m,p;
int f[MaxN];

int ABS(int x)
{
	if (x<0) return -x;
	return x;
}

bool cmp(node q,node w)
{
	return q.t<w.t;
}

int main()
{
	freopen("strike.in","r",stdin);
	freopen("strike.out","w",stdout);
	
	scanf("%d%d%d",&n,&m,&p);
	
	int ans=0;
	
	for (int i=1; i<=m; i++)
		scanf("%d%d%d",&a[i].t,&a[i].w,&a[i].x);

	sort(a+1,a+1+m,cmp);
	
	for (int i=1; i<=m; i++)
	{
		f[i]=a[i].w;
		if (f[i]>ans) ans=f[i];
	}
	
	for (int i=1; i<=m; i++)
	 for (int j=1; j<i; j++)
		if ( ABS(a[i].x-a[j].x)<=((a[i].t-a[j].t)*p) )
		{
			f[i]=max(f[i],f[j]+a[i].w);
			if (f[i]>ans) ans=f[i];
		}
	
	printf("%d\n",ans);

	fclose(stdin); fclose(stdout);
	return 0;
}