Cod sursa(job #491822)

Utilizator PavelPavel Ana-Oriana Pavel Data 12 octombrie 2010 16:03:36
Problema Carnati Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<fstream>

using namespace std;

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

struct client 
{
	int t,p; 
};

client v[2001];
int n,c;

bool cmp(client x,client y)
{
	if(x.t<y.t)
		return true;
	return false;
}
int pret(int pr)
{
	long smax=-1000000000,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()
{
	int i,sc,smax=-100000000;
	in>>n>>c;
	for(i=1;i<=n;i++)
		in>>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;
	}
	out<<smax<<'\n';
	return 0;
}