Cod sursa(job #218199)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 1 noiembrie 2008 08:32:43
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<stdio.h>

#define NMAX 100000
struct bee{int d,a;};
bee v[NMAX+1];

void poz(int li,int ls,int&piv){
int i=li,j=ls,d=0;
bee t;
while(i<j){
	if(v[i].d>v[j].d||
	   v[i].d==v[j].d&&v[i].a<v[j].a){
			t=v[i];v[i]=v[j];v[j]=t;d=1-d;
			}
	i+=d;
	j-=1-d;
	}
piv=i;
}

void qsrt(int st,int dr){
int piv;
if(st<dr){
	poz(st,dr,piv);
	qsrt(st,piv-1);
	qsrt(piv+1,dr);
	}
}

int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int n,x,l;
scanf("%d%d%d",&n,&x,&l);
int i,j,k;
for(i=0;i<n;++i)
	scanf("%d%d",&v[i].d,&v[i].a);
qsrt(0,n-1);
int s=0,max,ok,p;
i=0,j=n-1,ok=0;
for(p=0;p<n&&v[p].d<x;++p);
if(p==n) p=n-1;
if(v[p].d>x) p--;
k=x/l;
max=v[p].a;
for(i=p;i>=0&&k>=0;--i){
	j=i;
	while(v[j].d>(k-1)*l&&j>=0){
		if(max<v[j].a) max=v[j].a;
		j--;
		}
	s+=max;k--;
	i=j+1;max=v[j].a;
	}
printf("%d",s);
return 0;
}