Pagini recente » Cod sursa (job #3003371) | Cod sursa (job #2881468) | Cod sursa (job #774497) | Cod sursa (job #966139) | Cod sursa (job #80503)
Cod sursa(job #80503)
#include<stdio.h>
long long n,cant[100001],pret[100001],deque[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;
deque[cap]=pret[1];
cost[1]=pret[1]*cant[1];
for(i=2;i<=n;i++)
{
if (i>t+1)
{
el=pret[i-t-1];
if (el==deque[cap]) cap++;
while ((cant[i]*deque[coada]+(i-poz[coada])*s*cant[i])>pret[i]*cant[i])
coada--;
coada++;
deque[coada]=pret[i];
poz[coada]=i;
cost[i]=cant[i]*deque[cap]+(i-poz[cap])*s*cant[i];
}
else
{
while ((cant[i]*deque[coada]+(i-poz[coada])*s*cant[i])>(pret[i]*cant[i])&&coada>0)
coada--;
coada++;
deque[coada]=pret[i];
poz[coada]=i;
cost[i]=cant[i]*deque[cap]+(i-poz[cap])*s*cant[i];
}
}
s=0;
for(i=1;i<=n;i++)
s+=cost[i];
printf("%lld\n",s);
return 0;
}