Cod sursa(job #100139)

Utilizator raula_sanChis Raoul raula_san Data 11 noiembrie 2007 22:02:28
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <cstdio>
#include <deque>

#define maxN 100001

using namespace std;

deque <long long> dq;

long long N;
long long S;
long long T;
long long C[maxN];
long long D[maxN];
long long M[maxN];

long long cost(long long i)
{
    return
        C[i] + (N-i) * S;
}

void baga_dq(long long val)
{
    if(dq.empty() == true)
        dq.push_front(val);

    else
    {
        if(cost(dq.back()) < cost(val))
            dq.push_back(val);
        else
        {
            while(cost(dq.back()) > cost(val) && dq.empty() == false)
                dq.pop_back();

            dq.push_back(val);
        }
    }
}

int main()
{
    freopen("branza.in", "rt", stdin);
    freopen("branza.out", "wt", stdout);

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

    int i, lim;

    long long min;

    for(i=1; i<=N; ++i)
        scanf("%lld %lld", C+i, D+i);

    M[1] = C[1];
    baga_dq(1);

    for(i=2; i<=N; ++i)
    {
        lim = 1 > i - T ? 1 : i - T;
    
        while(dq.front() < lim)
            dq.pop_front();

        min = cost(dq.front());

        if(C[i] < min - ((N-i) * S))
            M[i] = C[i];
        else
            M[i] = min - ((N-i) * S);

        baga_dq(i);
    }

    long long sol = 0;

    for(i=1; i<=N; ++i)
        sol += D[i] * M[i];

    printf("%lld", sol);

    fclose(stdin);
    fclose(stdout);

    return 0;
}