Cod sursa(job #2884772)

Utilizator vlad_miscociMiscoci Vlad Andrei vlad_miscoci Data 4 aprilie 2022 20:44:35
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <fstream>
#include <deque>
using namespace std;
int p[100005];
int main()
{
    ifstream in("branza.in");
    ofstream out("branza.out");
    int n, s, k, rez=0;
    in >> n >> s >> k;
    deque<int> d;
    for(int i=0; i<n; i++)
    {
        int c;
        in >> p[i] >> 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();

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