Cod sursa(job #209188)

Utilizator katakunaCazacu Alexandru katakuna Data 21 septembrie 2008 11:59:38
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include<stdio.h>
#define INF 1000000

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

void up(int poz){
int 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(int poz){
int p,c,c1,c2;
p=poz;
c1=p<<1;
c2=c1+1;

  if( h[c2]<h[c1]  && c2<=N ){
  c=c2;
  }
  
  else
  c=c1;

      while( h[p]>h[c]  && (c<=N) ){
      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;

      c1=p<<1;
      c2=c1+1;

      if( h[c2]<h[c1]  && c2<=N ){
      c=c2;
      }
  
       else
       c=c1;


      }


}


int main(){

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

  for(i=1;i<=n;i++){
  fscanf(f,"%d %d",&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++){
  M[i]=b[i].c;

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

int 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));
        
    }

int sol=0;

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

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

return 0;
}