Pagini recente » Cod sursa (job #2831465) | Cod sursa (job #616356) | Cod sursa (job #2052435) | Cod sursa (job #2357684) | Cod sursa (job #208827)
Cod sursa(job #208827)
#include <stdio.h>
#define N 100001
long long n,s,h[N],poz;
long long t;
struct ab{
long long a,b;
};
ab v[N];
void swap(long long &x,long long &y){
long long z=x;x=y;y=z;
}
void sift(long long h[],long long k,long long n){
long long son=0;
do
if(2*k<=n) {
son=2*k;
if(2*k+1<=n && v[h[son]].a+(poz-h[son])*t>v[h[2*k+1]].a+(poz-h[2*k+1])*t)
son=2*k+1;
if(v[h[son]].a + (poz-h[son])*t >= v[h[k]].a + (poz-h[k])*t )
son=0;
else {
swap(h[son],h[k]);
k=son;
}
}
else son=0;
while(son);
}
void percolate(long long h[],long long k,long long n){
while(k>1 && v[h[k/2]].a+(poz-h[k/2])*t>v[h[k]].a+(poz-h[k])*t){
swap(h[k/2],h[k]);
k/=2;
}
}
void add(long long h[],long long key,long long &n){
h[++n]=key;
percolate(h,n,n);
}
void cut(long long h[],long long k,long long &n){
h[k]=h[n]; n--;
if(k>1 && v[h[k/2]].a+(poz-h[k/2])*t > v[h[k]].a +(poz-h[k])*t)
percolate(h,k,n);
else
sift(h,k,n);
}
int main(){
long long i,nr=1;
long long sol;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld%lld%lld",&n,&t,&s);
for(i=1;i<=n;i++)
scanf("%lld%lld",&v[i].a,&v[i].b);
h[1]=1;sol=v[1].a*v[1].b;
for(poz=2;poz<=n;poz++){
add(h,poz,nr);
if(poz-h[1]>s)
cut(h,1,nr);
sol+=( v[h[1]].a+(poz-h[1])*t ) * v[poz].b;
}
printf("%lld\n",sol);
return 0;
}