Cod sursa(job #471414)

Utilizator robigiirimias robert robigi Data 18 iulie 2010 18:16:53
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
// Carnati.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "cstdio"

int n, c;
int a[2001][2];
int max=-10000000;

void read()
{
	freopen("carnati.in", "r", stdin);
	scanf("%d%d",&n,&c); 
	for (int i=1; i<=n; i++)
		scanf("%d%d", &a[i][0], &a[i][1]);
	a[0][0]=a[0][1]=-1;
}


void quicksort(int low, int high)
{
	int i=low, j=high, x=a[(low+high)/2][0];
	int h;
	do
	{
		while (a[i][0]<x) i++;
		while (a[j][0]>x) j--;
		if (i<=j)
		{
			h=a[i][0]; a[i][0]=a[j][0]; a[j][0]=h;
			h=a[i][1]; a[i][1]=a[j][1]; a[j][1]=h;
			i++; j--;
		}
	}while (i<=j);
	if (i<high) quicksort(i, high);
	if (j>low) quicksort(low, j);
}



int maxim(int x, int y)
{
	if (x>y) return x;
	return y;
}


void program()
{
	int sum=0;
	for (int i=1; i<=n; i++)
	{
		sum=0;
		for (int j=1; j<=n; j++)
		{
			int p=a[i][1];
			if (a[j][1]<p)
			{
				p=0;
			}
			sum=maxim(sum-(a[j][0]-a[j-1][0])*c+p, p-c);
			if (sum>max) max=sum;
		}
	}
}



int main()
{
	read();
	quicksort(1, n);
	program();
	freopen("carnati.out","w",stdout);
	if (max>0)
		printf( "%d", max);
	else printf( "%d", 0);
	return 0;
}