Pagini recente » Cod sursa (job #1596377) | Cod sursa (job #2586310) | Cod sursa (job #1372974) | Cod sursa (job #1457190) | Cod sursa (job #208824)
Cod sursa(job #208824)
#include <stdio.h>
#define N 100001
int n,s,h[N],poz;
long long t;
struct ab{
long long a,b;
};
ab v[N];
void swap(int &x,int &y){
int z=x;x=y;y=z;
}
void sift(int h[],int k,int n){
int 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;
}
}
while(son);
}
void percolate(int h[],int k,int 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(int h[],int key,int &n){
h[++n]=key;
percolate(h,n,n);
}
void cut(int h[],int k,int &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(){
int i,nr=1;
long long sol;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d%lld%d",&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;
}