Cod sursa(job #22158)

Utilizator blasterzMircea Dima blasterz Data 25 februarie 2007 21:08:53
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#define maxn 100001
#include <algorithm>
using namespace std;
struct nod { int c, d;};

	int N, X, L, i,j;
	nod x[maxn];


bool operator<(const nod &a, const nod &b)
{
	if(a.d>b.d) return 1;
	if(a.d==b.d) if(a.c>b.c) return 1;
	return 0;
}

int main()
{
	freopen("lupu.in", "r", stdin);
	
	scanf("%d %d %d\n", &N, &X, &L);
	for(i=1;i<=N;i++) scanf("%d %d\n", &x[i].d, &x[i].c);
	
	sort(x+1, x+N+1);
	int nr=1;
	long long sum=0;
	
	//for(i=1;i<=N;i++) printf("%d %d\n", x[i].d, x[i].c);
	
//printf("%d\n", L);
	int p;
	i=1;
	while(i<=N)
	{
	
	p=i;
	for(;i<=N;i++)
		if(x[i].d<=X-nr*L)break;
i--;
	int max=-1;
		for(j=p;j<=i;j++) if(x[j].c>max && x[i].d<=X) max=x[j].c;
		sum+=(long long) max;
		nr++;
		i++;
		if(max==-1) break;
	//printf("(%d)\n", i);
	}
	freopen("lupu.out", "w", stdout);
	printf("%lld\n", sum);
	return 0;
}