Cod sursa(job #2583419)

Utilizator lucamLuca Mazilescu lucam Data 18 martie 2020 11:39:22
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");

const int NM = 1e5;
int pret[NM];

int main()
{
    int n, s, t;
    fin >> n >> s >> t;
    ++t;
    deque<int> d;
    long long p = 0;
    for (int i = 0; i < n; ++i) {
        int c;
        fin >> pret[i] >> c;
        if (!d.empty() && d.back() == i - t)
            d.pop_back();
        while (!d.empty() && pret[d.front()] + (i - d.front()) * s >= pret[i])
            d.pop_front();
        d.push_front(i);
        p += (long long)c * (pret[d.back()] + (long long)(i - d.back()) * s);
    }
    fout << p << '\n';
    return 0;
}