Cod sursa(job #743028)
Utilizator | Data | 2 mai 2012 21:55:57 | |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.52 kb |
#include <stdio.h>
#define NMAX 100100
int Q[NMAX], val[NMAX];
int main()
{
int N, S, T, p = 1, u = 0, C, P;
long long sol = 0;
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", &C, &P);
val[i] = C - i * S;
while (p <= u && val[i] <= val[Q[u]])
u--;
Q[++ u] = i;
sol += (long long)P * (val[Q[p]] + i * S);
if (Q[p] + T == i)
p ++;
}
printf ("%lld", sol);
return 0;
}