Cod sursa(job #495955)

Utilizator mihai995mihai995 mihai995 Data 27 octombrie 2010 12:33:22
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
using namespace std;

struct client{int ora,bani;} v[1<<11];
int n,c,maxim;

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

bool cmp(client a,client b)
{
	return a.ora<b.ora || a.ora==b.ora && a.ora<b.ora;
}

int main()
{
	int i,p,j,st;
	in>>n>>c;
	for (i=1;i<=n;i++)
		in>>v[i].ora>>v[i].bani;
	sort(v+1,v+n+1,cmp);
	maxim=0;
	for (i=1;i<=n;i++)
	{
		for (j=1;v[i].bani>v[j].bani;j++);
		st=j;p=1;
		for (j=st+1;j<=n;j++)
		{
			if (v[i].bani>v[j].bani)
				continue;
			if (p*v[i].bani<(v[j].ora-v[st].ora+1)*c)
			{
				p=0;
				st=j;
			}
			p++;
			if (p*v[i].bani-(v[j].ora-v[st].ora+1)*c>maxim)
				maxim=p*v[i].bani-(v[j].ora-v[st].ora+1)*c;
		}
	}
	out<<maxim<<"\n";
	return 0;
}