Cod sursa(job #749377)

Utilizator GrimpowRadu Andrei Grimpow Data 16 mai 2012 20:24:50
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include<fstream>
using namespace std;
ifstream f1 ("carnati.in");
ofstream f2 ("carnati.out");
struct carn {int p,t;};
carn a[2005];
struct cmp
{
	bool operator()(const carn &a, const carn &b)const
	{
		return a.t < b.t;
	}
};
int main()
{
	int i,j,n,c,ax,b,maxx=0,G;
	f1>>n>>c;
	for (i=1; i<=n; i++) f1>>a[i].t>>a[i].p;
	sort(a+1,a+n+1,cmp());
	a[0].t=a[0].p=-10;
	for(i=1;i<=n;++i)  
	{  
		if (a[0].p>=a[i].p)  ax=a[i].p-c;
		else ax=0;  
		maxx=max(maxx,ax);
		for(j=1;j<=n;++j)  
		{  
			if(a[ j ].p>=a[ i ].p) G=a[ i ].p;  
				else G=0;  
			b=max( (ax-(a[ j ].t-a[ j-1 ].t)*c+G), G-c); 
			maxx=max(maxx,b);  
			ax=b;  
		}  
	}
	f2<<maxx;
	return 0;
}