比赛 |
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;
}