Cod sursa(job #2884780)

Utilizator vlad_miscociMiscoci Vlad Andrei vlad_miscoci Data 4 aprilie 2022 21:01:22
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <deque>
using namespace std;
long long p[10000005];
int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n, k, c;
    long long rez=0, s;
    in >> n >> s >> k;
    k++;
    deque <int> d;
    for(int i=0; i<n; i++)
    {
        in >> p[i];
        in >> c;
        if(!d.empty() && d.front() == i-k)
            d.pop_front();
        while(!d.empty() && p[i] <= p[d.back()] + (i - d.back()) * s)
            d.pop_back();

        d.push_back(i);

        rez += c * (p[d.front()] + (i - d.front()) * s);
    }
    out << rez;
    return 0;
}