Pagini recente » Cod sursa (job #1777265) | Cod sursa (job #2744868) | Cod sursa (job #2028591) | Cod sursa (job #443550) | Cod sursa (job #120138)
Cod sursa(job #120138)
#include<stdio.h>
#define NMAX 100000
#define INF 20000000
typedef struct
{
int c,p;
}heap;
heap h[NMAX+1];
int s;
inline int 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(int 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(int i)
{
for(int j=1; j<=i; j++)
printf("(%d,%d) ",h[j].c,h[j].p);
printf("\n");
}
inline int minim(int x,int y)
{
if(compar(h[x],h[y])<=0)
return x;
return y;
}
void elimin(int &m)
{
heap aux=h[m];
int min,k=1;
while(2*k<m&&compar(aux,h[min=minim(k*2,k*2+1)])>0){
h[k]=h[min];
k=min;
}
h[k]=aux;
--m;
}
void init(){
for(int i=0;i<=NMAX;++i)
h[i].c=INF;
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
init();
int n,t,cost=0,nr,m=1;
scanf("%d%d%d",&n,&s,&t);
scanf("%d%d",&h[1].c,&nr);
cost+=h[1].c*nr;
h[1].p=1;
for(int i=2; i<=n; i++){
scanf("%d%d",&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("%d",cost);
return 0;
}