Cod sursa(job #2986309)

Utilizator IanDoIan Dontu IanDo Data 28 februarie 2023 11:26:03
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include <fstream>
#include <deque>
using namespace std;

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

const int NMAX = 1e5;

int main() {
    deque <int> dq;
    int n, s, t, c [NMAX];
    fin >> n >> s >> t;
    ++t;
    long long sum = 0;
    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 += (long long)p * (c [dq.front()] + s * (i - dq.front()));
    }
    fout << sum;
    fin.close();
    fout.close();
    return 0;
}