Cod sursa(job #95729)

Utilizator andrei.12Andrei Parvu andrei.12 Data 29 octombrie 2007 21:45:08
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<stdio.h>
#include<stdlib.h>
int n, l, d, i, j, li, ls, x, max;
long long t, rezultat;
struct read{
	int l, d;
};
read v[100005];
int cmp(const void*a, const void*b){
	read x = *(read*)a, y = *(read*)b;
	if (x.d < y.d) return -1;
	if (x.d > y.d) return 1;
	return 0;
}
int caut(){
	int x;
	while (li <= ls){
		x = (li+ls) / 2;
		if (v[x].d + t + l > d)
			if (v[x-1].d +t +l <= d)
				return x-1;
			else
				ls = x-1;
		else
			li = x+1;
	}
	return 0;
}
int main()
{
	freopen("lupu.in", "rt", stdin);
	freopen("lupu.out", "wt", stdout);
	scanf("%d%d%d", &n, &d, &l);
	for (i=1; i<=n; i++)
		scanf("%d%d", &v[i].d, &v[i].l);
	qsort(v, n+1, sizeof(v[0]), cmp);
	li = 1;
	ls = n;
	t = 0;
	while (ls){
		j = ls;
		x = caut();
		if (!x)
			printf("%d", v[155555].l);
		t += l;
		max = 0;
		for (i=j; i>=x; i--)
			if (v[i].l > max)
				max = v[i].l;
		rezultat += max;
		ls = x;
		li = 1;
	}
	printf("%lld\n", rezultat);
	fclose(stdin);
	fclose(stdout);
	return 0;
}