Cod sursa(job #183515)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 22 aprilie 2008 12:20:30
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct ab{
	int a,b;
};
ab v[2001];
int best[2001];
int comp(const ab &a,const ab &b){
	if(a.a<b.a) return 1;
	return 0;
}
int maxim(int x, int y){
	if(x>y) return x;
	return y;
}
int main(){
	int i,n,c,j,poz,max=0,s1,s2;
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;i++)
		scanf("%d%d",&v[i].a,&v[i].b);
	v[0].a=v[0].b=-1;
	sort(v+1,v+n+1,comp);
	for(i=1;i<=n;i++){
		s1=s2=0;
		for(j=1;j<=n;j++){
			if(v[j].b>=v[i].b) s1=maxim(s2-(v[j].a-v[j-1].a)*c+v[i].b,v[i].b-c);
			else s1=maxim(s2-(v[j].a-v[j-1].a)*c,-c);
			if(s1>max) max=s1;
			s2=s1;
		}
	}
	printf("%d",max);
}