Pagini recente » Istoria paginii runda/savedemdecesunteminstare | Cod sursa (job #2014811) | Cod sursa (job #608435) | Cod sursa (job #739839) | Cod sursa (job #203983)
Cod sursa(job #203983)
#include <stdio.h>
#define N 100005
int c[N],p=1,n,t;
long long s;
struct ab{
long long a,b;
};
ab v[N];
int caut(long long x,int k){
int st=p,dr=c[0],m;
while(st<dr){
m=(st+dr)>>1;
if(v[c[m]].a+(k-c[m])*s>=x) dr=m;
else st=m+1;
}
if(v[c[st]].a+(k-c[st])*s<x) st++;
return st;
}
int main(){
int i,z;
long long total=0;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%lld%d",&n,&s,&t);
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i].a,&v[i].b);
c[1]=c[0]=1;
total=v[1].a*v[1].b;
/*for(i=2;i<=min;i++){
z=caut(v[i].a,i);
c[0]=z;c[z]=i;
total+=v[i].b*(v[c[p]].a+(i-c[p])*s);
}*/
for(i=2;i<=n;i++){
if(i-t>c[p]) p++;
z=caut(v[i].a,i);
c[z]=i;c[0]=z;
total+=v[i].b*(v[c[p]].a+(i-c[p])*s);
}
printf("%lld\n",total);
}