Pagini recente » Cod sursa (job #964947) | Cod sursa (job #1592400) | Cod sursa (job #2644191) | Cod sursa (job #272752) | Cod sursa (job #209176)
Cod sursa(job #209176)
#include <stdio.h>
#define maxl 100010
int n,s,t,i,st,dr;
int brz[maxl][2];
int deq[maxl];
long long cost;
int main() {
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
for (i=1; i<=n; i++)
scanf("%d %d",&brz[i][0],&brz[i][1]);
st=1;t++;
for (i=1; i<=n; i++) {
if (i-t+1>deq[st]) st++;
deq[++dr]=i;
while (dr-1>=st && brz[deq[dr]][0]+s*(i-deq[dr]) < brz[deq[dr-1]][0]+s*(i-deq[dr-1])) {
deq[dr-1]=deq[dr];
dr--;
}
cost+=brz[deq[st]][0]*brz[i][1]+s*(i-deq[st])*brz[i][1];
}
printf("%lld\n",cost);
return 0;
}