Cod sursa(job #491862)

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

ifstream in("carnati.in");
ofstream out("carnati.out");
struct client
{
	int t,p;
};	
const int N=2010;
int n,c,i,smax=-100000000;
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=-100000000,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()
{
	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=2;i<=n;i++)
		if(profit(v[i].p)>profit(v[i-1].p))
			smax=profit(v[i].p);
	out<<smax<<endl;
	return 0;	
}