Pagini recente » Cod sursa (job #1676067) | Cod sursa (job #306634) | Cod sursa (job #1849399) | Cod sursa (job #1507899) | Cod sursa (job #209175)
Cod sursa(job #209175)
#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;
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;
}