Pagini recente » Cod sursa (job #1540777) | Cod sursa (job #244265) | Cod sursa (job #1902398) | Cod sursa (job #335146) | Cod sursa (job #462011)
Cod sursa(job #462011)
#include <cstdio>
int n,s,t,p[1<<17],c[1<<17],dq[1<<17],sum=0,st=1,dr=0;
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);
}
inline void stanga(int i)
{
if(dq[st]==i-t)
++st;
}
void dreapta(int i)
{
while(st<=dr && c[i]<=c[dq[dr]] + s * (i-dq[dr]))
--dr;
dq[++dr]=i;
sum+=(c[dq[st]]+s * (i - dq[st]))*p[i];
}
void work()
{
for(int i=1;i<=n;++i)
{
stanga(i);
dreapta(i);
}
printf("%d",sum);
}
int main()
{
citire();
work();
return 0;
}