Cod sursa(job #2989840)

Utilizator MAlex2019Melintioi George Alexandru MAlex2019 Data 7 martie 2023 08:50:50
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int MAXN = 1e5;
int c[MAXN];

int main() {
    int n, s, t;
    fin >> n >> s >> t;
    t++;
    long long sum = 0;
    deque<int> dq;
    for (int i = 0; i < n; ++i) {
        int p;
        fin >> c [i] >> p;
        if (!dq.empty() && dq.front() == i - t)
            dq.pop_front();
        while (!dq.empty() && c[i] <= c[dq.back()] + s*(i - dq.back()))
            dq.pop_back();
        dq.push_back(i);
        sum += 1LL*p*(c[dq.front()] + s*(i - dq.front()));
    }
    fout << sum;
    return 0;
}