Pagini recente » Clasament sadags | Cod sursa (job #1090336) | Cod sursa (job #1040212) | Cod sursa (job #846933) | Cod sursa (job #380481)
Cod sursa(job #380481)
#include<cstdio>
long long s,k,n,st,dr,v[1000010],dq[100010],c[100010];
long long nr;
inline void stanga (int i)
{
if(i-dq[st]==k)
++st;
}
void dreapta(int i)
{
while(st<=dr&&v[dq[dr]]+(i-dq[dr])*s>=v[i])
--dr;
dq[++dr]=i;
}
int main()
{
int i;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld%lld%lld",&n,&s,&k);
k++;
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i],&c[i]);
dr=1;
st=1;
dq[1]=1;
nr=v[1]*c[1];
for(i=2;i<=n;i++)
{
stanga(i);
dreapta(i);
nr=nr+(v[dq[st]]+(i-dq[st])*s)*c[i];
}
printf("%lld",nr);
return 0;
}