记录编号	460090	评测结果	AAAAAAAAAA
题目名称	[USACO Nov07] 挤奶时间	最终得分	100
用户昵称	WHZ0325	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2017-10-16 16:00:55	内存使用	0.31 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
struct milk0 {
	int s,e,v;
} milk[1000];
int next0[1000];
int d[1000];
bool cmp(milk0 a,milk0 b) {
	return a.s<b.s;
}
int main() {
	freopen("milkprod.in","r",stdin);
	freopen("milkprod.out","w",stdout);
	int n,m,r;
	scanf("%d%d%d",&n,&m,&r);
	for(int i=0;i<m;++i) {
		scanf("%d%d%d",&milk[i].s,&milk[i].e,&milk[i].v);
	}
	sort(milk,milk+m,cmp);
	for(int i=0;i<m;++i) {
		next0[i]=-1;
		for(int j=i+1;j<m;++j) {
			if(milk[i].e+r<=milk[j].s) {
				next0[i]=j;
				break;
			}
		}
	}
	for(int i=m-1;i>=0;--i) {
		if(next0[i]==-1) {
			d[i]=milk[i].v;
			continue;
		}
		for(int j=i+1;j<next0[i];++j) {
			d[i]=max(d[i],d[j]);
		}
		for(int j=next0[i];j<m;++j) {
			d[i]=max(d[i],d[j]+milk[i].v);
		}
	}
	printf("%d\n",d[0]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}