Cod sursa(job #434635)

Utilizator vdobrotaDobrota Valentin Eugen vdobrota Data 6 aprilie 2010 12:46:36
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.66 kb
#include<fstream>
#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);
}
int main() {
	int p[Q],n,h,u,i,j,k,s,v,m=0,t[Q];
	ifstream f("gutui.in",ios::in);
	ofstream g("gutui.out",ios::out);
	vector<pair<int,int> > x;
	f>>n>>h>>u;
	for(i=0;i<n;i++) {
		f>>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;
		t[k=1]=s;		
		for(;p[s]&&s>0;t[++k]=s=p[s]);				
		if(s>0) {
			v=(p[s-1]?p[s-1]:s-1);
			for(j=1;j<=k;j++)
				p[t[j]]=v;
			m+=x[i].z;
		}
	}	
	g<<m;
return 0;
}