Cod sursa(job #1098864)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 5 februarie 2014 12:05:22
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

ifstream fin("branza.in");
ofstream fout("branza.out");

const int Nmax = 100100;
const int oo = 0x3f3f3f3f;

long long N, T, S, C[Nmax], P[Nmax], sol;
deque <int> D;

int main()
{
    fin >> N >> S >> T;
    for(int i = 1; i <= N; i++)
        fin >> C[i] >> P[i];

    D.push_back(1); sol = C[1] * P[1];
    for(int i = 2; i <= N; i++)
    {
        int poz = D.front();
        sol += min(C[i] * P[i], C[poz] * P[i] + S * P[i] * (i - poz));

        poz = D.back();
        while(!D.empty() && C[poz] + S * (i - poz) >= C[i])
            D.pop_back(), poz = D.back();
        D.push_back(i);
        if(D.front() <= i - T)
            D.pop_front();
    }
    fout << sol;
    return 0;
}