Pagini recente » Cod sursa (job #1023066) | Cod sursa (job #1864418) | Cod sursa (job #1856336) | Cod sursa (job #761506) | Cod sursa (job #382197)
Cod sursa(job #382197)
#include<stdio.h>
int dq[1<<17],st=1,dr=0,t,s,n;
int cost[1<<17],kg[1<<17];
long long sum=0;
inline void stanga (int i)
{
if(i-dq[st]==t)
++st;
}
void dreapta(int i)
{
while(st<=dr && cost[i]<=cost[dq[dr]]+s*(i-dq[dr]))
--dr;
dq[++dr]=i;
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
++t;
for(int i=1;i<=n;++i)
scanf("%d%d",&cost[i],&kg[i]);
for(int i=1;i<t;++i)
{
dreapta(i);
sum=sum+(long long)(cost[dq[st]]+s*(i-dq[st]))*(long long)kg[i];
}
for(int i=t;i<=n;++i)
{
stanga(i);
dreapta(i);
sum=sum+(long long)(cost[dq[st]]+s*(i-dq[st]))*(long long)kg[i];
}
printf("%lld",sum);
return 0;
}