Pagini recente » Cod sursa (job #2246990) | Cod sursa (job #779958) | Cod sursa (job #1833731) | Cod sursa (job #984302) | Cod sursa (job #114435)
Cod sursa(job #114435)
#include<stdio.h>
int n, cs, t, i, first, last, cost, nr;
long long rezultat;
struct deque{
int v, i;
};
deque q[100005];
int main()
{
freopen("branza.in", "rt", stdin);
freopen("branza.out", "wt", stdout);
scanf("%d%d%d", &n, &cs, &t);
rezultat = 0;
first = 1, last = 0;
for (i=1; i<=n; i++){
scanf("%d%d", &cost, &nr);
while (first <= last && q[first].i + t < i)
first ++;
while (first <= last && nr*(q[last].v + (i-q[last].i)*cs) > nr*cost)
last --;
q[++last].v = cost;
q[last].i = i;
rezultat += nr*(q[first].v + (i-q[first].i)*cs);
}
printf("%lld\n", rezultat);
fclose(stdin);
fclose(stdout);
return 0;
}