Cod sursa(job #368661)

Utilizator DeadEyeNaiba Mihai Lucian DeadEye Data 25 noiembrie 2009 12:28:30
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,c,i,j,p1,p3,p1max,ptreads,maxim,zz;
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; a[0].y=0; p1max=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=0;
				//p2=0;
				p3=0;
			}
			if(p3>maxim)
			{
				maxim=p3;
				p1max=p1;
			}
		}
	}
	if(maxim-c<0)
		printf("%d\n",maxim);
	else
	{
		zz=maxim-c;
		if(zz+a[p1max-1].y-c*(a[p1max].y-a[p1max-1].y)>zz)
			zz=zz+a[p1max-1].y-c*(a[p1max].y-a[p1max-1].y);
		printf("%d\n",zz);
	}
	return 0;
}