记录编号	94063	评测结果	AAAAAAAAAAAAAAAA
题目名称	1568.[USACO Oct05]奶牛航班	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.203 s
提交时间	2014-03-29 21:39:17	内存使用	0.55 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int SIZEN=10010;
vector<pair<int,int> > southward[SIZEN],northward[SIZEN];//从某个机场向南/北飞
//在处理时,不妨改变从南到北的坐标以使其亦为1~N
int N,K,C;
int deal(vector<pair<int,int> > pas[SIZEN]){//乘客信息是pas
	multiset<int,greater<int> > load;//从大到小
	multiset<int,greater<int> >::iterator key;
	int ans=0;
	for(int i=1;i<=N;i++){
		key=load.end();if(!load.empty()) key--;
		while(!load.empty()&&(*key)==i) load.erase(key--),ans++;//卸人
		int j=0,k=1;
		while(load.size()<C&&j<pas[i].size()){//若人未满,试图上人
			load.insert(pas[i][j].first);k++;
			if(k==pas[i][j].second+1) j++,k=1;
		}
		if(load.size()==C){//若人已满,尝试取代
			while(j<pas[i].size()){
				key=load.begin();
				if(pas[i][j].first<(*key)){
					load.erase(key);
					load.insert(pas[i][j].first);k++;
					if(k==pas[i][j].second+1) j++,k=1;
				}
				else break;
			}
		}
	}
	return ans;
}
void read(void){
	scanf("%d%d%d",&K,&N,&C);
	int S,E,M;
	for(int i=1;i<=K;i++){
		scanf("%d%d%d",&S,&E,&M);
		if(S<=E) southward[S].push_back(make_pair(E,M));//从北向南
		else northward[N+1-S].push_back(make_pair(N+1-E,M));//从南向北
	}
	for(int i=1;i<=N;i++) sort(southward[i].begin(),southward[i].end());
	for(int i=1;i<=N;i++) sort(northward[i].begin(),northward[i].end());
}
int main(){
	freopen("cowflight.in","r",stdin);
	freopen("cowflight.out","w",stdout);
	read();
	printf("%d\n",deal(southward)+deal(northward));
	return 0;
}