Pagini recente » Cod sursa (job #3261883) | Cod sursa (job #567153) | Cod sursa (job #1679345) | Cod sursa (job #1917251) | Cod sursa (job #120142)
Cod sursa(job #120142)
#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;
while(compar(aux,h[min=minim(k*2,k*2+1)])>0){
h[k]=h[min];
k=min;
}
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;
}