Cod sursa(job #206581)

Utilizator devilkindSavin Tiberiu devilkind Data 7 septembrie 2008 21:14:53
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 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,a; 
int din[NMAX];

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

	int i,j,x,y;

	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() );

	int sol=0;
	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]);

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