Cod sursa(job #1809207)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 18 noiembrie 2016 18:32:26
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <cstdio>
#include <deque>

using namespace std;

const int Nmax = 100005;

long long N,S,T;
long long sum;
long long P[Nmax], C[Nmax];

deque < long long > Dq;

bool comp(int i, int j)
{
    if((i-j)*S+C[j]<C[i])
        return 0;

    else
        return 1;
}

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

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

void Solve()
{
    Dq.push_back(1);

    sum=C[1]*P[1];

    for(int i=2; i<=N; ++i)
    {

        if(i-Dq.front()>T)
            Dq.pop_front();

        while(!Dq.empty() && comp(i,Dq.back()))
             Dq.pop_back();

        Dq.push_back(i);

        sum+=((C[Dq.front()]+S*(i-Dq.front()))*P[i]) * 1LL;
    }
}

int main()
{
    freopen("branza.in", "r", stdin);
    freopen("branza.out", "w", stdout);

    Read();
    Solve();
    printf("%lld", sum);

    return 0;
}