Cod sursa(job #437906)

Utilizator VladTVlad Tudose VladT Data 10 aprilie 2010 11:06:28
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 1.15 kb
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef struct{
	long weight;
	long height;
}quince;

bool compare (quince i,quince j) 
{ 
	return (i.height>j.height); 
}

long Quinces()
{
	long N,H,U,total_weight=0,sum=0,last;
	int i;
	FILE *in=fopen("gutui.in","r");
	fscanf(in,"%ld %ld %ld\n",&N,&H,&U);
	vector<quince> q(N);
	priority_queue<long> pq;

	for(i=0;i<N;i++)
	{
		
		fscanf(in,"%ld %ld\n",&q[i].height,&q[i].weight);
		total_weight+=q[i].weight;
	}
	fclose(in);
	if(!U)
	return total_weight;
    long pick;
	sort(q.begin(),q.end(),compare);
	last=q.back().height;
	pick=(last/U)*U;
	while((!q.empty()or!pq.empty())and last<=H)
	{
		if(!pq.empty())
		{
			sum+=pq.top();
			pq.pop();
			last+=U;
			pick+=U;
		}
		else
		{
		    last=q.back().height;
		    pick=(last/U)*U;
        }
        while(!q.empty()and q.back().height<=pick+U)
		{
			pq.push(q.back().weight);
			q.pop_back();
		}                       
	}
	return sum;
}

int main ()
{
	FILE *out=fopen("gutui.out","w");
	fprintf(out,"%ld",Quinces());
	fclose(out);  
	return 0;
}