POJ2970 The lazy programmer

解いてる人が233人で難しそうとか思ったけど考えてみると普通にgreedyに選んでいけばいいだけということに気付く。

なんでこんなに通してる人少ないんだろう。

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
#define mt(A,B,C) make_pair(A,make_pair(B,C))
typedef pair<int,int>pii;
typedef pair<int,pii>pi3;
typedef pair<int,double>pid;
int main()
{
	int num;
	scanf("%d",&num);
	vector<pi3>vec;
	for(int i=0;i<num;i++)
	{
		int za,zb,zc;
		scanf("%d%d%d",&za,&zb,&zc);
		vec.push_back(mt(zc,za,zb));
	}
	sort(vec.begin(),vec.end());
	priority_queue<pii>que;
	double ret=0;
	int tim=0;
	for(int i=0;i<num;i++)
	{
		tim+=vec[i].second.second;
		que.push(make_pair(vec[i].second.first,vec[i].second.second));
		if(tim>vec[i].first)
		{
			for(;;)
			{
				pii zan=que.top();
				que.pop();
				if(tim-zan.second<=vec[i].first)
				{
					zan.second-=tim-vec[i].first;
					ret+=double(tim-vec[i].first)/double(zan.first);
					tim=vec[i].first;
					que.push(zan);
					break;
				}
				else
				{
					ret+=double(zan.second)/double(zan.first);
					tim-=zan.second;
				}
			}
		}
	}
	printf("%.2lf\n",ret);
}

なんとなくJOI過去問の「ダンジョン」に似てる気がした。