Cod sursa(job #682809)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 19 februarie 2012 16:05:59
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <fstream>
#include <algorithm>
#define MULT 999999
#define DN 2005
#define x first
#define y second
using namespace std;

typedef pair<int, int> PER;

PER v[DN];
int n,c,sol=-MULT;
/*
void cit(int n,int a[])
{
	if(n)
	{
		cit(n-1,a);
		f>>a[n]>>" ";
	}
}
*/
int calc(int pret) {
	int smax=-MULT,sc=0,ut=-1;
	for(int i=1; i<=n; ++i) {
		if(v[i].y<pret) continue;
		if(-1!=ut && sc>(v[i].x-ut-1)*c) sc+=pret-c*(v[i].x-ut);
		else sc=pret-c;
		smax=max(smax,sc);
		ut=v[i].x;
	}
	return smax;
}

int main()
{
	ifstream f("carnati.in");
	ofstream g("carnati.out");
	f>>n>>c;
	for(int i=1; i<=n; ++i) f>>v[i].x>>v[i].y;
	sort(v+1,v+n+1);
	for(int i=1; i<=n; ++i) {
		int pc=calc(v[i].y);
		sol=max(sol,pc);
	}
	g<<sol;
	return 0;
}