Cod sursa(job #2728873)

Utilizator ChelaruPaulChelaru Paul ChelaruPaul Data 23 martie 2021 20:11:43
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

deque<long long> coada;
int n, s, t;
unsigned int nrMin = 0;

int main() {
    fin >> n >> s >> t;
    unsigned int c[n + 10], p[n + 10];

    for (int i = 0; i < n; i++) {
        fin >> c[i] >> p[i];

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

        while ((!coada.empty()) && (i - coada.front() > t))
            coada.pop_front();

        coada.push_back(i);
        nrMin = nrMin + p[i] * (c[coada.front()] + (i - coada.front()) * s);
    }
    fout << nrMin << endl;
    return 0;
}