Cod sursa(job #497751)

Utilizator mihai995mihai995 mihai995 Data 3 noiembrie 2010 11:27:17
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <fstream>
using namespace std;

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

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

inline int profit(om a,om b,int x)
{
	return  x-(b.ora-a.ora+1)*c;
}

bool cmp(om a,om b)
{
	return a.ora<b.ora;
}

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