Cod sursa(job #164837)

Utilizator AndreyPAndrei Poenaru AndreyP Data 24 martie 2008 21:22:17
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<stdio.h>
#include<stdlib.h>
struct car
{
	long long a,b;
};
car v[2002];
int compar(const void *p, const void *q)
{
	car *pp=(car*)p,*qq=(car*)q;
	car u=*pp,w=*qq;
	if(u.a<w.a)
		return -1;
	if(u.a>w.a)
		return 1;
	return u.b-w.b;
}
int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	long long n,c,i,p,j,o;
	long long x,max;
	scanf("%lld%lld",&n,&c);
	for(i=0; i<n; i++)
		scanf("%lld%lld",&v[i].a,&v[i].b);
	qsort(v,n,sizeof(v[0]),compar);
	max=-c;
	for(i=0; i<n; i++)
	{
		p=v[i].b;
		x=-c;
		o=v[0].a;
		for(j=0; j<n; j++)
		{
			if(p<=v[j].b)
				x+=p;
			x=x-((v[j].a-o)*c);
			o=v[j].a;
			if(x>max)
				max=x;
			if(x<0)
			{
				x=-c;
				o=v[j+1].a;
			}
		}
	}
	printf("%lld\n",max);
	return 0;
}