Pagini recente » Cod sursa (job #39622) | Cod sursa (job #2929262) | Cod sursa (job #1372009) | Cod sursa (job #2977303) | Cod sursa (job #120155)
Cod sursa(job #120155)
#include<stdio.h>
#define NMAX 100000
#define INF 20000000
typedef struct
{
long long c,p;
}heap;
heap h[NMAX+1];
long long s;
inline long long compar(heap x,heap y){
if(s*(x.p-y.p)+y.c>x.c)
return -1;
if(s*(x.p-y.p)+y.c<x.c)
return 1;
return 0;
}
void adaugare(long long m)
{
heap aux=h[m];
while(compar(aux,h[m/2])<=0&&m>=2)
{
h[m]=h[m/2];
m/=2;
}
h[m]=aux;
}
/*
void scrie(long long i)
{
for(long long j=1; j<=i; j++)
printf("(%d,%d) ",h[j].c,h[j].p);
printf("\n");
}
*/
inline long long minim(long long x,long long y)
{
if(compar(h[x],h[y])<=0)
return x;
return y;
}
void elimin(long long &m)
{
heap aux=h[m];
long long min,k=1,k1=minim(2*k,2*k+1);
/*
while(k*2+1<=NMAX&&compar(aux,h[min=minim(k*2,k*2+1)])>0){
h[k]=h[min];
k=min;
}
while((k*2<m&&compar(aux,h[k*2])>0)||(k*2+1<m&&compar(aux,h[k*2+1])>0)){
if(k*2+1>=m)
min=k*2;
else
min=minim(k*2,k*2+1);
h[k]=h[min];
k=min;
}
*/
while(k1<=m&&compar(aux,h[k1])>0){
h[k]=h[k1];
k=k1;
k1=minim(2*k,2*k+1);
}
h[k]=aux;
--m;
}
void init(){
for(long long i=0;i<=NMAX;++i)
h[i].c=INF;
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
init();
long long n,t,cost=0,nr,m=1;
scanf("%lld%lld%lld",&n,&s,&t);
scanf("%lld%lld",&h[1].c,&nr);
cost+=h[1].c*nr;
h[1].p=1;
for(long long i=2; i<=n; i++){
scanf("%lld%lld",&h[i].c,&nr);
h[i].p=i;
adaugare(++m);
while(i-h[1].p>=t)
elimin(m);
//scrie(m);
cost+=nr*(h[1].c+s*(i-h[1].p));
}
printf("%lld",cost);
return 0;
}