Pagini recente » Cod sursa (job #1388217) | Cod sursa (job #3041829) | Cod sursa (job #870618) | Cod sursa (job #828894) | Cod sursa (job #113239)
Cod sursa(job #113239)
#include<stdio.h>
struct coada{
int pret,poz;
};
coada nr[100010];
long long suma;
int main(){
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
int n,s,t,i,inc,sf,cost,cant;
int pr,ul,mij;
scanf("%d%d%d",&n,&s,&t);
scanf("%d%d",&cost,&cant);
suma=cant*cost;
inc=sf=0;
nr[0].pret=cost;
nr[0].poz=0;
for(i=1;i<n;++i){
scanf("%d%d",&cost,&cant);
if(nr[inc].poz+t<i)
++inc;
pr=inc;
ul=sf;
while(pr!=ul){
mij=(pr+ul)>>1;
if(nr[mij].pret+(i-nr[mij].poz)*s>cost)
ul=mij;
else
pr=mij+1;
}
if(nr[pr].pret+(i-nr[pr].poz)*s<cost)
++pr;
nr[pr].pret=cost;
nr[pr].poz=i;
sf=pr;
suma+=cant*(nr[inc].pret+s*(i-nr[inc].poz));
}
printf("%lld\n",suma);
fclose(stdin);
fclose(stdout);
return 0;
}