Cod sursa(job #434627)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 6 aprilie 2010 12:36:28
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.75 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define Q 100001
#define y first
#define z second
bool c(pair<int,int> i, pair<int,int> j)
{
	return (i.z<j.z)?true:false;
}
int main()
{
	int p[Q],n,h,u,i,j,k,s,v,m=0,t[Q];
	freopen("gutui.in","r",stdin);
	freopen("gutui.out","w",stdout);
	vector<pair<int,int> > x;
	scanf("%d %d %d",&n,&h,&u);
	for(i=0;i<n;i++)
	{
		scanf("%d %d",&j,&k);
		x.push_back(make_pair(j,k));
	}	
	sort(x.begin(),x.end(),c);
	p[0]=-1;
	for(i=n-1;i>=0;--i) {
		s=1+(h-x[i].y)/u;
		k=1;
		t[k]=s;		
		while(p[s]&&s>0) {
			s=p[s];
			t[++k]=s;
		}		
		if(s>0) {
			if(p[s-1])
				v=p[s-1];
			else
				v=s-1;
			for(j=1;j<=k;j++)
				p[t[j]]=v;
			m+=x[i].z;
		}
	}	
	printf("%d\n",m);
return 0;
}