Cod sursa(job #3158504)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 18 octombrie 2023 20:57:57
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int NMAX = 100003;
deque<pair<int,int> > dq;
int n, s, t, c[NMAX], p[NMAX];
long long res = 0;

int main() {

    fin >> n >> s >> t;
    for (int i = 1; i <= n; i++) {
        fin >> c[i] >> p[i];
    }

    for (int i = 1; i <= n; i++) {
        int cost = c[i] - i * s;
        while (!dq.empty() && cost < dq.back().first)
            dq.pop_back();
        while (!dq.empty() && i - dq.front().second > t)
            dq.pop_front();

        dq.push_back(make_pair(cost, i));

        res += (i * s + dq.front().first) * p[i];
    }

    fout << res;

    return 0;
}