Cod sursa(job #498738)

Utilizator chiar_nimeninimeni chiar_nimeni Data 5 noiembrie 2010 21:21:30
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
# include <stdio.h>
# include <algorithm>

# define ll long long
using namespace std;

typedef struct 
{
	ll d,s;
} oaie;

oaie a[100100];
int n,m,r,i;
long long x,l,q1,q2,mx;

inline bool cmp (const oaie &x,const oaie &y)
{
	if (x.d==y.d) return x.s>y.s;
	else return x.d<y.d;
}
	
int main ()
{
freopen ("lupu.in","r",stdin);
freopen ("lupu.out","w",stdout);
scanf ("%d %d %d",&n,&x,&l);
r=0;
for (i=0; i<n; i++)
{
	scanf ("%lld %lld",&q1,&q2);
	if (q1<=x) 
	{
		a[m].d=q1;
		a[m].s=q2;
		m++;
	}		
}
sort (a,a+m,cmp);
mx=0;
int j=0;
ll sum =0;
while (a[m].d+r<=x)
{
	j=0;
	mx=0;
	while (a[j].d+r<=x-l) j++;
	while (a[j].d+r<=x)
	{
		if (a[j].s>mx) mx=a[j].s;
		j++;
	}
	sum+=mx;
	r+=l;
}
printf ("%lld\n",sum);
return 0;
}