Pagini recente » Atasamentele paginii minmax | Cod sursa (job #3149161) | Cod sursa (job #331489) | Cod sursa (job #2820962) | Cod sursa (job #68428)
Cod sursa(job #68428)
#include <stdio.h>
#define MAX_N 100005
#define FIN "branza.in"
#define FOUT "branza.out"
#define ll long long
int N, S, T, P[MAX_N], C[MAX_N], Q[MAX_N];
long long Res;
int main(void)
{
int i, ql, qr;
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d %d %d", &N, &S, &T);
for (ql = 0, qr = -1, i = 0; i < N; i++)
{
scanf("%d %d", C+i, P+i);
for (; ql <= qr && Q[ql] < i-T; ql++);
for (; ql <= qr && C[Q[qr]]-(ll)Q[qr]*S >= C[i]-(ll)i*S; qr--);
Q[++qr] = i;
Res += (C[Q[ql]]+(ll)(i-Q[ql])*S)*P[i];
}
printf("%lld\n", Res);
return 0;
}