Pagini recente » Cod sursa (job #1080344) | Cod sursa (job #1783292) | Cod sursa (job #1643271) | Cod sursa (job #814407) | Cod sursa (job #497243)
Cod sursa(job #497243)
#include <cstdio>
#define nmax 100010
int c[nmax], p[nmax], v[nmax], q[nmax], n, s, t;
long long sol;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
int i, st, dr, j;
for (i=1; i<=n; i++) scanf("%d %d",&c[i],&p[i]);
st=1;
dr=0;
for (i=1; i<=n; i++)
{
while (st<=dr && c[i]+(n-i)*s<c[q[dr]]+(n-q[dr])*s)
dr--;
while (q[st]+t<i && st<=dr) st++;
q[++dr]=i;
v[i]=c[q[st]]+(i-q[st])*s;
}
for (i=1; i<=n; i++) sol+=(long long) p[i]*v[i];
printf("%lld\n",sol);
}