Cod sursa(job #471399)

Utilizator robigiirimias robert robigi Data 18 iulie 2010 17:06:55
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
// Carnati.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"
#include "stdio.h"

FILE *f=fopen("carnati.in", "r");
FILE *g=fopen("carnati.out", "w");

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

void read()
{
	fscanf(f, "%d%d", &n, &c);
	for (int i=1; i<=n; i++)
		fscanf(f, "%d%d", &a[i][0], &a[i][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;
		int p=a[i][1];
		for (int j=1; j<=n; j++)
		{
			int cv=0;
			if (a[j][1]<p)
			{
				cv=p;
				p=0;
			}
			sum=maxim(sum-(a[j][0]-a[j-1][0])*c+p, p-c);
			if (sum>max) max=sum;
			if (p==0)
				p=cv;
		}
	}
	fprintf(g, "%d", max);
}



int main()
{
	read();
	quicksort(1, n);
	program();
	return 0;
}