Cod sursa(job #286565)

Utilizator vladbBogolin Vlad vladb Data 23 martie 2009 21:58:08
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>

using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

long n,c,g,d,maxim,s;
struct client { long t,p;
              } a[2001];

void quick(int x,int y)
{    	int i,j,p;
     client aux;
	if(x<y)
	{	i=x-1;
		j=y+1;
		p=a[(x+y)/2].t;
		while(i<j)
		{	do i++; while(a[i].t<p);
			do j--; while(a[j].t>p);
			if(i<j) {  aux=a[i];
				   a[i]=a[j];
				   a[j]=aux;
				}
		}
		quick(x,i-1);
		quick(j+1,y);
	}
}

int main()
{   long i,j;
     fin>>n>>c;
     for(i=1;i<=n;i++)
         fin>>a[i].t>>a[i].p;
     quick(1,n);
     for(i=1;i<=n;i++)
     {   s=0;
         for(j=1;j<=n;j++)
         {   if(a[j].p>=a[i].p) g=a[i].p;
               else g=0;
              d=s-(a[j].t-a[j-1].t)*c+g;
              if(d<g-c) d=g-c;
              if(maxim<d) maxim=d;
              s=d;
         }
     }
     fout<<maxim;
     fin.close();
     fout.close();
     return 0;
}