Cod sursa(job #74663)
Utilizator | Andrei Grigorean wefgef | Data | 26 iulie 2007 21:16:28 |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <cstdio>
#define Nmax 100005
int n, s, t;
int c[Nmax];
int Q[Nmax], qe, qb;
long long ret;
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
int i, need;
scanf("%d %d %d", &n, &s, &t);
qe = 0; qb = 1;
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &c[i], &need);
while (qe >= qb && (i-Q[qe])*s + c[Q[qe]] >= c[i]) --qe;
Q[++qe] = i;
if (i-Q[qb] == t) ++qb;
ret += need*(c[Q[qb]] + (i-Q[qb])*s);
}
printf("%lld\n", ret);
return 0;
}