Pagini recente » Cod sursa (job #1766099) | Cod sursa (job #2193414) | Cod sursa (job #1257745) | Cod sursa (job #2185856) | Cod sursa (job #68632)
Cod sursa(job #68632)
#include <stdio.h>
#define NMAX 100000
typedef struct deque
{
long long e;
int poz;
};
deque d[NMAX+5];
inline int min(int a, int b) { return (a < b) ? a : b; }
int st, dr;
int c[NMAX+5], p[NMAX+5];
int n, t, s;
long long res;
int main()
{
int i;
long long aux;
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
st = 1;
dr = 1;
scanf("%d %d %d", &n, &s, &t);
scanf("%d %d", c+1, p+1);
res += c[1]*p[1];
d[1].poz = 1;
d[1].e = c[1] + s*(n-1);
for(i = 2; i <= n; ++i)
{
scanf("%d %d", c+i, p+i);
aux = c[i];
if(d[st].poz < i-t)
++st;
aux = min(aux, d[st].e - s*(n-i));
res += aux*p[i];
aux += s*(n-i);
while(st <= dr && d[dr].e - s*(n-i) >= aux-s*(n-i))
--dr;
d[++dr].poz = i;
d[dr].e = aux;
}
printf("%lld\n", res);
return 0;
}