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

#include<cstdio>
#include<algorithm>
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
struct dp{
	int End,next,w;
}st[1000006];
int f[1000006];
int n,m,R,tot,head[1000006];
void add(int x,int y,int z){
	st[++tot].End=y; st[tot].next=head[x]; st[tot].w=z; head[x]=tot;
}
int main(){
    freopen("milkprod.in","r",stdin);
	freopen("milkprod.out","w",stdout);
	scanf("%d%d%d",&n,&m,&R);
	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=head[i];j;j=st[j].next)
		 f[i]=Max(f[i],f[st[j].End]+st[j].w);
	}
	printf("%d",f[n]);
	getchar();getchar();
}