Cod sursa(job #146034)

Utilizator hadesgamesTache Alexandru hadesgames Data 1 martie 2008 08:23:20
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <stdlib.h>
struct ceva
{
	long long a,b;
};
ceva a[2005];
long long b[2005];
long long max=-1;
int compare(const void *a,const void *b)
{
	ceva *aa=(ceva*)a;
	ceva *bb=(ceva*)b;
	if (aa->a<bb->a)
		return -1;
	if (aa->a>bb->a)
		return 1;
	return 0;
}
int main()
{
	FILE *in,*out;
	int n,c,i,j,k;
	in=fopen("carnati.in","r");
	out=fopen("carnati.out","w");
	fscanf(in,"%d%d",&n,&c);
	for (i=1;i<=n;i++)
	{
		fscanf(in,"%lld%lld",&a[i].a,&a[i].b);
	}
	qsort(a+1,n,sizeof(a[1]),compare);
	for (i=1;i<=n;i++)
	{
		for (k=1;k<=n;k++)
			b[k]=0;
		j=1;
		while (a[j].b<a[i].b)
		{
			b[j]=0;
			j++;
		}
		b[j]=a[i].b-c;
		if (b[j]>max)
			max=b[j];
		for (k=j+1;k<=n;k++)
		{	
			if (!b[k-1])
			{
				if (a[k].b<a[i].b)
					b[k]=0;
				else
					b[k]=a[i].b-c;
			}
			else
			{
			if (a[k].b<a[i].b) 
			{
				if (b[k-1]-c*(a[k].a-a[k-1].a)>0)
					b[k]=b[k-1]-c*(a[k].a-a[k-1].a);
				else
					b[k]=0;
			}
			else
				if (b[k-1]-c*(a[k].a-a[k-1].a)+a[i].b>a[i].b-c)
					b[k]=b[k-1]-c*(a[k].a-a[k-1].a)+a[i].b;
				else
					b[k]=a[i].b-c;
			if (b[k]>max)
				max=b[k];
			}
		}
	}
	fprintf(out,"%d",max);
	fclose(in);
	fclose(out);
	return 0;
	
}