Pagini recente » Cod sursa (job #557627) | Cod sursa (job #1583925) | Cod sursa (job #2254529) | Cod sursa (job #1587837) | Cod sursa (job #462016)
Cod sursa(job #462016)
#include <cstdio>
int n,s,t,p[1<<17],c[1<<17],dq[1<<17],st=1,dr=0;
long long sum;
void citire()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%d%d",&n,&s,&t);
for(int i=1;i<=n;++i)
scanf("%d%d",c+i,p+i);
++t;
}
inline void stanga(int i)
{
if(dq[st]==i-t)
++st;
}
void dreapta(int i)
{
while(st<=dr && c[i]<=c[dq[dr]] + (long long)s * (i-dq[dr]))
--dr;
dq[++dr]=i;
sum+=(c[dq[st]]+(long long)s * (i - dq[st]))*p[i];
}
void work()
{
for(int i=1;i<=n;++i)
{
stanga(i);
dreapta(i);
}
printf("%lld",sum);
}
int main()
{
citire();
work();
return 0;
}