Cod sursa(job #252310)

Utilizator Mishu91Andrei Misarca Mishu91 Data 4 februarie 2009 11:03:04
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>
#include <deque>

using namespace std;

#define MAX_N 100005
#define val first
#define poz second

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

void citire()
{
    scanf("%d %lld %d",&N, &S, &T);

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

void solve()
{
    deque <pair<long long, int> > Q;

    for(int i = 1; i <= N; ++i)
    {
        long long x = (N - i)*S + P[i];
        while(!Q.empty() &&  Q.back().val >= x) Q.pop_back();
        while(!Q.empty() &&  Q.front().poz <= i-T-1) Q.pop_front();

        Q.push_back(make_pair(x, i));

        M[i] = Q.front().val - S*(N-i);
    }
    long long Rez = 0;
    for(int i = 1; i <= N; ++i)
        Rez += M[i]*C[i];
    printf("%lld\n",Rez);
}

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

    citire();
    solve();
}