Pagini recente » Cod sursa (job #1814067) | Cod sursa (job #2392457) | Cod sursa (job #61566) | Cod sursa (job #1281188) | Cod sursa (job #203988)
Cod sursa(job #203988)
#include<stdio.h>
#define N 100007
struct branz{
long long a,b;
};
branz v[N];
long long s,z=0;
inline long long val(int k,int l){
return v[k].a+((long long)(l-k))*s;
}
int p,u;
int c[N];
int bynary(int k,int p,int u){
long long y=val(k,k);
while(p!=u)
if(y<=val(c[(p+u)/2],k))
u=(p+u)/2;
else
p=(p+u)/2+1;
if(val(c[p],k)>=y)
return p;
return p+1;
}
int main(){
int i,q,t,n;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%lld%d",&n,&s,&t);
p=u=0;
scanf("%lld%lld",&v[1].a,&v[1].b);
c[u]=1;
z=val(1,1);
for(i=2;i<=n;++i){
scanf("%lld%lld",&v[i].a,&v[i].b);
if(i-c[p]>t)
++p;
q=bynary(i,p,u);
u=q;
c[q]=i;
z+=val(c[p],i)*v[i].b;
}
printf("%lld\n",z);
return 0;
}