Pagini recente » Cod sursa (job #2205101) | Cod sursa (job #390574) | Cod sursa (job #805160) | Cod sursa (job #300274) | Cod sursa (job #209177)
Cod sursa(job #209177)
#include <stdio.h>
#define maxl 100010
long long n,s,t,i,st,dr;
long long brz[maxl][2];
long long deq[maxl];
long long cost;
int main() {
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%lld %lld %lld",&n,&s,&t);
for (i=1; i<=n; i++)
scanf("%lld %lld",&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;
}