Cod sursa(job #177592)

Utilizator katakunaCazacu Alexandru katakuna Data 13 aprilie 2008 12:48:46
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<stdio.h>

int maxf,max,a[10010],x,y,l,X,N,v[10010],c,nr,i,k,C,p,n;

struct carnati {int a,b;}s[10010],aux;


void sort(){

 for(i=2;i<=k;i++){
  c=i;
  p=c>>1;

     while((p)&&(s[c].a>s[p].a)){
     aux=s[c];
     s[c]=s[p];
     s[p]=aux;

     c=p;
     p=c>>1;

     }

  }


  for(i=k;i>1;i--){
  aux=s[i];
  s[i]=s[1];
  s[1]=aux;
  p=1;
  c=p<<1;

    k--;

      while(c<=k){
       if((s[c].a<s[c+1].a)&&c<k){c++;}

       if(s[p].a<s[c].a){
       aux=s[p];
       s[p]=s[c];
       s[c]=aux;
       p=c;
       c=p<<1;
       }
       else{break;}
     }
  }

}



int main(){


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

fscanf(f,"%d %d",&n,&C);

for(i=1;i<=n;i++){
fscanf(f,"%d %d",&s[i].a,&s[i].b);
}

fclose(f);

k=n;
sort();

/*
a[1]=s[1].b-C;

  for(i=2;i<=n;i++){
   x=a[i-1]-(s[i].a-s[i-1].a)*C  +s[i].b;
   y=s[i].b-C;

     if(x>y)
     a[i]=x;

     else
     a[i]=y;

  }

*/


//h[i]=s[1].i-s[]


  for(l=1;l<=n;l++){
  X=s[l].b;
  N=0;

    for(i=1;i<=n;i++)
     if(s[i].b>=X){
     N++;
     v[N]=i;
     }

  a[1]=X-C;
  max=-1000;

    for(i=2;i<=N;i++){
     x=a[i-1]-(s[v[i]].a-s[v[i-1]].a)*C+X;
     y=X-C;

     if(x>y)
     a[i]=x;

     else
     a[i]=y;

     if(a[i]>max)
     max=a[i];


    }



   if(max>maxf)
   maxf=max;

  }


FILE *g=fopen("carnati.out","w");
fprintf(g,"%d",maxf);
fclose(g);

return 0;
}