Pagini recente » Cod sursa (job #786526) | Cod sursa (job #2517795) | Cod sursa (job #953660) | Cod sursa (job #239422) | Cod sursa (job #81532)
Cod sursa(job #81532)
#include<stdio.h>
long long n,cant[100001],pret[100001],s,t,cost[100001],poz[100001],el,i,cap,coada,aux;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld %lld %lld",&n,&s,&t);
for(i=1;i<=n;i++)
scanf("%lld %lld",&pret[i],&cant[i]);
cap=1;
coada=1;
poz[cap]=1;
pret[0]=1000000000;
cost[1]=pret[1]*cant[1];
for(i=2;i<=n;i++)
{
if (i>t+1)
{
el=i-t-1;
if (el==poz[cap]) {poz[cap]=0;cap++;}
while (((cant[i]*pret[poz[coada]]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i]))&&(coada>cap-1))
coada--;
coada++;
poz[coada]=i;
cost[i]=cant[i]*pret[poz[cap]]+(i-poz[cap])*s*cant[i];
}
else
{
while (((cant[i]*pret[poz[coada]]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i]))&&(coada>cap-1))
coada--;
coada++;
poz[coada]=i;
cost[i]=cant[i]*pret[poz[cap]]+(i-poz[cap])*s*cant[i];
}
}
s=0;
for(i=1;i<=n;i++)
s+=cost[i];
printf("%lld\n",s);
return 0;
}