Cod sursa(job #209507)

Utilizator katakunaCazacu Alexandru katakuna Data 22 septembrie 2008 21:39:53
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.94 kb
#include<stdio.h>   

struct branza {long long c,p;} b[100011];   
long long p2[100011],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[c];
  P[c]=P[p];
  P[p]=aux;

  p2[P[c]]=c;
  p2[P[p]]=p;
  
  
  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[c];
     P[c]=P[p];
     P[p]=aux;

     p2[P[c]]=c;
     p2[P[p]]=p;

     
     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;   
  p2[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[p2[q]]<b[i].c+s*(n-i))
     ok=1;
     else  
     ok=0;   
  
  
       h[p2[q]]=b[i].c+s*(n-i);

       P[p2[q]]=i;
       p2[i]=p2[q];

        if(ok==1)   
        down(p2[i]);
  
        if(ok==0)   
        up(p2[i]);
  
    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;   
}