Cod sursa(job #491863)

Utilizator matei_cChristescu Matei matei_c Data 12 octombrie 2010 17:18:31
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<algorithm>
using namespace std;

ifstream in("carnati.in");
ofstream out("carnati.out");
struct client
{
	int t,p;
};
const int inf = 1<<30;
const int N=2010;
int n,c;
client v[N];

bool cmp(client x,client y)
{
	if(x.t<y.t)
		return true;
	return false;
}
int profit(int p)
{
	int sc=0,smax=-inf,u=-1,i;
	for(i=1;i<=n;i++)
	{
		if(v[i].p<p)
			continue;
		if(u!=-1 && sc-(v[i].t-u-1)*c>0)
			sc+=p-(v[i].t-u)*c;
		else
			sc=p-c;
		if(sc>smax)
			smax=sc;
		u=v[i].t;
	}	
	return smax;
}
int main()
{
	int smax = -inf;
	in>>n>>c;
	for(int i=1;i<=n;i++)
		in>>v[i].t>>v[i].p;
	sort(&v[1],&v[n+1],cmp);
	for(int i=1;i<=n;i++)
		if(profit(v[i].p)>smax)
			smax=profit(v[i].p);
	out<<smax<<"\n";
	return 0;
}