Cod sursa(job #429960)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 30 martie 2010 17:26:25
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.07 kb
#include<fstream.h>
#include<algorithm>

using namespace std;

struct vector { long long a,b ;} v[100005];

long long n,H,u,k,h[100005],smax;

inline int cmp (const vector &v1, const vector &v2) { return v1.a>=v2.a; }

void afisare ()
{
	ofstream g("gutui.out");
	g<<smax;
	g.close();
}

void urca ()
{
	int x=k;
	while (x>1 && h[x]<h[x/2])
	{
		h[x]=(h[x]^h[x/2])^(h[x/2]=h[x]);
		x>>=1;
	}
}

void coboara ()
{
	int x=k,y=1,t;
	while (x!=y)
	{
		x=y;
		t=x<<1;
		if (t<=k && h[x]>h[t]) y=t;
		if (t+1<=k && h[y]>h[t+1]) y=t+1;
		h[x]=(h[y]^h[x])^(h[y]=h[x]);
	}
}

void dinamic ()
{
	int nr,i,max;
	for (i=1;i<=n;i++)
	{
		nr=(H-v[i].a)/u+1;
		if (nr>k)
		{
			k++;
			smax+=v[i].b;
			h[k]=v[i].b;
		}
		else
			if (h[1]<v[i].b)
			{
				smax+=(v[i].b-h[1]);
				h[1]=v[i].b;
				coboara ();
			}
	}
}

void citire ()
{
	int i;
	ifstream f("gutui.in");
	f>>n>>H>>u;
	for (i=1;i<=n;i++)
		f>>v[i].a>>v[i].b;
	f.close();
}

int main()
{
	citire ();
	sort (v+1,v+n+1,cmp);
	dinamic ();
	afisare ();
	return 0;
}