Cod sursa(job #458244)

Utilizator hendrikHendrik Lai hendrik Data 24 mai 2010 08:06:52
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for (int i=(a);i<=(b);i++)
#define FORD(i,b,a) for (int i=(b);i>=(a);i--)
#define MAXN 2010
#define x first
#define y second
typedef pair<int,int>pii;
int n,c,A[MAXN],m[MAXN],ans,p1;
pii p[MAXN];
bool used[MAXN];

void open(){
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
}

int main(){
	open();
	scanf("%d%d",&n,&c);
	REP(i,n){
		scanf("%d%d",&p[i].x,&p[i].y);
	}
	sort(p,p+n);
	REP(i,n){
		int G=p[i].y;
		A[0]=((p[i].y<=p[0].y)?p[i].y:0)-c;
		ans=max(ans,A[0]);
		FOR(j,1,n-1){
			A[j]=max(A[j-1]-c*(p[j].x-p[j-1].x)+((p[i].y<=p[j].y)?p[i].y:0),((p[i].y<=p[j].y)?p[i].y:0)-c);
			ans=max(ans,A[j]);
		}
	}
	printf("%d\n",ans);
	//system("pause");
	return 0;
}