Cod sursa(job #145302)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 28 februarie 2008 18:26:50
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define nmax 2048
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define mp make_pair
#define f first
#define s second

int n,C,sol;
pair <int,int> P[nmax];

int f(int i,int j)
{
	return (P[i].s>=P[j].s)?P[j].s:0;
}

int main()
{
	freopen("carnati.in","r",stdin);
	freopen("carnati.out","w",stdout);
	int ii,i,j,a,b,aux;
	scanf("%d %d",&n,&C);
	FOR(ii,0,n)
	{
		scanf("%d %d",&a,&b);
		P[ii]=mp(a,b);
	}
	sort(P,P+n);
	FOR(i,0,n)
	{
		aux=f(0,i)-C;
		if(aux>sol) sol=aux;
		FOR(j,1,n)
		{
			aux-=(P[j].f-P[j-1].f-1)*C;
			if(aux<0) aux=0;
			aux+=f(j,i)-C;
			if(aux>sol) sol=aux;
		}
	}
	printf("%d\n",sol);
	return 0;
}