Cod sursa(job #209476)

Utilizator katakunaCazacu Alexandru katakuna Data 22 septembrie 2008 18:15:34
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

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

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

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

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

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

}

void down(long long poz){
int c,p;
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[p]]=P[P[p]];
        P[P[p]]=aux;

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

        else
        break;

     }

}


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);
N=1;
m[1]=b[1].c;
h[1]=b[1].c + s*(n-1);

long long R;

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

     if(i-(t+1) > 0){
     R=b[i].c + s*(n-i);

        if(R > h[P[i-(t+1) ]]){
        h[P[i-(t+1) ]]=R;
        down(P[i-(t+1) ]);
        }
        else{
        h[P[i-(t+1) ]]=R;
        up(P[i-(t+1) ]);
        }

     }

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

   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,"%d",sol);
fclose(g);

return 0;
}