Pagini recente » Cod sursa (job #222685) | Cod sursa (job #2318068) | Cod sursa (job #805917) | Cod sursa (job #213327) | Cod sursa (job #140589)
Cod sursa(job #140589)
#include<stdio.h>
#define NMAX 101000
long long i,in,sf,j,a,poz,max,s,n,b,k,m,rez,y[NMAX];
struct deque
{
long long I,C;
};
deque q[NMAX],aux;
struct kkt
{
long long C,X;
};
kkt x[NMAX];
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld%lld%lld",&n,&s,&k);
for (i=1;i<=n;i++)
scanf("%lld%lld",&x[i].C,&x[i].X);
in=1;
sf=0;
for (i=1;i<=n;i++)
{
while ((in<=sf&&i-q[in].I>k))
in++;
while (in<=sf&&q[sf].C>x[i].C+(n-i)*s)
sf--;
q[++sf].C=x[i].C+(n-i)*s;
q[sf].I=i;
y[i]=q[in].C-(n-q[in].I)*s;
}
for (i=1;i<=n;i++)
{
q[i].C=y[i];
q[i].I=i;
}
a=1;
while (a)
{
a=0;
for (i=1;i<n;i++)
if ((q[i].C>q[i+1].C)||(q[i].C==q[i+1].C&&q[i].I>q[i+1].I))
{
a=1;
aux=q[i];
q[i]=q[i+1];
q[i+1]=aux;
}
}
for (i=1;i<=n;i++)
{
if (q[i].C==q[i+1].C)
{
a=0;
b=0;
j=i;
while (q[i].C==q[i+1].C)
{
a+=(x[q[i].I+1].X)*(q[i].I+1-q[j].I);
b+=x[q[i].I+1].X;
i++;
}
rez+=a*s;
rez+=(b+x[q[j].I].X)*x[q[j].I].C;
} else
rez+=q[i].C*x[q[i].I].X;
}
/* for (i=1;i<=n;i++)
{
if (y[i]==y[i+1])
{
a=0;
b=0;
j=i;
while (y[i]==y[i+1])
{
a+=(x[i+1].X)*(i+1-j);
b+=x[i+1].X;
i++;
}
rez+=a*s;
rez+=(b+x[j].X)*x[j].C;
} else
rez+=y[i]*x[i].X;
} */
printf("%lld\n",rez);
return 0;
}