Cod sursa(job #629206)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 2 noiembrie 2011 20:55:13
Problema Gutui Scor 100
Compilator cpp Status done
Runda gc_practice Marime 0.91 kb
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
int n,h,u,sol;
struct Gutuie{int h,g;};
Gutuie A[100010];

void Citire()
{
	int i;
	ifstream fin("gutui.in");
	fin>>n>>h>>u;
	for(i=1;i<=n;i++)
		fin>>A[i].h>>A[i].g;
	fin.close();
}

inline bool Sortare(Gutuie A,Gutuie B)
{
	if(A.h==B.h)
		return A.g>B.g;
	return A.h<B.h;
}

void Rezolvare()
{
	priority_queue <int> H;
	int alt,poz,ok=1;
	sort(A+1,A+n+1,Sortare);
	alt=h;
	while(alt-u>=A[1].h)
		alt-=u;
	poz=1;
	while(ok)
	{
		if(A[poz].h>alt || poz>n)
		{
			if(!H.empty())
			{
				sol+=H.top();
				H.pop();
			}
			alt+=u;
			if(alt>h)
				ok=0;
		}
		else
			if(A[poz].h<=alt && poz<=n)
			{
				H.push(A[poz].g);
				poz++;
			}
	}
}

void Afisare()
{
	ofstream fout("gutui.out");
	fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}