Cod sursa(job #240315)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 7 ianuarie 2009 11:00:30
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <cstdio>
#include <deque>

using namespace std;

#define FIN "branza.in"
#define FOUT "branza.out"
#define NMAX 100100

deque<int> Q;

long long C[NMAX], P[NMAX], M[NMAX], Sol;
int N, S, T;

int main(){
    int i,j;

    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);

    scanf("%d%d%d", &N, &S, &T);

    for (i = 1; i <= N; ++i)
        scanf("%d%d", &C[i], &P[i]);

    Q.push_back(1);
    M[1] = C[1];

    for (i = 2; i <= N; ++i){
        j = i - T;
        while (!Q.empty() && Q.front() < j)
            Q.pop_front();
        while (!Q.empty() &&  C[i] + S * (long long)(N - i ) < ( C[ Q.back()] + S * (long long)( N - Q.back() )))
            Q.pop_back();
        Q.push_back(i);
        M[i] = C[ Q.front()] + S * (long long)(N - Q.front()) - S * (long long)(N - i);
    }
    for (i = 1; i <= N; ++i)
        Sol += M[i] * P[i];
    printf("%lld\n", Sol);
    return 0;
}