Pagini recente » Cod sursa (job #1085673) | Cod sursa (job #2362887) | Cod sursa (job #1959545) | Clasament summer_challenge_intarziat | Cod sursa (job #385627)
Cod sursa(job #385627)
#include<cstdio>
const int N=1<<20;
long long k;
long long dq[N];
long long s;
long long st,dr;
long long x[N],y[N];
void inline stanga(long long i)
{
if (i-dq[st]>k)
++st;
}
void dreapta(long long i)
{
while( st<=dr && (x[i]<x[dq[dr]]+s*(i-dq[dr])) )
--dr;
dq[++dr]=i;
}
int main()
{
long long sum=0,n,i;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld%lld%lld",&n,&s,&k);
st=1;
for (i=1;i<=n;++i)
{
scanf("%lld%lld",&x[i],&y[i]);
stanga(i);
dreapta(i);
sum+=x[dq[st]]*y[i]+(i-dq[st])*s*y[i];
}
printf("%lld",sum);
return 0;
}