Cod sursa(job #3127279)

Utilizator dandragosDan Dragos dandragos Data 7 mai 2023 14:10:15
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

int main()
{
std::ifstream file_in("branza.in");
std::ofstream file_out("branza.out");
long long n, s, t, cost = 0;
std::deque<long long> d;
file_in >> n >> s >> t;

std::vector<long long> c(n + 2), p(n + 2);
for (int i = 1; i <= n; i++) {
    file_in >> c[i] >> p[i];
}

for (int i = 1; i <= n; i++) {

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

    d.push_back(i);

    while (!d.empty() && i - d.front() > t) {
        d.pop_front();
    }

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

file_out << cost;

file_in.close();
file_out.close();

return 0;
}