Cod sursa(job #209198)

Utilizator katakunaCazacu Alexandru katakuna Data 21 septembrie 2008 12:37:04
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<stdio.h>


struct branza {long long c,p;} b[100011];
long long ok,i,n,m,s,t,aux,N,M[100011],P[100011];
long long h[100011];

void up(long long poz){
long long c,p;
c=poz;
p=poz>>1;

  while( (h[c] < h[p]) && c!=1 ){
  aux=h[c];
  h[c]=h[p];
  h[p]=aux;

  aux=P[P[c]];
  P[P[c]]=P[P[p]];
  P[P[p]]=aux;

  c=p;
  p=c>>1;
  }
  
}


void down(long long poz){
long long p,c;
p=poz;
c=p<<1;

   while(c<=N){

     if(h[c] > h[c+1] && c<N )
     c++;


     if(h[p] > h[c]){
     aux=h[c];
     h[c]=h[p];
     h[p]=aux;

     aux=P[P[c]];
     P[P[c]]=P[P[p]];
     P[P[p]]=aux;

     p=c;
     c=p<<1;
     }

     else
     break;



   }


}


int main(){

FILE *f=fopen("branza.in","r");
fscanf(f,"%lld %lld %lld",&n,&s,&t);

  for(i=1;i<=n;i++){
  fscanf(f,"%lld %lld",&b[i].c,&b[i].p);
  P[i]=i;
  }
  
fclose(f);

t++;

h[1]=b[1].c+s*(n-1);
N=1;
M[1]=b[1].c;

  for(i=2;i<=t;i++){

  N++;
  h[N]=b[i].c+s*(n-i);
  up(N);
  M[i]=h[1]-(s*(n-i));
  }

long long q=1;

    for(i=t+1;i<=n;i++,q++){
    M[i]=b[i].c;
    //inlocuim elem de pe pozitia q din sir care se afla pe poz P[q] in heap

     if( h[P[q]]<b[i].c+s*(n-i))
     //cobor
     ok=1;
     else
     ok=0;


       h[P[q]]=b[i].c+s*(n-i);

        if(ok==1)
        down(P[q]);

        if(ok==0)
        up(P[q]);

    M[i]=h[1]-(s*(n-i));
        
    }

long long sol=0;

    for(i=1;i<=n;i++)
    sol+=(b[i].p*M[i]);

FILE *g=fopen("branza.out","w");
fprintf(g,"%lld",sol);
fclose(g);

return 0;
}