Cod sursa(job #490854)

Utilizator tudor0013tudor petrescu tudor0013 Data 8 octombrie 2010 15:58:37
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
#include<algorithm>

using namespace std;

const int N = 2001;
const int inf = 1000000000;

struct client
{
	int t,p;
};

client v[N];
long n,c,sal;

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

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

bool comp(client x, client y)
{
	return x.t < y.t;
}

int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	in>>n>>c;
	sal=c;
	for(int i=1;i<=n;i++)
		in>>v[i].t>>v[i].p;
	sort(&v[1],&v[1+n],comp);
	long max=-inf,x;
	for(int i=1;i<=n;i++)
	{
		x=val(v[i].p);
		if(x>max)
			max=x;
	}
	out<<max;
	return 0;
}