Cod sursa(job #229388)

Utilizator cotofanaCotofana Cristian cotofana Data 10 decembrie 2008 00:03:34
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#define dim 100000

long n, x, l, c[dim+1], d[dim+1], init, s=0;
char fol[dim+1]={0};

void quicksort (long *a, long *b, long lo, long hi)
{
    long i=lo, j=hi, h;
    long x=a[(lo+hi)/2];

    do
    {
	while (a[i]>x || (a[i]==x && b[i]>b[(hi+lo)/2])) i++;
	while (a[j]<x || (a[j]==x && b[j]<b[(hi+lo)/2])) j--;
	if (i<=j)
	{
	    h=a[i]; a[i]=a[j]; a[j]=h;
	    h=b[i]; b[i]=b[j]; b[j]=h;
	    i++; j--;
	}
    } while (i<=j);

    if (lo<j) quicksort(a, b, lo, j);
    if (i<hi) quicksort(a, b, i, hi);
}


int main()
{
	long i, j, max=0;
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	scanf("%ld %ld %ld\n", &n, &x, &l);
	for (i=1; i<=n; i++) scanf("%ld %ld\n", &d[i], &c[i]);
	quicksort(c, d, 1, n);
	for (i=1; i<=n; i++)
	{
		d[i]=(x-d[i])/l+1;
		if (d[i]>max) max=d[i];
	}
	for (i=1; i<=max; i++)
	{
		j=1;
		while (d[j]-i<0) j++;
		s+=c[j];
                d[j]=0;
	}
	printf("%ld\n", s);
	return 0;
}