Cod sursa(job #681509)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 februarie 2012 11:38:35
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
long long c,profitM=-564525154,n;
long long max( long long a, long long b)
{
	if (a<b)
		return b;
	return a;
}
struct v
{
	long long  o,p;
};
v A[2012];
long long  a[2012];
int cmp(v a, v b)
{
	if (a.o<b.o)
		return 1;
	return 0;
}
long long calcul (long long pret)
{
	  long long profi=-516561,i;
	if (pret<=A[1].p)
			a[1]=pret-c;
	else
		a[1]=0;
	
	for (i=2;i<=n;i++)
	{
		if (pret<=A[i].p)
			a[i]=max(a[i-1]-(A[i].o-A[i-1].o)*c+pret, pret-c);
		else
			a[i]=max(a[i-1]-(A[i].o-A[i-1].o)*c, 0);
		if (a[i]>profi)
			profi=a[i];
	}
	return profi;
}
int main(void)
{
	int i,m;
	fstream f,g;
	f.open("carnati.in",ios::in);
	g.open("carnati.out",ios::out);
	f>>n>>c;
	for (i=1;i<=n;i++)
		f>>A[i].o>>A[i].p;
	sort (A+1, A+1+n, cmp);
	/*for (i=1;i<=n;i++)
		g<<A[i].o<<" "<<A[i].p<<"\n";
	*/
	for (i=1;i<=n;i++)
	{
		long long pret=A[i].p;
		long long  profit=calcul(pret);
		if (profit>profitM)
			profitM=profit;
	}
	g<<profitM;
	//cout<<m;
}