Cod sursa(job #158613)

Utilizator swift90Ionut Bogdanescu swift90 Data 13 martie 2008 18:42:32
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
pair <int, int> nr[2010];
inline int max(int a,int b){
	return a>b?a:b;
}
int main(){
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	int n,c,maxim,i,j,sum,sf;
	
	scanf("%d%d",&n,&c);
	for(i=0;i<n;++i)
		scanf("%d%d",&nr[i].first,&nr[i].second);
	maxim=-1000000000;
	sort(nr,nr+n);
	for(i=0;i<n;++i){
		sum=0;
		if(nr[i].second<=nr[0].second){
			sum=nr[i].second-c;
			sf=nr[0].first;
		}
		else
			sf=nr[1].first-1;
		if(sum>maxim)
			maxim=sum;
		for(j=1;j<n;++j){
			if(nr[i].second<=nr[j].second)
				sum=max(sum+nr[i].second-(nr[j].first-sf)*c,nr[i].second-c);
			else
				sum=max(sum-(nr[j].first-sf)*c,-c);
			sf=nr[j].first;
			if(sum>maxim)
				maxim=sum;
		}
	}
	
	if(maxim<0)
		printf("0\n");
	else
		printf("%d\n",maxim);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}