Cod sursa(job #3170808)

Utilizator RaduIC12Ciocirlan Radu-Ioan RaduIC12 Data 18 noiembrie 2023 10:11:56
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>
using namespace std;

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

int cost[100000];

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

    t++;

    long long rez = 0;

    deque<int> dq;

    for(int i = 0; i < n; ++i)
    {
        fin >> cost[i] >> x_kg;
        if(!dq.empty() && dq.front() == i-t)
            dq.pop_front();

        while(!dq.empty() && cost[i] <= cost[dq.back()] + ((i - dq.back()) * s))
            dq.pop_back();

        dq.push_back(i);

        rez = rez + (long long) x_kg * (cost[dq.front()] + ((i-dq.front()) * s));
    }

    fout << rez;

    return 0;
}