Cod sursa(job #681537)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 17 februarie 2012 12:10:43
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int c,profitM=-564525154,n;
struct v
{
	int  o,p;
};
v A[2012];
int  a[2012];
int cmp(v a, v b)
{
	if (a.o<b.o)
		return 1;
	return 0;
}
int calcul ( int pret)
{
	int profi=-5,i;
	if (pret<=A[1].p)
		if(pret>c)
			a[1]=pret-c;
		else
			a[1]=0;
	else
		a[1]=0;
	if (a[1]>profi)
			profi=a[1];
	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;
	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++)
	{
		int pret=A[i].p;
		int   profit=calcul(pret);
		if (profit>profitM)
			profitM=profit;
	}
	g<<profitM;
	//cout<<m;
}