Cod sursa(job #368538)

Utilizator liv182copoiu liviu liv182 Data 25 noiembrie 2009 10:30:25
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
struct carnat
{
	int t,p;
};
carnat v[1<<16];
int n,c;
int profmax(int p)
{
	int j,prof,prmax=0;
	if(v[1].p>=prof)
		prof=v[1].p-c;
	else
		prof=-c;
	prmax=prof;
	for(j=2;j<=n;++j)
	{
		prof-=c*(v[j].t-v[j-1].t-1);
		if(prof<0)
			prof=0;
		if(p<=v[j].p)
			prof+=p;
		prof-=c;
	    if(prof>prmax)
			prmax=prof;
	}
	return prmax;
}
bool comp(const carnat&x,const carnat&y)
{
	return x.t<y.t;
}
int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	int i,p,pmax=0;
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;++i)
	{
		scanf("%d%d",&v[i].t,&v[i].p);
	}
	sort(v+1,v+n+1,comp);
	for(i=1;i<=n;++i)
	{
		p=profmax(v[i].p);
		if(pmax<p) pmax=p;
	}
	printf("%d",pmax);	
	return 0;
}