Cod sursa(job #2466603)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 2 octombrie 2019 18:28:01
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <deque>

using namespace std;

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

struct chestie
{
    long long val, poz;
};

deque<chestie> dq;
long long n, s, t;

void add(long long C, long long P, long long i)
{
    long long curV = C * P;
    while(!dq.empty() && P * dq.back().val + P * (i - dq.back().poz) * s > curV)
        dq.pop_back();
    dq.push_back({C, i});
}

int main()
{
    fin >> n >> s >> t;

    long long rez = 0;
    for(long long i = 1; i <= n; ++i)
    {
        long long C, P;
        fin >> C >> P;

        if(i > t){
            if(dq.front().poz == i - t - 1)
                dq.pop_front();
        }
        add(C, P, i);
        rez += (P * dq.front().val + P * (i - dq.front().poz) * s);
    }
    fout << rez << '\n';
    return 0;
}