Cod sursa(job #174485)

Utilizator laurpoppopescu laurentiu laurpop Data 8 aprilie 2008 21:35:52
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
 #include<stdio.h>
long long m[100001],c[100001],cd[2][100001],u,i,j,n,k,l,p,s,t,nr[100001],x[100001];
FILE *in,*out;

int main(){
in=fopen("branza.in","rt");
out=fopen("branza.out","wt");
fscanf(in,"%lld%lld%lld%lld%lld",&n,&s,&t,&c[1],&nr[1]);x[1]=nr[1];

for(i=2;i<=n;i++){
 fscanf(in,"%lld%lld",&c[i],&nr[i]);
   x[i]=x[i-1]+nr[i];
  }
p=u=cd[1][1]=1;cd[0][1]=c[1]+(n-1)*s;m[1]=1;
 for(i=2;i<=n;i++){
  while (i-cd[1][p]>=t)p++;
// p+=(i-cd[1][p]>=t);
 l=c[i]+(n-i)*s;
 if (l<=cd[0][p]){ m[i]=i;l=c[i];}
 else
   m[i]=cd[1][p];
  while((u-p+1)&&cd[0][u]>=l)
   u--;
 cd[1][++u]=i;cd[0][u]=l;
// m[i]=cd[1][p];
}
fclose(in);
l=0;
for(i=1;i<=n;i++)
 l+=c[m[i]]*nr[i]+(i-m[i])*s*nr[i];
fprintf(out,"%lld",l);
fclose(out);
return 0;
}