记录编号	96340	评测结果	AAAAAAAAAA
题目名称	[USACO Dec05]清理牛棚	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.088 s
提交时间	2014-04-12 16:02:48	内存使用	13.81 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int SIZEN=10010;
class COW{
public:
	int t1,t2,s;
}c[SIZEN];
bool operator < (COW a,COW b){
	return a.t1<b.t1;
}
int N;
int M,E;
int f[SIZEN]={0};
priority_queue<pair<int,int> > Q;//first是f值的相反数,second是编号
void work(void){
	sort(c+1,c+1+N);
	f[1]=c[1].s;
	Q.push(make_pair(-f[1],1));
	for(int i=2;i<=N;i++){
		while(!Q.empty()&&c[Q.top().second].t2<c[i].t1-1) Q.pop();
		if(Q.empty()){
			printf("-1\n");
			return;
		}
		int x=Q.top().second;
		f[i]=f[x]+c[i].s;
		Q.push(make_pair(-f[i],i));
	}
	int ans=0x7fffffff;
	for(int i=1;i<=N;i++) if(c[i].t2>=E) ans=min(ans,f[i]);
	printf("%d\n",ans);
}
void read(void){
	scanf("%d%d%d",&N,&M,&E);
	for(int i=1;i<=N;i++) scanf("%d%d%d",&c[i].t1,&c[i].t2,&c[i].s);
}
int main(){
	freopen("clean.in","r",stdin);
	freopen("clean.out","w",stdout);
	read();
	work();
	return 0;
}