Cod sursa(job #2801769)

Utilizator wav_uuwRares Paul wav_uuw Data 16 noiembrie 2021 20:43:16
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.61 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream f("branza.in");
ofstream g("branza.out");

int main()
{
    int n, s, k;
    f >> n >> s >> k;
    
    k++;

    deque<int> d;

    int c[100001], p;
    long long sum = 0;
    for(int i = 0; i < n; i++)
    {
        f >> c[i] >> p;

        if(!d.empty() && d.front() == i - k)
            d.pop_front();

        while(!d.empty() && c[d.back()] + s * (i - d.back()) >= c[i])
            d.pop_back();

        d.push_back(i);

        sum += (c[d.front()] + s * (i - d.front())) * p;
    }

    g << sum;

    f.close();
    g.close();
    return 0;
}