Cod sursa(job #602053)

Utilizator smaraldaSmaranda Dinu smaralda Data 8 iulie 2011 21:20:57
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include<stdio.h>
#include<stdlib.h>
struct oi { int d, a,t; };
oi oaie[100010];
struct TIP {int c1,c2; };
TIP aux[100010];
bool f[100010];
int comp (const void *x, const void *y)
{
	oi *pa,*pb;
	pa=(oi *)x;
	pb=(oi *)y;
	if(pa->a==pb->a) return 0;
	if(pa->a>pb->a) return -1;
	return 1;
}

int comp2 (const void *x, const void *y)
{
	TIP *pa,*pb;
	pa=(TIP *)x;
	pb=(TIP *)y;
	if(pa->c2==pb->c2) return 0;
	if(pa->c2>pb->c2) return -1;
	return 1;
}

int bs ( int val, int n)
{
	int st,dr,med;
	st=1; dr=n;
	while(st<dr)
		{
			med=(st+dr)/2;
			if(aux[med].c2==val) return med;
			if(aux[med].c2>val)   dr=med-1;
			if(aux[med].c2<val)   st=med+1;
		}
	return -1;
}

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	int i,rez,j,n,k,x,l;
	scanf("%d%d%d",&n,&x,&l);
	for(i=1;i<=n;i++)
		{
			scanf("%d%d",&oaie[i].d,&oaie[i].a);
			oaie[i].t=(x-oaie[i].d)/2;
		}
	qsort(oaie+1,n,sizeof(oaie[0]),comp);
	for(i=1;i<=n;i++)
		{
			aux[i].c1=i;
			aux[i].c2=oaie[i].t;
		}
	qsort(aux+1,n,sizeof(aux[0]),comp2);
	rez=0;
	for(i=1;i<=n;i++)
		{
			if(f[oaie[i].t]==0) 
				{ 
					rez=rez+oaie[i].a;
					f[oaie[i].t]=1;
				}
			else
				{
					k=bs(oaie[i].t,n);
					if(k==-1) continue;
					for(j=k;j>=1;j--)
						if(f[oaie[aux[j].c1].t]==0)
							{
								rez=rez+oaie[aux[j].c1].a;
								f[oaie[aux[j].c1].t]=1;
							}
				}
		}
    printf("%d\n",rez);
	return 0;
}