Cod sursa(job #491841)

Utilizator mattapoMatei Apolzan mattapo Data 12 octombrie 2010 16:23:34
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<algorithm>

using namespace std;
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=-9999999,sc=0,u=-1,i;
	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 ()
{
	int i,sc,smax=-9999999;
	ifstream in("carnati.in");
	ofstream out("carnati.out");
	in>>n>>c;
	for (i=1;i<=n;i++)
	{
		in>>v[i].t>>v[i].p;
	}
	sort(&v[1],&v[n+1],cmp);
	for (i=1;i<=n;i++)
	{
		sc=pret(v[i].p);
		if (sc>smax)
			smax=sc;
	}
	out<<smax<<'\n';
	return 0;
}