Cod sursa(job #206584)

Utilizator devilkindSavin Tiberiu devilkind Data 7 septembrie 2008 21:24:05
Problema Carnati Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 2048
#define pb push_back
#define sz size()
#define mp make_pair
#define ff first
#define ss second

int N,C;
vector< pair<int,int> > v;
vector<int> a;
int din[NMAX];

int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);

	int i,j,x,y,sol;

	scanf("%d %d",&N,&C);

	for (i=1;i<=N;i++){
		scanf("%d %d",&x,&y);
		v.pb( mp(x,y) );
	}

	sort(v.begin(), v.end() );
	C=-C;

	for (i=0;i<N;i++){
		a.clear();
		memset(din,0,sizeof(din));
		
		for (j=0;j<N;j++)
			if (v[j].ss>=v[i].ss) a.pb(v[j].ff);

		din[0]=v[i].ss+C;
                sol=max(sol,din[0]);
                
		for (j=1;j<a.sz;j++){
				din[j]=max( (a[j] - a[j-1] )*C + v[i].ss + din[j-1], v[i].ss+C );
				sol=max(sol,din[j]);
			}
	}
	printf("%d\n",sol);
	return 0;
}