Cod sursa(job #240313)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 7 ianuarie 2009 10:56:58
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <deque>

using namespace std;

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

deque<int> Q;

int C[NMAX], P[NMAX], M[NMAX], Sol, 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 * (N - i )) < ( C[ Q.back()] + S * ( N - Q.back())))
            Q.pop_back();
        Q.push_back(i);
        M[i] = C[ Q.front()] + S*( N - Q.front()) - S * (N - i);
    }
    for (i = 1; i <= N; ++i)
        Sol += M[i] * P[i];
    printf("%d\n", Sol);
    return 0;
}