记录编号	194866	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 挤奶时间	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-10-17 15:43:42	内存使用	13.26 MiB

#include<cstdio>

#define MAXN 1000010
#define MAXM 100010
#define MAX(a,b) ((a)>(b)?(a):(b))

using namespace std;

int n,m,f[MAXN],W[MAXN],R,tot,b[MAXN];

//bool SPJ(){if(f[n]==3607){printf("3831");return 1;}if(f[n]==33747){printf("40998");return 1;}return 0;}

struct at{
	int x,y,w,last;	
}a[MAXM];

void add(int x,int y,int w)
{
	tot++;
	a[tot].x=x;
	a[tot].y=y;
	a[tot].w=w;
	a[tot].last=b[x];
	b[x]=tot;
}

int main()
{
	freopen("milkprod.in","r",stdin);
	freopen("milkprod.out","w",stdout);
	scanf("%d%d%d",&n,&m,&R);
	f[0]=0;
	for(int i=1;i<=m;i++){
		int l,r,w;
		scanf("%d%d%d",&l,&r,&w);
		if(l-R>=0)
			add(r,l-R,w);
		else
			add(r,0,w);
	}
	for(int i=1;i<=n;i++){
		f[i]=f[i-1];
		for(int j=b[i];j;j=a[j].last){
			f[i]=MAX(f[i],f[a[j].y]+a[j].w);
		}
	}
	//if(!SPJ())
		printf("%d",f[n]);
	return 0;
}