Cod sursa(job #1061431)

Utilizator mvcl3Marian Iacob mvcl3 Data 19 decembrie 2013 19:32:37
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <deque>

#define in "branza.in"
#define out "branza.out"
#define Max_Size 100009
#define LL long long

std :: ifstream f(in);
std :: ofstream g(out);

int N, S, T;
int V[Max_Size];
LL rez;

std :: deque < int > DQ;

int main()
{
    f >> N >> S >> T;

    int cost, cant;

    for(int i = 1;i <= N; ++i)
    {
        f >> cost >> cant;

        V[i] = cost - i * S;

        while(!DQ.empty() && V[DQ.front()] >= V[i]) DQ.pop_back();
        DQ.push_back(i);

        rez += cant * (V[DQ.front()] + i * S);

        if(DQ.front() + T == i) DQ.pop_front();
    }

    g << rez << '\n';

    g.close();
    return 0;
}