Cod sursa(job #532242)

Utilizator S7012MYPetru Trimbitas S7012MY Data 11 februarie 2011 10:42:01
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MULT 9999999
#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;

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;
}