Pagini recente » Cod sursa (job #3243160) | Cod sursa (job #623757) | Cod sursa (job #1588179) | Cod sursa (job #2489542) | Cod sursa (job #1027292)
#include<cstdio>
long long v[100001],c[100001],dq[100001],st=1,dr,t,s;
int dreapta(int i)
{
long long min=v[i];
int j=dr-1,u=i;
while(st<=j)
{
if(v[dq[j]]+(i-dq[j])*s<=min)
{
min=v[dq[j]];
u=dq[j];
}
--j;
}
return u;
}
inline void stanga(int i)
{
if(i-dq[st]==t)
++st;
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
int n,i,x;
long long sum=0;
scanf("%d%d%d",&n,&s,&t);
for(i=1;i<=n;++i)
scanf("%lld%lld",&v[i],&c[i]);
dq[++dr]=1;
for(i=2;i<=n;++i)
{
stanga(i);
dq[++dr]=dreapta(i);
}
for(i=1;i<=n;++i)
sum+=v[dq[i]]*c[i]+s*(i-dq[i])*c[i];
printf("%lld",sum);
return 0;
}