Cod sursa(job #328730)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 3 iulie 2009 11:19:30
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#define Nmax 2005

struct om{
	long t,p;
};
om a[Nmax];
long best[Nmax];
long n,i,j,c,rez;

long MAX(long x,long y){
	return x > y ? x : y;
}

void incearca(long pfix){
	long i;
   if (a[1].p>=pfix)best[1]=pfix-c;  else best[1]=0;
   for(i=2;i<=n;++i){
      if(a[i].p>=pfix)
        best[i]=MAX(pfix-c,best[i-1] -  (a[i].t-a[i-1].t)*c + pfix);
      else best[i]=best[i-1] - (a[i].t-a[i-1].t)*c;
      if(best[i] > rez) rez=best[i];
   }
}

void sort(long l,long r){
	long i,j,x,y;
   i=l; j=r; x=a[l+(r-l)/2].t;
   do{
   	while(a[i].t < x) i++;
      while(x < a[j].t) j--;
      if(i<=j){
      	y=a[i].t; a[i].t=a[j].t; a[j].t=y;
      	y=a[i].p; a[i].p=a[j].p; a[j].p=y;
         ++i; --j;
      }
   } while(i<=j);
   if(i<r) sort(i,r);
   if(l<j) sort(l,j);
}

int main(){
	freopen("carnati.in","r",stdin);
   freopen("carnati.out","w",stdout);
   scanf("%ld%ld",&n,&c);
   for(i=1;i<=n;++i) scanf("%ld%ld",&a[i].t,&a[i].p);

   sort(1,n);
 //  a[0].t=best[0]=-10;
   for(i=1;i<=n;++i)
     incearca(a[i].p);

   if(rez>0)printf("%ld\n",rez);
   else printf("0\n");
   fclose(stdin); fclose(stdout);
   return 0;
}