Pagini recente » Cod sursa (job #2787377) | Cod sursa (job #1334424) | Cod sursa (job #513759) | Cod sursa (job #2024628) | Cod sursa (job #933199)
Cod sursa(job #933199)
#include<stdio.h>
long long d[100001], c[100001],p[100001],deque[100001];
int st=1,dr=0,n,s,t;
void stanga(int i){
if(i-deque[st]+1>t)
st++;
}
void dreapta(int i){
while(st<=dr && c[i]<0LL+c[deque[dr]]+s*(i-deque[dr]))
dr--;
}
inline long long minim(long long a, long long b)
{
if(a<=b)
return a;
return b;
}
int main ()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
for(int i=1;i<=n;i++){
scanf("%lld %lld",&c[i],&p[i]);
if (i>1)d[i]=0LL+minim(c[i]*p[i],1LL*s*p[i]*(i-deque[st])+c[deque[st]]*p[i])+d[i-1];
else
d[1]=c[i]*p[i];
stanga(i);
dreapta(i);
deque[++dr]=i;
}
printf("%lld",d[n]);
return 0;
}