Cod sursa(job #491830)

Utilizator theocmtAxenie Theodor theocmt Data 12 octombrie 2010 16:06:03
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
/*#include<fstream>

using namespace std;

ifstream in("ssm.in");
ofstream out("ssm.out");

int main()
{
	long i,n,x,sc=0,smax=-1000000,p1=1,p2=1,p=1;
	in>>n;
	for (i=1; i<=n; i++)
	{
		in>>x;
		sc+=x;
		if (sc>smax)
		{
			p1=p;
			p2=i;
			smax=sc;
		}
		if (sc<0)
		{
			sc=0;
			p=i+1;
		}
	}
	out<<smax<<" "<<p1<<" "<<p2;
}
*/ 
/*#include<fstream>

using namespace std;

ifstream f("carnati.in");
ofstream g("carnati.out");

int main()
{
	long i,n,s,t,p,p1=1,p2=1,p3=1,smax=-10000000,sc=0;
	f>>n>>s;
	for (i=1;i<+n;i++)
	{
		f>>t>>p;
		sc+=p;
		if (sc-s*(t-p3+1)>smax)
		{
			smax=sc-s*(t-p1+1);
			p1=p3;
			p2=t;
		}
		if (sc<0)
		{
			sc=0;
			p3=t;
		} 
	}
	g<<smax;
}
*/
#include<fstream>

using namespace std;

ifstream f("carnati.in");
ofstream g("carnati.out");

struct client
{
	int t,p;
};	

int n,c;
client v[2001];

bool cmp(client x, client y)
{
	if(x.t<y.t)
		return true;
	return false;
}

int pret( int pr)
{
	long smax=-1000000,sc=0,i,u=-1;
	for (i=1; i<=n; i++)
	{
		if (v[i].p<pr)
			continue;
		if ((u!=-1) && (sc-(v[i].t-u-1)*c>0))
			sc+=pr-(v[i].t-u)*c;
		else 
			sc=pr-c;
		if (sc>smax)
			smax=sc;
		u=v[i].t;
	}
	return smax;
}

int main()
{
	long i,smax=-1000000,sc=0;
	f>>n>>c;
	for (i=1; i<=n; i++)
		f>>v[i].t>>v[i].p;
	sort(&v[i],&v[n+1],cmp);
	for (i=1; i<=n; i++)
	{
		sc=pret(v[i].p);
		if (sc>smax)
			smax=sc;
	}
	g<<smax;
}