Cod sursa(job #68428)

Utilizator dominoMircea Pasoi domino Data 27 iunie 2007 21:20:04
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#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;
}