Cod sursa(job #497780)

Utilizator mihai995mihai995 mihai995 Data 3 noiembrie 2010 11:54:39
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 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 cost(om a,om b)
{
	return  (b.ora-a.ora+1)*c;
}

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

int main()
{
	int i,j,maxim=0,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;
			
			if (cost(v[st],v[j])>nr)
			{
				st=j;
				nr=0;
			}
			nr+=x;
			maxim=max(maxim,nr-cost(v[st],v[j]));
		}
	}
	out<<maxim<<"\n";
	return 0;
}