Cod sursa(job #368638)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 25 noiembrie 2009 11:57:53
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,c,i,j,p1,p3,ptreads,maxim;
struct omg
{
	int x,y;
};
omg a[2002];
bool comp(const omg &a, const omg &b)
{
	if(a.x>b.x) return false;
	return true;
}
int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;++i)
	{
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	sort(a+1,a+n+1,comp); // I has a bucket
	maxim=0;
	a[n+1].y=0;
	for(i=1;i<=n;++i)
	{
		ptreads=a[i].y;
		p1=0; //p2=0; p3=0;
		for(j=1;j<=n;++j)
		{
			if(a[j].y>=ptreads)
			{
				if(p1==0)
				{
					p1=j;
					//p2=j;
					p3=ptreads;
				}
				else
				{
					//p2=j;
					p3=p3+ptreads-c*(a[j].x-a[j-1].x);
				}
			}
			else p3-=c*(a[j].x-a[j-1].x);
			if(p3<0)
			{
				//NOOOOO THEY BE STEALIN' MAH BUCKET
				p1=1;
				//p2=0;
				p3=a[j].y;
			}
			if(p3>maxim)
				maxim=p3;
		}
	}
	if(maxim-c<0)
		printf("%d\n",maxim);
	else printf("%d\n",maxim-c);
	return 0;
}